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

This article focuses on a comprehensive computational evaluation comparing constraint programming (CP) models, specifically IBM’s CP Optimizer 20.1, with mixed-integer programming (MIP) models solved by CPLEX 20.1 and Gurobi 9.1.2 across twelve diverse shop scheduling problems. These problems range from pure sequencing (e.g., flow shop, open shop) to joint assignment-sequencing (e.g., hybrid flow shop) and pure assignment problems (e.g., parallel machine scheduling). The study uses over 6,600 benchmark instances and measures performance via feasibility rates, optimality gaps, and relative percentage deviations (RPD) against best-known solutions. Results indicate that CP Optimizer 20.1 generally outperforms MIP solvers in feasibility, optimality gap, and solution quality for all but pure assignment problems, where MIP models, particularly solved by CPLEX, perform better. The study also highlights that CP models are robust to increases in job numbers but sensitive to the number of machines and problem characteristics, and that recent advances in CP solvers now provide bounds and optimality guarantees, making CP a viable and often superior alternative to traditional MIP approaches for complex scheduling problems.