Mixed-Integer Programming vs. Constraint Programming for Shop Scheduling Problems: New Results and Outlook

References

• Androutsopoulos KN, Manousakis EG, Madas MA (2020) Modeling and solving a bi-objective airport slot scheduling problem. Eur. J. Oper. Res. 284(1):135–151.Crossref, Google Scholar
• Applegate D, Cook W (1991) A computational study of the job-shop scheduling problem. ORSA J. Comput. 3(2):149–156.Link, Google Scholar
• Booth KEC, Tran TT, Beck JC (2016) Logic-based decomposition methods for the travelling purchaser problem. Claude-Guy Quimper, ed. Integration of AI and OR Techniques in Constraint Programming. Proc. Internat. Conf. on AI and OR Techniques in Constraint Programming for Combinatorial Optim. Problems (Springer, Berlin), 55–64.Google Scholar
• Bowman EH (1959) Schedule-sequencing problem. Oper. Res. 7(5):612–614.Link, Google Scholar
• Brandimarte P (1993) Routing and scheduling in a flexible job shop by tabu search. Ann. Oper. Res. 41(3):157–183.Crossref, Google Scholar
• Brucker P, Hurink J, Jurisch B, Wöstmann B (1997) A branch & bound algorithm for the open-shop problem. Discrete Appl. Math. 76(1–3):43–59.Crossref, Google Scholar
• Bukchin Y, Raviv T (2018) Constraint programming for solving various assembly line balancing problems. Omega 78:57–68.Crossref, Google Scholar
• CPOptimizer (2017) IBM ILOG CPLEX Optimization Studio CP Optimizer User’s Manual, 12th ed. (IBM).Google Scholar
• Dauzère-Pérès S, Paulli J (1997) An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Ann. Oper. Res. 70:281–306.Crossref, Google Scholar
• Demirkol E, Mehta S, Uzsoy R (1998) Benchmarks for shop scheduling problems. Eur. J. Oper. Res. 109(1):137–141.Crossref, Google Scholar
• Doulabi SHH, Rousseau L-M, Pesant G (2016) A constraint-programming-based branch-and-price-and-cut approach for operating room planning and scheduling. INFORMS J. Comput. 28(3):432–448.Link, Google Scholar
• Fanjul-Peyro L, Ruiz R (2010) Iterated greedy local search methods for unrelated parallel machine scheduling. Eur. J. Oper. Res. 207(1):55–69.Crossref, Google Scholar
• Fattahi P, Mehrabad MS, Jolai F (2007) Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J. Intelligent Manufacturing 18(3):331–342.Crossref, Google Scholar
• Fontaine D, Michel L, Van Hentenryck P (2016) Parallel composition of scheduling solvers. Claude-Guy Quimper, ed. Integration of AI and OR Techniques in Constraint Programming (Springer International Publishing, Cham, Switzerland), 159–169.Crossref, Google Scholar
• Gedik R, Kalathia D, Egilmez G, Kirac E (2018) A constraint programming approach for solving unrelated parallel machine scheduling problem. Comput. Industrial Engrg. 121:139–149.Crossref, Google Scholar
• Guéret C, Prins C (1999) A new lower bound for the open shop problem. Ann. Oper. Res. 92(1–4):165–183.Crossref, Google Scholar
• Hooker JN, Yan H (2002) A relaxation of the cumulative constraint. Pascal Van Hentenryck, ed. Principles and Practice of Constraint Programming (Springer, Berlin), 686–691.Google Scholar
• Hurink J, Jurisch B, Thole M (1994) Tabu search for the job-shop scheduling problem with multi-purpose machines. Oper. Res. Spektrum 15(4):205–215.Crossref, Google Scholar
• IBM (2016) Constraint programming modeling for python v2.22 documentation. Accessed November 18, 2021, https://ibmdecisionoptimization.github.io/docplex-doc/cp/docplex.cp.modeler.py.html.Google Scholar
• Kreter S, Schutt A, Stuckey PJ, Zimmermann J (2018) Mixed-integer linear programming and constraint programming formulations for solving resource availability cost problems. Eur. J. Oper. Res. 266(2):472–486.Crossref, Google Scholar
• Ku W-Y, Beck JC (2016) Mixed integer programming models for job shop scheduling: A computational analysis. Comput. Oper. Res. 73:165–173.Crossref, Google Scholar
• Laborie P (2015) Modeling and solving scheduling problems with CP optimizer. Presentation, Continuously improve the CP Optimizer component of IBM ILOG CPLEX Optimization Studio, April 2015. https://doi.org/10.13140/RG.2.1.3984.0166.Google Scholar
• Laborie P (2018) An update on the comparison of MIP, CP and hybrid approaches for mixed resource allocation and scheduling. Willem-Jan van Hoeve, ed. Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Springer International Publishing, Cham, Switzerland), 403–411.Crossref, Google Scholar
• Laborie P, Godard D (2007) Self-adapting large neighborhood search: Application to single-mode scheduling problems. Baptiste P, Kendall G, Munier-Kordon A, Sourd F, eds. Proc. 3rd Multidisciplinary Internat. Conf. Scheduling: Theory Appl. (MISTA), 276–284.Google Scholar
• Laborie P, Rogerie J, Shaw P, Vilím P (2018) IBM ILOG CP optimizer for scheduling. 20+ years of scheduling with constraints at IBM/ILOG. Constraints 23(2):210–250.Crossref, Google Scholar
• Lawrence S (1984) Resource constrained project scheduling. Technical report, Carnegie Mellon University, Pittsburgh, PA.Google Scholar
• Malapert A, Cambazard H, Guéret C, Jussien N, Langevin A, Rousseau L-M (2012) An optimal constraint programming approach to the open-shop problem. INFORMS J. Comput. 24(2):228–244.Link, Google Scholar
• Manne AS (1960) On the job-shop scheduling problem. Oper. Res. 8(2):219–223.Link, Google Scholar
• Meng L, Zhang C, Ren Y, Zhang B, Lv C (2020) Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem. Comput. Industrial Engrg. 142:106347.Crossref, Google Scholar
• Naderi B, Roshanaei V (2021) Critical-path-search logic-based benders decomposition approaches for flexible job shop scheduling. INFORMS J. Optim. 4(1):1–28. https://doi.org/10.1287/ijoo.2021.0056.Google Scholar
• Naderi B, Ruiz R (2010) The distributed permutation flowshop scheduling problem. Comput. Oper. Res. 37(4):754–768.Crossref, Google Scholar
• Naderi B, Ruiz R, Roshanaei V (2023) Repository for mixed-integer programming versus constraint programming for shop scheduling problems: New results and outlook. URL http://dx.doi.org/10.5281/zenodo.7541223, https://github.com/INFORMSJoC/2021.0326.Google Scholar
• Naderi B, Roshanaei V, Luong C, Aleman M, Urbach D (2021) Increasing surgical capacity with additional resources: Generalized operating room planning and scheduling. Production Oper. Management 30(8):2608–3635.Crossref, Google Scholar
• Pan CH (1997) A study of integer programming formulations for scheduling problems. Internat. J. Systems Sci. 28(1):33–41.Crossref, Google Scholar
• Pan Q-K, Ruiz R, Alfaro-Fernández P (2017) Iterated search methods for earliness and tardiness minimization in hybrid flowshops with due windows. Comput. Oper. Res. 80:50–60.Crossref, Google Scholar
• Pour SM, Drake JH, Ejlertsen LS, Rasmussen KM, Burke EK (2018) A hybrid constraint programming/mixed integer programming framework for the preventive signaling maintenance crew scheduling problem. Eur. J. Oper. Res. 269(1):341–352.Crossref, Google Scholar
• Qin T, Du Y, Jiang HC, Sha M (2020) Combining mixed integer programming and constraint programming to solve the integrated scheduling problem of container handling operations of a single vessel. Eur. J. Oper. Res. 285(3):884–901.Crossref, Google Scholar
• Roshanaei V (2012) Mathematical modelling and optimization of flexible job shops scheduling problem. Accessed November 18, 2021, https://scholar.uwindsor.ca/etd/157.Google Scholar
• Roshanaei V, Naderi B (2021) Solving integrated operating room planning and scheduling: Logic-based benders decomposition vs. branch-price-and-cut. Eur. J. Oper. Res. 293(1):65–78.Crossref, Google Scholar
• Roshanaei V, Azab A, ElMaraghy H (2013) Mathematical modelling and a meta-heuristic for flexible job shop scheduling. Internat. J. Production Res. 51(20):6247–6274.Crossref, Google Scholar
• Roshanaei V, Booth KEC, Aleman D, Urbach D, Beck JC (2020) Branch-and-check approaches for multi-level or planning and scheduling. Internat. J. Production Econom. 220:107433.Crossref, Google Scholar
• Ruiz R, Maroto C, Alcaraz J (2005) Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics. Eur. J. Oper. Res. 165(1):34–54.Crossref, Google Scholar
• Samarghandi H, Behroozi M (2017) On the exact solution of the no-wait flow shop problem with due date constraints. Comput. Oper. Res. 81:141–159.Crossref, Google Scholar
• Schefers N, Juan JRG, Folch P, Munoz-Gamarra JL (2018) A constraint programming model with time uncertainty for cooperative flight departures. Transportation Res. Part C Emerging Tech. 96:170–191.Crossref, Google Scholar
• Stafford EF (1988) On the development of a mixed-integer linear-programming model for the flowshop sequencing problem. J. Oper. Res. Soc. 39(12):1163–1174.Crossref, Google Scholar
• Stafford EF, Tseng FT, Gupta JND (2005) Comparative evaluation of milp flowshop models. J. Oper. Res. Soc. 56(1):88–101.Crossref, Google Scholar
• Storer RH, Wu SD, Vaccari R (1992) New search spaces for sequencing problems with application to job shop scheduling. Management Sci. 38(10):1495–1509.Link, Google Scholar
• Taillard E (1993) Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64(2):278–285.Crossref, Google Scholar
• Tofighian AA, Naderi B (2015) Modeling and solving the project selection and scheduling. Comput. Industrial Engrg. 83:30–38.Crossref, Google Scholar
• Tran TT, Araujo A, Beck JC (2016) Decomposition methods for the parallel machine scheduling problem with setups. INFORMS J. Comput. 28(1):83–95.Link, Google Scholar
• Tseng FT, Stafford EF (2008) New milp models for the permutation flowshop problem. J. Oper. Res. Soc. 59(10):1373–1386.Crossref, Google Scholar
• Tseng FT, Stafford EF, Gupta JND (2004) An empirical analysis of integer programming formulations for the permutation flowshop. Omega 32(4):285–293.Crossref, Google Scholar
• Unsal O, Oguz C (2019) An exact algorithm for integrated planning of operations in dry bulk terminals. Transportation Res., Part E Logist. Transportation Rev. 126:103–121.Crossref, Google Scholar
• Valicka CG, Garcia D, Staid A, Watson J-P, Hackebeil G, Rathinam S, Ntaimo L (2019) Mixed-integer programming models for optimal constellation scheduling given cloud cover uncertainty. Eur. J. Oper. Res. 275(2):431–445.Crossref, Google Scholar
• Vallada E, Ruiz R, Framinan JM (2015) New hard benchmark for flowshop scheduling problems minimising makespan. European J. Oper. Res. 240(3):666–677.Crossref, Google Scholar
• Vallada E, Ruiz R, Minella G (2008) Minimising total tardiness in the m-machine flowshop problem: A review and evaluation of heuristics and metaheuristics. Comput. Oper. Res. 35(4):1350–1373.Crossref, Google Scholar
• Vilim P, Laborie P, Shaw P (2015) Failure-directed search for constraint-based scheduling. Michel L, ed. Integration of AI and OR Techniques in Constraint Programming (Springer, Berlin), 437–453.Google Scholar
• Wagner HM (1959) An integer linear-programming model for machine scheduling. Naval Res. Logist. 6(2):131–140.Crossref, Google Scholar
• Wang T, Meskens N, Duvivier D (2015) Scheduling operating theatres: Mixed integer programming vs. constraint programming. Eur. J. Oper. Res. 247(2):401–413.Crossref, Google Scholar
• Wilson JM (1989) Alternative formulations of a flowshop scheduling problem. J. Oper. Res. Soc. 40(4):395–399.Crossref, Google Scholar
• Yamada T, Nakano R (1992) A genetic algorithm applicable to large-scale job-shop instances. Männer R, Manderick B, eds. Parallel Instance Solving from Nature 2 (Elsevier, Amsterdam), 281–290.Google Scholar
• Younespour M, Atighehchian A, Kianfar K, Esfahani ET (2019) Using mixed integer programming and constraint programming for operating rooms scheduling with modified block strategy. Oper. Res. Health Care 23:100220.Crossref, Google Scholar