Computing smallest Cartesian products of intervals: application to the job-shop scheduling problem

(1) We give the syntax and semantics of a set of constraints that are essentially conjunctions of primitive constraints with possible existential quantifications. In particular, we introduce some global primitive constraints which bring us important gains both in saving memory and in enforcing pruning power for solving combinatorial problems.
(2) We describe the algorithms of resolution and optimization by a set of rewrite rules. These rules notably narrow and split the intervals of values assigned to variables.
(3) Finally we study in detail the primitive constraint of distinct integers that will be used for solving other constraints like the sorting constraint which states that an n-tuple of integers is obtained by sorting another n-tuple of integers.

The practical part of our work is devoted to applications of the constraint language presented in the theoretical part. (1) We solve a set of
problems relatively simple that are usually used as benchmark problems in the constraint programming literature. In particular, we solve the problem of 16 queens for which we can compute the number of solutions and the knight problem for which we obtain the first solution in 3 seconds on a Pentium 90.
(2) 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 Carlier and Pinson. In particular, we specify the differences both in the fashion of stating the constraints (the use of the sorting constraint) and in the heuristic of choosing variables to instantiate (splitting of intervals of task orders).
In addition, we study some special techniques like the bound trimming technique which allow us to solve two hard instances la21 and la38. These two instances have been open problems in a paper of Applegate and Cook.