Solving the no-wait job shop problem: An ILP and CP approach

The no-wait job shop problem is a variant of the traditional job shop scheduling problem, where the time between operations of the same job is fixed. The only variables left are the start times of each job. We show that all constraints can be expressed as a set of no-overlap constraints for each pair of jobs. This deceivingly simple-looking problem turns out to be quite hard to solve within a reasonable amount of time. In this paper, we present exact solution methods using ILP (Integer Linear Programming) and a combination of binary search with CP (Constraint Programming) to find an optimal makespan. We derive two simple but effective propagators. We performed extensive experiments using different ILP formulations, lower bounds, constraint propagation strategies and branching strategies. We show that the edge-finding and not-first, not-last propagators used in solving the traditional job shop problem are less effective in the presence of no-wait constraints. For medium-sized problem instances of 10 jobs the performance of our best CP strategy is comparable to that of the best-known branch-and-bound algorithm for the no-wait job shop problem. Our algorithm scales better with the number of machines and number of operations per job and the branch-and-bound methods scales better with the number of jobs.