.png){kind=icon}
.png){kind=icon}
Return
A constraint programming-based decomposition procedure for shop scheduling problems
.png){kind=icon}
PRE
AI
DOI：10.1080/00207543.2026.2719849.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we propose a two-phase constraint programming (CP) based algorithm to obtain high-quality lower and upper bounds for classical scheduling problems under the makespan minimisation criterion. The method relies on a resource-constrained project scheduling problem (RCPSP) formulation that incorporates a decomposition approach and a warm-start mechanism exploiting the problem structure to derive competitive bounds. We evaluate our approach on 280 instances of the non-permutation flow shop scheduling problem (NPFSSP) and the job shop scheduling problem (JSSP), comprising 120 and 160 instances, respectively. A comprehensive computational analysis shows that the proposed decomposition approach (DA) is highly competitive in terms of optimality gap and relative percentage deviation with respect to both the lower and upper bounds, outperforming a direct solution (DS) approach commonly used in industrial practice. DA consistently dominates DS across most instance subsets, both in average performance and in variability. We further validate our approach on 20 real-world industrial instances featuring non-rectangular job structures, job recirculation, and unbalanced machine workloads, reaching the optimal makespan on all instances in an average of 251 s. By obtaining highly competitive bounds, our proposed decomposition procedure increases managerial confidence when committing to due dates, allocating workloads, or evaluating whether additional capacity is required.
Keywords:
Scheduling
constraint programming
job shop
flow shop
warm-start
CP Optimizer
ADVANCED PLANNING AND SCHEDULING SYSTEMS
FLOW SHOP SCHEDULING
JOB SHOP SCHEDULING
Journal
IF:
7.3
Papers:
1.1W
Citations:
3.7W
Organization
View more organizations