A constraint programming-based decomposition procedure for shop scheduling problems

doi:10.1080/00207543.2026.2719849

Return

A constraint programming-based decomposition procedure for shop scheduling problems

2026-08-24

PRE

Francisco Yuraszeck *

Gonzalo Mejía

Daniel Alejandro Rossit

Armin Lüer‐Villagra

DOI：10.1080/00207543.2026.2719849

Original

Original request for help

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