AddNoOverlap for Single-Machine Scheduling

A single-machine scheduling problem has $n$ tasks competing for one resource that can process at most one task at a time. In constraint programming we model each task $i$ as an interval variable with start $s_i$, processing time $p_i$, and end $e_i = s_i + p_i$.

The constraint

$$\text{AddNoOverlap}(I_1, I_2, \dots, I_n)$$

forces every pair of intervals to be disjoint. For all $i \ne j$, the solver requires

$$e_i \le s_j \quad \text{or} \quad e_j \le s_i.$$

Geometrically, the intervals lie on a single time axis and may touch but never overlap.

Illustration. Take two tasks with $p_1 = 3$ and $p_2 = 2$. The assignment $s_1 = 0,\, s_2 = 3$ produces $I_1 = [0,3)$ and $I_2 = [3,5)$, and $e_1 = 3 \le s_2 = 3$ — accepted. The assignment $s_1 = 0,\, s_2 = 2$ produces $I_2 = [2,4)$, which overlaps $I_1$ on $[2,3)$ — rejected by AddNoOverlap.