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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Using FailureDirectedSearchEmphasis=3.5.
- 2.
Using FailureDirectedSearch=Off.
- 3.
All instances of the benchmark are feasible except for 5 instances of the de family.
- 4.
Computed from the detailed results the authors gratefully sent us.
- 5.
Using TemporalRelaxation=Off.
- 6.
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.
- 7.
Note that FDS is automatically switched off for large problems. Here, it is not being used for problems with 500 and 1000 jobs.
References
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)
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_14
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_2
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_24
Hooker, J.N.: Planning and scheduling by logic-based benders decomposition. Oper. Res. 55(3), 588–602 (2007)
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)
Laborie, P., Rogerie, J., Shaw, P., Vilím, P.: IBM ILOG CP optimizer for scheduling. Constraints J. 23(2), 210–250 (2018)
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)
Mistry, M., D’Iddio, A.C., Huth, M., Misener, R.: Satisfiability modulo theories for process systems engineering. Optimization Online (2017)
Tesch, A.: Compact MIP models for the resource-constrained project scheduling problem. Master’s thesis, Technische Universität Berlin (2015)
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_22
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_30
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Laborie, P. (2018). An Update on the Comparison of MIP, CP and Hybrid Approaches for Mixed Resource Allocation and Scheduling. In: van Hoeve, WJ. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2018. Lecture Notes in Computer Science(), vol 10848. Springer, Cham. https://doi.org/10.1007/978-3-319-93031-2_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-93031-2_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-93030-5
Online ISBN: 978-3-319-93031-2
eBook Packages: Computer ScienceComputer Science (R0)