Introduction

This book collects notes and examples of scheduling models built with OR-Tools CP-SAT. The focus is on job-shop style problems: sequencing tasks on machines, handling changeovers, respecting breaks and shifts, modeling resources, and grouping tasks into campaigns.

The book is split into two parts.

Concepts walks through the core modeling ideas once. Read these first if CP-SAT or constraint programming is new to you.
Examples indexes the Python files in the scheduling/ folder and links each one back to the concepts it demonstrates. Examples are numbered and build on each other, so reading them in order is usually easiest.

All code lives in the scheduling/ directory of the repo. Open a file in your editor while reading the corresponding chapter to see the full model.

A minimal CP-SAT template

Almost every example follows the same five-step shape.

from ortools.sat.python import cp_model

# 1. Data
# ... sets, durations, changeover table, etc.

# 2. Decision variables
model = cp_model.CpModel()
# ... start/end/interval/bool vars

# 3. Objective
make_span = model.new_int_var(0, max_time, "make_span")
model.add_max_equality(make_span, [ends[t] for t in tasks])
model.minimize(make_span)

# 4. Constraints
# ... precedence, resources, circuits, ...

# 5. Solve and post-process
solver = cp_model.CpSolver()
status = solver.solve(model)

The rest of the book explains what goes into step 4.

CP-SAT basics

CP-SAT is a constraint-programming solver with integer and boolean variables. Before looking at scheduling, it helps to be comfortable with a few primitives.

Variables

x = model.new_int_var(0, 100, 'x')      # integer in [0, 100]
b = model.new_bool_var('b')             # boolean (integer in {0, 1})

Linear constraints

model.add(x + y == 10)
model.add(x <= y)
model.add(sum(bs) == 1)               # exactly-one on a list of bools
model.add_exactly_one(bs)               # same, more idiomatic

Boolean combinations

model.add_bool_or([a, b])               # a or b
model.add_bool_and([a, b])              # a and b
model.add_bool_xor([a, b])              # exactly one of a, b

Reification with `only_enforce_if`

A constraint can be conditioned on a boolean literal. The constraint is only active when the literal is true.

model.add(x >= 5).only_enforce_if(b)
model.add(x < 5).only_enforce_if(~b)

Chaining two only_enforce_if calls gives an "and" of conditions:

model.add(y == 1).only_enforce_if(b1).only_enforce_if(b2)  # y == 1 iff b1 and b2

For "or", you normally introduce intermediate booleans or use add_bool_or.

`add_min_equality`, `add_max_equality`, `add_multiplication_equality`

These express z = min(xs), z = max(xs), z = x * y (or the product of a list). add_max_equality is how makespan is usually encoded:

model.add_max_equality(make_span, [ends[t] for t in tasks])

Domains

For "x belongs to a non-contiguous set of values" use add_linear_expression_in_domain:

domain = cp_model.Domain.from_intervals([[0, 4], [11, 100]])
model.add_linear_expression_in_domain(x, domain)

See example_00_unit_tests.py for a collection of small snippets exercising each of these.

Solve and read back

solver = cp_model.CpSolver()
status = solver.solve(model)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print(solver.value(x))

Interval variables

An interval variable bundles three integer variables - start, size, end - with the implicit constraint start + size == end. CP-SAT uses intervals to reason efficiently about scheduling: add_no_overlap and add_cumulative both expect intervals.

Three flavors

Regular interval

iv = model.new_interval_var(start, size, end, name="t1")

Replaces a manual model.add(end - start == size).

Optional interval

An interval that is only scheduled when a presence boolean is true. Essential when a task may or may not be assigned to a given machine.

iv = model.new_optional_interval_var(start, size, end, is_present, name="t1_on_m1")

If is_present is false, the interval disappears from add_no_overlap / add_cumulative reasoning.

Fixed-size interval

Convenient for breaks, shift boundaries, and anything with a known position.

br = model.new_fixed_size_interval_var(start=2, size=1, name="break")

Typical use

intervals = {
    (m, t): model.new_optional_interval_var(
        starts[m, t],
        processing_time[product_of(t)],
        ends[m, t],
        presence[m, t],
        f"t{t}_on_m{m}",
    )
    for t in tasks for m in machines
}

for m in machines:
    model.add_no_overlap([intervals[m, t] for t in tasks])

Examples that introduce intervals: example_05_seq_with_intervals.py (first use), example_03_seq_scale_Mathieu.py (dramatic speed-up vs. manual duration constraints).

Circuit and sequencing

To sequence tasks on a machine, you need both the order and the time constraints that follow from it. CP-SAT's add_circuit is the standard tool.

What `add_circuit` does

add_circuit(arcs) takes a list of triples [i, j, literal]. It asserts that the selected arcs (where literal == 1) form a single Hamiltonian circuit over the referenced nodes. Self-arcs [i, i, literal] mean node i is skipped when literal is true.

arcs = []
for t1 in tasks:
    arcs.append([0, t1, start_literal(t1)])   # dummy -> t1 (first)
    arcs.append([t1, 0, end_literal(t1)])     # t1 -> dummy (last)
    arcs.append([t1, t1, ~presence[t1]]) # skip t1 if absent
    for t2 in tasks:
        if t1 == t2:
            continue
        arcs.append([t1, t2, seq[t1, t2]])

model.add_circuit(arcs)

Node 0 (or -1) is typically a dummy "first/last" node.

Linking the circuit to time

add_circuit only picks the order. You also need: if t1 -> t2 is chosen, then end[t1] + gap <= start[t2]. This is a reified constraint:

model.add(end[t1] + gap <= start[t2]).only_enforce_if(seq[t1, t2])

gap is usually changeover_time (see Changeover) or 0.

Multi-machine

With multiple machines, build one circuit per machine and gate absent tasks with self-loops:

for m in machines:
    arcs = []
    for t in tasks:
        arcs.append([t, t, ~presence[m, t]])
        for t2 in tasks:
            if t != t2:
                arcs.append([t, t2, seq[m, t, t2]])
    model.add_circuit(arcs)

add_exactly_one(presence[m, t] for m in machines) ensures each task ends up on exactly one machine.

Examples: example_01_simple_sequence.py (single machine), example_03_seq_multi_stations.py (multi-machine).

Changeover

A changeover is the time needed to switch a machine from producing one product to another. There are three common ways to model it.

1. In the objective

Charge a cost for each seq[t1, t2] whose products differ. The cost does not appear in the schedule itself, only the cost minimised.

total_co = sum(seq[t1, t2] * changeover_cost[t1, t2] for ...)
model.minimize(make_span + total_co)

Simple, but time and cost are decoupled: the schedule may not leave physical room for the changeover.

Example: example_01_simple_sequence.py.

2. In the precedence constraint

Include the changeover in the gap between tasks:

gap = changeover_time if products_differ(t1, t2) else 0
model.add(end[t1] + gap <= start[t2]).only_enforce_if(seq[t1, t2])

Now time and cost agree: a changeover actually pushes the next task later.

Example: example_04_seq_with_changeover_in_constraint.py.

3. As a first-class event

Create an optional interval for every (t1, t2) that represents the changeover itself. When t1 -> t2 is chosen, the interval is present, sits between the two tasks, and has the right duration.

co_iv = model.new_optional_interval_var(co_start, co_duration, co_end, co_present, ...)
model.add(end[t1] <= co_start).only_enforce_if(seq[t1, t2])
model.add(co_end <= start[t2]).only_enforce_if(seq[t1, t2])
model.add(co_present == 1).only_enforce_if(seq[t1, t2])

This lets you add the changeover interval to add_cumulative (it consumes operator time) or apply cleaning-resource constraints to it.

Example: example_08_changeover_as_event.py.

Starting product

A machine usually begins with some product already loaded. Model it with a dummy task 0 whose "product" is the starting product; the cost from dummy to the first real task is zero if they match, else the usual changeover.

Example: example_02_seq_lock_starting_product.py.

Breaks

A break is a time window during which a machine or operator is unavailable. Three techniques cover most cases.

1. Break as a fixed interval in `add_cumulative`

For each break, build a new_fixed_size_interval_var and add it alongside task intervals with the full demand. Tasks are pushed around the break.

break_intervals = [
    model.new_fixed_size_interval_var(start=s, size=e - s, name="break")
    for (s, e) in breaks
]
all_intervals = task_intervals + break_intervals
demands = [1] * len(task_intervals) + [1] * len(break_intervals)
model.add_cumulative(all_intervals, demands, capacity=1)

Example: example_07_break_without_changeover.py.

2. Task duration stretched by overlapping breaks

When a task may run through a break and the break simply extends its total time on the machine, use per-time-slot booleans that indicate whether the task uses slot i, then add is_break[i] for each covered slot.

uses[t, i] = starts_before_i AND ends_after_i
duration[t] = base + sum(is_break[i] * uses[t, i] for i)
interval[t] = new_interval_var(start, duration, end, ...)

Example: example_14_task_delaying_break.py.

3. Break-aware start domains

If the break pattern is periodic, restrict task starts to the valid slots with add_linear_expression_in_domain. Much faster than per-slot booleans.

domain_no_break = cp_model.Domain.from_values([...])
model.add_linear_expression_in_domain(start[t], domain_no_break)

Example: example_29_linear_domain_for_breaks.py, example_33_conditional_duration_linear_domain.py.

Automatic jobs

Some "automatic" tasks don't consume the operator while running (think: a machine runs itself after a short manual setup). Model only the setup portion inside the cumulative, using a 1-unit interval at the task's start.

Example: example_12_an_automatic_job.py, example_13_automatic_jobs.py.

Shifts

A shift is a working window. Tasks must fit inside one shift (or, depending on policy, be split / disallowed from crossing shifts).

Synthetic shift breaks

Insert a tiny "fake break" interval at each shift boundary and forbid any task from overlapping it with add_no_overlap. This prevents shift-crossing without enumerating shift assignments.

for (s, e) in synthetic_shift_breaks:
    br = model.new_fixed_size_interval_var(start=s, size=e - s, name="shift_edge")
    for t in tasks:
        model.add_no_overlap([task_interval[t], br])

Example: example_16_shift_crossing_fake_time_unit.py.

Explicit shift assignment

Alternatively, give every task a one-hot presence[shift, task] and enforce the shift window when present:

for t in tasks:
    model.add_exactly_one(presence[s, t] for s in shifts)
    for s in shifts:
        model.add(start[t] >= shift_start[s]).only_enforce_if(presence[s, t])
        model.add(end[t]   <= shift_end[s]  ).only_enforce_if(presence[s, t])

More variables, but the assignment is explicit and easy to extend (e.g. to per-shift capacity).

Example: example_17_shift_crossing_mathieu.py.

Resources and cumulative

add_no_overlap says "at most one interval at a time". add_cumulative is the generalisation: each interval consumes some amount of a shared resource, and the total consumption must not exceed a capacity.

No-overlap

model.add_no_overlap(intervals)

Used per machine (one task at a time) and per stage (one job at a time in a flow-shop style).

Cumulative

model.add_cumulative(intervals, demands, capacity)

demands[i] is the amount of resource taken by intervals[i] while it runs. Typical uses:

Shared operator across machines. If two machines need the same operator, cumulative over all their task intervals with demand 1 and capacity 1 forbids parallel runs. Example: example_06_seq_with_intervals_resource.py.
Breaks. Treat a break as an interval that fully occupies the resource. Example: example_07_break_without_changeover.py.
Automatic jobs. Only the setup portion consumes the operator, modeled as a size-1 interval at each task's start.

Resource modes

Some tasks can run in different modes with different durations and headcounts. Encode the choice with a one-hot bool per mode and derive the actual processing time from it:

for t in tasks:
    model.add_exactly_one([mode[t, k] for k in modes])
    model.add(
        proc_time[t] == sum(processing_time[product[t], k] * mode[t, k] for k in modes)
    )

Example: example_10_people_mode.py.

Headcount tracking

If the per-task resource depends on whether the task overlaps a break (or some other condition), plain add_cumulative may be insufficient. Build an explicit per-timestep resource variable and link it to task-start presence booleans. Three methods are compared in example_34_headcount_tracking.py.

Multi-stage jobs

A job can consist of several stages that must run in order. Each stage is a task with its own start/end; the job start is the earliest task start and the job end is the latest task end.

Job - stage - task structure

tasks = {(job, stage) for job in jobs for stage in stages}

for job in jobs:
    model.add_min_equality(job_start[job], [start[job, s] for s in stages])
    model.add_max_equality(job_end[job],   [end  [job, s] for s in stages])

    # stage precedence
    for s in sorted(stages)[:-1]:
        model.add(end[job, s] <= start[job, s + 1])

Example: example_21_stages_one_job.py.

Stage-level no-overlap

If each stage has a single shared machine, forbid two jobs from sitting on the same stage simultaneously:

for s in stages:
    model.add_no_overlap([intervals[job, s] for job in jobs])

Examples: example_22_stages_two_jobs.py, example_23_multistage_two_jobs_co.py.

Campaigning

A campaign is a run of same-product tasks on a machine between two changeovers. Typical rules:

tasks within a campaign are the same product and pay no changeover cost,
a campaign has a maximum size (e.g. at most N tasks),
switching products or hitting the cap triggers a changeover.

Approach 1: campaigns as entities

Create a set of potential campaigns, each with start/end/duration/presence, and variables linking tasks to campaigns. Sequence campaigns (not tasks) using add_circuit. The campaign-level changeover cost sits in the gap between campaigns.

Pros: close to the business view. Cons: more variables, scales worse.

Example: example_09_max_number_of_continuous_tasks.py.

Approach 2: cumulative rank per task

Keep tasks as the atomic unit and attach a rank variable cumul[t] in [0, campaign_size - 1]. On each t1 -> t2 arc:

if the campaign continues, cumul[t2] = cumul[t1] + 1,
if a changeover happens, cumul[t2] = 0 and end[t1] + changeover <= start[t2].

A reach_max[t] boolean fires when cumul[t] == campaign_size - 1, forcing a reset and changeover. add_max_equality(max_value, [0, cumul[t1] + 1 - reach_end[t1] * campaign_size]) is a useful trick to compute the next rank under an only_enforce_if.

Pros: fewer variables, scales better. Cons: trickier to explain.

Examples: example_24_campaigning_with_cumul.py (base), example_27_campaigning_products.py (multi-product), example_28_campaigning_products_machines.py (multi-machine).

Locking the task order

When tasks have deadlines that align with their index, locking start[t-1] <= start[t] (or the stricter end[t-1] <= start[t]) is a cheap heuristic that often gives a 10x+ solve-time improvement. See example_25_campaigning_with_locked_seq.py and the two example_26_campaigning_locked_seq_improved*.py variants.

Flexible campaign ends

If the model should be free to end a campaign early (not just at the cap), drop the "force reach_end when cumul hits max" implication and let the solver choose. This usually gives better objective values at a small solve- time cost. See the two example_26_*_improved*.py files for the comparison.

Solver techniques

Beyond modeling, CP-SAT exposes a few knobs that help on hard instances.

Decision strategies

Tell the solver which variables to branch on first, and which value to try first. Often needed when a symmetric model returns a "correct but ugly" schedule.

model.add_decision_strategy(
    starts.values(),
    cp_model.CHOOSE_FIRST,
    cp_model.SELECT_MIN_VALUE,
)

Example: example_07_break_without_changeover.py applies two strategies (one on starts, one on sequence literals) to get a canonical output.

Parallel workers

solver.parameters.num_search_workers = 8

Uses N worker threads. Examples example_03_seq_scale*.py benchmark the resulting speedup.

Warm-starting with hints

You can seed the search with values for any subset of variables:

model.proto().solution_hint.vars.append(var_index)
model.proto().solution_hint.values.append(value)

Or clear and re-set them between solves:

model.clear_hints()
add_hints(model, previous_solution)

This is the basis of phase solving: build the full model once, then run it repeatedly with an increasing max_time, feeding each phase's solution in as hints to the next. Example: example_32_solving_by_phases.py.

Reading back values

status = solver.solve(model)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print(solver.value(var))
    print(solver.objective_value())

MODEL_INVALID almost always means a constraint references a variable that was never bound to the right model instance, or an only_enforce_if was attached to something that is not a literal.

Examples overview

Each example in this section corresponds to one Python file under scheduling/. Chapters are kept short: a brief description, the concepts it demonstrates (linked back to the Concepts section), and the source file inlined at the bottom.

Examples are grouped by topic in the sidebar:

Basics - CP-SAT primitives and small modeling tricks.
Sequencing - ordering tasks on one or more machines.
Changeover and intervals - different ways to model switches between products and the move from manual durations to interval variables.
Breaks - unavailable time windows, including breaks that extend a task's duration and automatic jobs that only need an operator for setup.
Shifts - preventing tasks from crossing shift boundaries.
Multi-stage jobs - jobs with ordered stages and per-stage capacity.
Resources - flexible resource/headcount modes and time-varying demand tracking.
Campaigning - grouping same-product tasks between changeovers, with multiple modelling approaches.
Solver techniques - warm-starting CP-SAT across phases with hints.

A few files (example_11, example_18, example_19, example_30) are empty placeholders kept for numbering; their chapters only note what they would have covered.

Unit tests

Source: scheduling/example_00_unit_tests.py

CP for Job Shop Problems