Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search

We introduce a simple technique for disjunctive machine scheduling problems and show that this method can match or even outperform state-of-the-art algorithms on a number of problem types. Our approach combines a number of generic search techniques such as restarts, adaptive heuristics, and solution-guided branching on a simple model based on a decomposition of disjunctive constraints and on the reification of these disjuncts.

This paper describes the method and its application to variants of the job shop scheduling problem (JSP). We show that our method can easily be adapted to handle additional side constraints and different objective functions, often outperforming the state-of-the-art and closing a number of open problems. Moreover, we perform in-depth analysis of the various factors that make this approach efficient. We show that, while most of the factors give moderate benefits, the variable and value ordering components are key.