A constraint programming-based decomposition procedure for shop scheduling problems

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.