A note on “A constraint programming-based lower bounding procedure for the job shop scheduling problem”

Abstract

In Yuraszeck et al. (2025), we recently proposed a constraint programming (CP) lower-bounding procedure for the minimal makespan job shop scheduling problem (JSSP). This approach consisted of two phases: in the first phase, a relaxation of the original problem is solved, while in the second phase, this relaxation is iteratively tightened until a time limit is reached or no better bounds are found. In this paper, we introduce a third phase, that iteratively solves the subproblems left unaddressed in the second phase. Additionally, we evaluate the influence of warm-starting the algorithm on solution quality and computational time. We tested our updated procedure on 80 open JSSP instances, finding 14 new lower bounds with an average reduction in the optimality gap of 29.59% compared with the best-known bounds from the literature.