Job Shop Scheduling in CP-SAT

Model the classical job shop scheduling problem in CP-SAT: create one interval variable per task, enforce in-job precedence with start/end inequalities, prevent machine conflicts with AddNoOverlap, and minimize the makespan with AddMaxEquality.

Step 1 of 157%

Tutorial

The Job Shop Problem and Interval Variables

A job shop scheduling problem consists of:

$n$ jobs, each an ordered sequence of tasks;
$m$ machines;
a fixed assignment of every task to one specific machine for an integer duration.

A valid schedule must satisfy two rules:

Precedence. Within a job, task $k+1$ cannot start before task $k$ ends.
No overlap. Each machine processes at most one task at a time.

The standard objective is to minimize the makespan — the time at which all jobs are complete.

In CP-SAT, every task becomes an interval variable with three parts: a start, a fixed duration, and an end (equal to $\text{start}+\text{duration}$ ). We create it with

\text{interval} = \text{NewIntervalVar}(\text{start},\ \text{duration},\ \text{end}).

The integer variables start and end are given the domain $[0, H]$ , where $H$ is a horizon — any safe upper bound on completion time. The standard, always-valid choice is the sum of all task durations:

H = \sum\limits_{j,\,k} d_{j,k}.

For example, the instance with Job 0 = $[(M_0,3),(M_1,2)]$ and Job 1 = $[(M_1,4),(M_0,1)]$ has $4$ tasks, so the model needs $4$ interval variables, and we may take $H = 3+2+4+1 = 10$ .