A Permutation-Based Approach for Solving the Job-Shop Problem

In this paper, we deal with the famous job-shop scheduling problem, which has been being a constant subject of study for many years due to its high computational complexity (NP-hard in the strong sense). We present a permutation-based scheme for solving the problem, which in the abstraction level differs from the classical one of Jacques Carlier and Éric Pinson. In particular, we specify the differences both in the fashion of stating the constraints (the use of the generalized sorting constraint) and in the search strategy (splitting intervals of task orders). We will first give a constraint program for solving the problem, which involves only primitive constraints and which is clean and simple to understand. We then study some special techniques based on testing variable bounds that allow us to solve two hard instances 1a21 and 1a38. These two instances have been open problems recommended in a paper of David Applegate and William Cook in 1991.