Job shop scheduling with setup times and maximal time-lags: A simple constraint programming approach

Abstract. In previous work we introduced a simple constraint model that com-bined generic AI strategies and techniques (weighted degree heuristic, geometric restarts, nogood learning from restarts) with naive propagation for job shop and open shop scheduling problems. Here, we extend our model to handle two vari-ants of the job shop scheduling problem: job shop problems with setup times; and job shop problems with maximal time lags. We also make some important addi-tions to our original model, including a solution guidance component for search. We show empirically that our new models often outperform the state of the art techniques on a number of known benchmarks for these two variants, finding a number of new best solutions and proving optimality for the first time on some problems. We provide some insight into the performance of our approach through analysis of the constraint weighting procedure.