nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

An Update on the Comparison of MIP, CP and Hybrid Approaches for Mixed Resource Allocation and Scheduling

verfasst von : Philippe Laborie

Erschienen in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider a well known resource allocation and scheduling problem for which different approaches like mixed-integer programming (MIP), constraint programming (CP), constraint integer programming (CIP), logic-based Benders decompositions (LBBD) and SAT-modulo theories (SMT) have been proposed and experimentally compared in the last decade. Thanks to the recent improvements in CP Optimizer, a commercial CP solver for solving generic scheduling problems, we show that a standalone tiny CP model can out-perform all previous approaches and close all the 335 instances of the benchmark. The article explains which components of the automatic search of CP Optimizer are responsible for this success. We finally propose an extension of the original benchmark with larger and more challenging instances.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Objective Landscapes for Constraint Programming

Nächstes Kapitel Modelling and Solving the Senior Transportation Problem

Using FailureDirectedSearchEmphasis=3.5.

Using FailureDirectedSearch=Off.

All instances of the benchmark are feasible except for 5 instances of the de family.

Computed from the detailed results the authors gratefully sent us.

Using TemporalRelaxation=Off.

As a comparison, this scheduling gap is only 0.77% in average for the instances of the ‘c’ family with 20 jobs and 2 facilities.

Note that FDS is automatically switched off for large problems. Here, it is not being used for problems with 500 and 1000 jobs.

Ciré, A., Çoban, E., Hooker, J.N.: Logic-based benders decomposition for planning and scheduling: a computational analysis. Knowl. Eng. Rev. 31(5), 440–451 (2016)CrossRef

Erschler, J., Lopez, P.: Energy-based approach for task scheduling under time and resources constraints. In: Proceedings of the 2nd International Workshop on Project Management and Scheduling, pp. 115–121 (1990)

Heinz, S., Beck, J.C.: Solving resource allocation/scheduling problems with constraint integer programming. In: Proceedings of the Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS 2011), pp. 23–30 (2011)

Heinz, S., Beck, J.C.: Reconsidering mixed integer programming and MIP-based hybrids for scheduling. In: Beldiceanu, N., Jussien, N., Pinson, É. (eds.) CPAIOR 2012. LNCS, vol. 7298, pp. 211–227. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29828-8_14CrossRef

Heinz, S., Ku, W.-Y., Beck, J.C.: Recent improvements using constraint integer programming for resource allocation and scheduling. In: Gomes, C., Sellmann, M. (eds.) CPAIOR 2013. LNCS, vol. 7874, pp. 12–27. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38171-3_2CrossRef

Hooker, J.N.: A hybrid method for planning and scheduling. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 305–316. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30201-8_24CrossRef

Hooker, J.N.: Planning and scheduling by logic-based benders decomposition. Oper. Res. 55(3), 588–602 (2007)MathSciNetCrossRef

Laborie, P., Godard, D.: Self-adapting large neighborhood search: application to single-mode scheduling problems. In: Baptiste, P., Kendall, G., Munier-Kordon, A., Sourd, F. (eds.) Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA 2007), pp. 276–284. Paris, France, 28–31 Aug 2007

Laborie, P., Rogerie, J.: Temporal linear relaxation in IBM ILOG CP optimizer. J. Sched. 19(4), 391–400 (2016)MathSciNetCrossRef

10.

Laborie, P., Rogerie, J., Shaw, P., Vilím, P.: IBM ILOG CP optimizer for scheduling. Constraints J. 23(2), 210–250 (2018)MathSciNetCrossRef

11.

Laborie, P., Rogerie, J.: Reasoning with conditional time-intervals. In: Proceedings of the 21th International Florida Artificial Intelligence Research Society Conference (FLAIRS 2008), pp. 555–560 (2008)

12.

Mistry, M., D’Iddio, A.C., Huth, M., Misener, R.: Satisfiability modulo theories for process systems engineering. Optimization Online (2017)

13.

Tesch, A.: Compact MIP models for the resource-constrained project scheduling problem. Master’s thesis, Technische Universität Berlin (2015)

14.

Vilím, P.: Timetable edge finding filtering algorithm for discrete cumulative resources. In: Achterberg, T., Beck, J.C. (eds.) CPAIOR 2011. LNCS, vol. 6697, pp. 230–245. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21311-3_22CrossRefMATH

15.

Vilím, P., Laborie, P., Shaw, P.: Failure-directed search for constraint-based scheduling. In: Michel, L. (ed.) CPAIOR 2015. LNCS, vol. 9075, pp. 437–453. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-18008-3_30CrossRefMATH

Titel: An Update on the Comparison of MIP, CP and Hybrid Approaches for Mixed Resource Allocation and Scheduling
verfasst von: Philippe Laborie
Verlag: Springer International Publishing
Buch: Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Print ISBN: 978-3-319-93030-5

Electronic ISBN: 978-3-319-93031-2

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-93031-2_29

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"