Mixed-integer versus Constraint Programming Solvers
An Extensive Comparison with the Job Shop Scheduling Problem
DOI:
https://doi.org/10.5540/03.2026.012.01.0308Keywords:
Production Sequencing, Combinatorial Optimization, OR-Tools, HiGS, Job ShopAbstract
This paper compares free/open-source and commercial solvers of mixed-integer programming (MILP) and constraint programming (CP) in the classic job shop scheduling problem (JSSP) with makespan and total flowtime minimization. We implemented a MILP model and solved it with CPLEX, Gurobi, and HIGS solvers, and we also implemented and solved CP models with IBM CP, Hexaly, and OR-Tools solvers. We conducted computational experiments using 80 well-known Taillard instance sets. The extensive computational experience shows that the MILP model is promising for solving small-sized instances, and the CP model got the best average relative deviation and superior performance in large-sized instances. The solver IBM CP got the best average results.
Downloads
References
L. R. de Abreu, K. A. G. Araújo, B. A. de Prata, M. S. Nagano, and J. V. Moccellin. “A new variable neighbourhood search with a constraint programming search strategy for the open shop scheduling problem with operation repetitions”. In: Engineering Optimization 54.9 (2022), pp. 1563–1582. doi: 10.1080/0305215X.2021.1957101.
L. R. Abreu, B. A. Prata, M. S. Nagano, and J. M. Framinan. “A constraint programming-based iterated greedy algorithm for the open shop with sequence-dependent processing times and makespan minimization”. In: Computers & Operations Research 160 (2023). doi: 10.1016/j.cor.2023.106386.
W. Ku and J. C. Beck. “Mixed integer programming models for job shop scheduling: A computational analysis”. In: Computers & Operations Research 73 (2016), pp. 165–173. doi: 10.1016/j.cor.2016.04.006.
P. Laborie, J. Rogerie, P. Shaw, and P. Vilím. “IBM ILOG CP optimizer for scheduling: 20+ years of scheduling with constraints at IBM/ILOG”. In: Constraints 23 (2018), pp. 210–250.
A. S. Manne. “On the job-shop scheduling problem”. In: Operations research 8.2 (1960), pp. 219–223.
D. Müller, M. G. Müller, D. Kress, and E. Pesch. “An algorithm selection approach for the flexible job shop scheduling problem: Choosing constraint programming solvers through machine learning”. In: European Journal of Operational Research 302.3 (2022), pp. 874–891. doi: 10.1016/j.ejor.2022.01.034.
B. Naderi, R. Ruiz, and V. Roshanaei. “Mixed-integer programming vs. constraint programming for shop scheduling problems: new results and outlook”. In: INFORMS Journal on Computing 35.4 (2023), pp. 817–843. doi: 10.1287/ijoc.2023.1287.
F. B. Ozsoydan. “Reinforcement learning enhanced swarm intelligence and trajectory-based algorithms for parallel machine scheduling problems”. In: Computers & Industrial Engineering (2025), p. 110948.
B. A. Prata, L. R. Abreu, and M. S. Nagano. “Applications of constraint programming in production scheduling problems: A descriptive bibliometric analysis”. In: Results in Control and Optimization 14 (2024), p. 100350. doi: 10.1016/j.rico.2023.100350.
E. Taillard. “Benchmarks for basic scheduling problems”. In: European Journal of Operational Research 64.2 (1993), pp. 278–285.
