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

Bahman Naderi (), Rubén Ruiz () and Vahid Roshanaei ()
Additional contact information
Bahman Naderi: Department of Mechanical, Automotive, and Materials, Faculty of Engineering, University of Windsor, Windsor, Ontario N9B 3P4, Canada
Rubén Ruiz: Grupo de Sistemas de Optimización Aplicada, Universitat Politècnica de València, 46021 València, Spain
Vahid Roshanaei: Department of Operations Management & Statistics, Rotman School of Management, University of Toronto, Toronto, Ontario M5S 3E6, Canada

INFORMS Journal on Computing, 2023, vol. 35, issue 4, 817-843

Abstract: Constraint programming (CP) has been recently in the spotlight after new CP-based procedures have been incorporated into state-of-the-art solvers, most notably the CP Optimizer from IBM. Classical CP solvers were only capable of guaranteeing the optimality of a solution, but they could not provide bounds for the integer feasible solutions found if interrupted prematurely due to, say, time limits. New versions, however, provide bounds and optimality guarantees, effectively making CP a viable alternative to more traditional mixed-integer programming (MIP) models and solvers. We capitalize on these developments and conduct a computational evaluation of MIP and CP models on 12 select scheduling problems. 1 We carefully chose these 12 problems to represent a wide variety of scheduling problems that occur in different service and manufacturing settings. We also consider basic and well-studied simplified problems. These scheduling settings range from pure sequencing (e.g., flow shop and open shop) or joint assignment-sequencing (e.g., distributed flow shop and hybrid flow shop) to pure assignment (i.e., parallel machine) scheduling problems. We present MIP and CP models for each variant of these problems and evaluate their performance over 17 relevant and standard benchmarks that we identified in the literature. The computational campaign encompasses almost 6,623 experiments and evaluates the MIP and CP models along five dimensions of problem characteristics, objective function, decision variables, input parameters, and quality of bounds. We establish the areas in which each one of these models performs well and recognize their conceivable reasons. The obtained results indicate that CP sets new limits concerning the maximum problem size that can be solved using off-the-shelf exact techniques.

Keywords: shop scheduling; flow shop; job shop; flexible job shop; open shop; parallel machines; benchmarks; constraint programming; mixed integer programming (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.1287 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:4:p:817-843

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().