Industrial-size job shop scheduling with constraint programming

Giacomo Da Col and Erich C. Teppan

Operations Research Perspectives, 2022, vol. 9, issue C

Abstract: The job shop scheduling problem is one of the most studied optimization problems to this day and it becomes more and more important in the light of the fourth industrial revolution (Industry 4.0) that aims at fully automated production processes. For a long time exact methods like constraint programming had problems to solve real large-scale problem instances and methods of choice were to be found in the area of (meta-) heuristics. However, developments during the last decade improved the performance of state-of-the-art constraint solvers dramatically, to the point that they can be applied also on large-scale instances. The presented work’s main target is to elaborate the performance of state-of-the-art constraint solvers with respect to industrial-size job shop scheduling problem instances. To this end, we analyze and compare the performance of two cutting-edge constraint solvers: OR-Tools, an open-source solver developed by Google and recurrent winner of the MiniZinc Challenge, and CP Optimizer, a proprietary constraint solver from IBM targeted at industrial optimization problems. In order to reflect real-world industrial scenarios with heavy workloads like found in the semi-conductor domain, we use novel benchmarks that comprise up to one million operations to be scheduled on up to one thousand machines. The comparison is based on the best makespan (i.e. completion time) achieved and the time required to solve the problem instances. We test the solvers on single-core and quad-core configurations.

Keywords: Large scale optimization; Job shop scheduling problem; Constraint programming; CP Optimizer; OR-Tools (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S2214716022000215
Full text for ScienceDirect subscribers only

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:eee:oprepe:v:9:y:2022:i:c:s2214716022000215

DOI: 10.1016/j.orp.2022.100249

Access Statistics for this article

Operations Research Perspectives is currently edited by Rubén Ruiz Garcia

More articles in Operations Research Perspectives from Elsevier
Bibliographic data for series maintained by Catherine Liu ().