Practical Tutorial · OR-Tools CP-SAT · Python

Scheduling with
CP-SAT Solvers

A ground-up guide to modelling and solving scheduling problems in Python — from a single machine to resource-constrained projects, with working code throughout.

google-ortools Python 3.8+ Interval Variables No-Overlap Cumulative Job Shop RCPSP

Scheduling
Series

Part 1 The World of Scheduling Problems

Part 2 Scheduling with CP-SAT

Part 3 When Scheduling Meets Reality

Part 4 Scheduling in the Wild

Getting Started

Setup & Install

One package. No extra dependencies. Every example on this page runs with just this.

Install

pip install ortools

Standard imports — use these at the top of every script

from ortools.sat.python import cp_model

model  = cp_model.CpModel()   # the model you add variables and constraints to
solver = cp_model.CpSolver()  # the solver that searches for a solution

How CP-SAT works: You describe what a valid schedule looks like (variables + constraints) and what makes one schedule better than another (objective). The solver searches for a provably optimal solution — or the best it can find within a time limit.

Foundation

Three Core Primitives

Every scheduling model in CP-SAT is built from these three building blocks. Master them and any problem becomes a composition of these parts.

Primitive 1

Interval Variable

model.new_interval_var(start, duration, end, name)

An interval variable represents a task: it has a start time, a fixed duration, and an end time. The solver decides when the interval is placed on the timeline. The invariant end = start + duration is always enforced automatically.

horizon = 30  # the latest any job can finish (upper bound on schedule length)

# Three variables — the solver decides their values
start    = model.new_int_var(0, horizon, 'start')
end      = model.new_int_var(0, horizon, 'end')
duration = 8  # fixed — can also be a variable for flexible durations

# Interval variable ties them together: end = start + duration
interval = model.new_interval_var(start, duration, end, 'job_a')

Optional intervals — for problems where a job might not be scheduled (e.g., optional tasks, machine assignment): model.new_optional_interval_var(start, duration, end, is_present, name) where is_present is a boolean variable the solver can set to True or False.

Primitive 2

No-Overlap Constraint

model.add_no_overlap(intervals)

Ensures that no two intervals in the list overlap in time. This is the constraint that models a single machine — at most one job at a time. Give it a list of interval variables; the solver figures out the non-overlapping sequence.

# Build one interval per job
intervals = []
for i, duration in enumerate([6, 8, 5]):
    s  = model.new_int_var(0, horizon, f's{i}')
    e  = model.new_int_var(0, horizon, f'e{i}')
    iv = model.new_interval_var(s, duration, e, f'iv{i}')
    intervals.append(iv)

# Single constraint: no two jobs run simultaneously on the machine
model.add_no_overlap(intervals)

Primitive 3

Cumulative Constraint

model.add_cumulative(intervals, demands, capacity)

At every point in time, the total demand of all active intervals must not exceed the capacity. This models renewable resources — workers, machines, memory, bandwidth — where multiple tasks can run in parallel as long as they don't exceed the limit together.

tasks   = [{'duration': 6, 'demand': 2},
           {'duration': 6, 'demand': 2},
           {'duration': 6, 'demand': 3}]
capacity = 4

intervals = []
demands   = []
for i, t in enumerate(tasks):
    s  = model.new_int_var(0, horizon, f's{i}')
    e  = model.new_int_var(0, horizon, f'e{i}')
    iv = model.new_interval_var(s, t['duration'], e, f'iv{i}')
    intervals.append(iv)
    demands.append(t['demand'])

# At every time point: sum of active demands ≤ capacity
model.add_cumulative(intervals, demands, capacity)

Rule of thumb: Use add_no_overlap for machines (binary — a machine does one thing at a time). Use add_cumulative for resources (continuous — workers, units, bandwidth with a shared pool).

Problem Type 01

Single Machine Scheduling

The simplest environment — one machine, n jobs, each needing a slot. The right objective changes the optimal sequence entirely.

Makespan = when the last job finishes. Minimizing it packs all work as early as possible. For a single machine, any ordering gives the same makespan — sum of all durations. This objective matters more on parallel machines.

Complete example — single machine, minimize makespan

from ortools.sat.python import cp_model

model  = cp_model.CpModel()
solver = cp_model.CpSolver()

durations = [5, 8, 3, 6, 4]        # processing time for each job
horizon   = sum(durations)          # makespan can't exceed this

# ── Variables ──────────────────────────────────────────
starts    = [model.new_int_var(0, horizon, f's{i}') for i in range(len(durations))]
ends      = [model.new_int_var(0, horizon, f'e{i}') for i in range(len(durations))]
intervals = [
    model.new_interval_var(starts[i], durations[i], ends[i], f'iv{i}')
    for i in range(len(durations))
]

# ── Constraints ────────────────────────────────────────
model.add_no_overlap(intervals)     # one job at a time on the machine

# ── Objective ──────────────────────────────────────────
makespan = model.new_int_var(0, horizon, 'makespan')
model.add_max_equality(makespan, ends)   # makespan = max completion time
model.minimize(makespan)

# ── Solve ──────────────────────────────────────────────
status = solver.solve(model)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print(f'Makespan: {solver.value(makespan)}')
    for i in range(len(durations)):
        print(f'  Job {i}: [{solver.value(starts[i])}, {solver.value(ends[i])})')

CP-SAT Output Makespan = 26

Total completion time = sum of finish times across all jobs. Minimized by the SPT rule — Shortest Processing Time first. Scheduling short jobs early reduces wait for everyone downstream.

Swap just the objective — the rest of the model is identical

from ortools.sat.python import cp_model

model  = cp_model.CpModel()
solver = cp_model.CpSolver()

durations = [5, 8, 3, 6, 4]
horizon   = sum(durations)

starts    = [model.new_int_var(0, horizon, f's{i}') for i in range(len(durations))]
ends      = [model.new_int_var(0, horizon, f'e{i}') for i in range(len(durations))]
intervals = [
    model.new_interval_var(starts[i], durations[i], ends[i], f'iv{i}')
    for i in range(len(durations))
]
model.add_no_overlap(intervals)

# ── Objective: minimize total completion time ──────────
model.minimize(sum(ends))          # sum of all end times

status = solver.solve(model)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print(f'Total completion: {sum(solver.value(e) for e in ends)}')
    order = sorted(range(len(durations)), key=lambda i: solver.value(starts[i]))
    print('SPT order:', order)
    for i in order:
        print(f'  Job {i} (dur={durations[i]}): [{solver.value(starts[i])}, {solver.value(ends[i])})')

CP-SAT Output — SPT order Total completion = 66

SPT is provably optimal for minimizing total completion time on a single machine with no release dates. CP-SAT will discover this, but you can also enforce it directly to speed up large instances.

Tardiness of a job = max(0, completion_time − due_date). A job finished before its deadline has zero tardiness. Minimizing weighted tardiness (priority × lateness) is NP-hard — CP-SAT handles it exactly for moderate instance sizes.

Single machine — minimize total weighted tardiness

from ortools.sat.python import cp_model

model  = cp_model.CpModel()
solver = cp_model.CpSolver()

durations  = [5, 8, 3, 6, 4]
due_dates  = [7, 12, 5, 18, 10]    # deadline for each job
weights    = [3, 1, 2, 1, 2]       # priority / penalty weight
horizon    = sum(durations)

starts    = [model.new_int_var(0, horizon, f's{i}') for i in range(len(durations))]
ends      = [model.new_int_var(0, horizon, f'e{i}') for i in range(len(durations))]
intervals = [
    model.new_interval_var(starts[i], durations[i], ends[i], f'iv{i}')
    for i in range(len(durations))
]
model.add_no_overlap(intervals)

# ── Tardiness variables ────────────────────────────────
tardiness = []
for i in range(len(durations)):
    # tardiness[i] = max(0, end[i] - due_date[i])
    t = model.new_int_var(0, horizon, f'tard{i}')
    model.add_max_equality(t, [ends[i] - due_dates[i], 0])
    tardiness.append(weights[i] * t)

model.minimize(sum(tardiness))

status = solver.solve(model)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    for i in range(len(durations)):
        s, e = solver.value(starts[i]), solver.value(ends[i])
        tard = max(0, e - due_dates[i])
        print(f'  Job {i}: [{s}, {e})  due={due_dates[i]}  tardiness={tard}')

CP-SAT Output — due dates shown as markers Weighted tardiness minimized

Watch the horizon: Setting horizon = sum(durations) is safe but sometimes too loose. For tardiness problems, a tighter horizon (e.g., max(due_dates) + sum(durations)) helps the solver prune the search space faster.

Problem Type 02

Parallel Machine Scheduling

Multiple identical machines run simultaneously. Each job must be assigned to exactly one machine and scheduled without overlapping other jobs on that machine. This is NP-hard even with 2 machines.

Key idea: For each (job, machine) pair, create an optional interval variable. Enforce that exactly one machine is chosen per job. Then add a no-overlap constraint per machine over only the optional intervals assigned to it.

Parallel machines — minimize makespan

from ortools.sat.python import cp_model

model  = cp_model.CpModel()
solver = cp_model.CpSolver()

num_jobs     = 5
num_machines = 2
durations    = [8, 6, 5, 4, 3]
horizon      = sum(durations)

# For each job: one start, one end (shared across all machine alternatives)
starts = [model.new_int_var(0, horizon, f's{j}') for j in range(num_jobs)]
ends   = [model.new_int_var(0, horizon, f'e{j}') for j in range(num_jobs)]

# For each (job, machine): optional interval + presence boolean
machine_intervals = [[] for _ in range(num_machines)]
presences        = [[None] * num_machines for _ in range(num_jobs)]

for j in range(num_jobs):
    for m in range(num_machines):
        is_present = model.new_bool_var(f'p{j}_{m}')
        iv = model.new_optional_interval_var(
            starts[j], durations[j], ends[j], is_present, f'iv{j}_{m}'
        )
        machine_intervals[m].append(iv)
        presences[j][m] = is_present

    # Each job goes to exactly one machine
    model.add_exactly_one(presences[j])

# No two jobs overlap on the same machine
for m in range(num_machines):
    model.add_no_overlap(machine_intervals[m])

# Minimize makespan
makespan = model.new_int_var(0, horizon, 'makespan')
model.add_max_equality(makespan, ends)
model.minimize(makespan)

status = solver.solve(model)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print(f'Makespan: {solver.value(makespan)}')
    for j in range(num_jobs):
        m = next(m for m in range(num_machines) if solver.value(presences[j][m]))
        print(f'  Job {j}: machine={m}  [{solver.value(starts[j])}, {solver.value(ends[j])})')

CP-SAT Output — 2 machines Makespan = 13

Symmetry breaking: If machines are identical, add model.add(starts[0] <= starts[1]) for the first job across machine pairs. This cuts the search space roughly in half by eliminating mirror solutions.

Problem Type 03

Flow Shop Scheduling

Every job visits every machine in the same fixed order (e.g., cut → paint → assemble). Jobs cannot skip stages or change order. With 2 machines, Johnson's Algorithm solves it optimally in O(n log n). With 3+, it is NP-hard.

Create a grid of interval variables

One interval per (job, machine) pair. Each interval's duration is the processing time for that job on that machine.

No-overlap per machine column

For each machine, collect all job intervals on that machine and add a no-overlap constraint.

Precedence along each job row

For each job, stage k+1 must start after stage k finishes: starts[j][m+1] >= ends[j][m].

Flow shop — 3 jobs × 2 machines — minimize makespan

from ortools.sat.python import cp_model

model  = cp_model.CpModel()
solver = cp_model.CpSolver()

# proc[job][machine] = processing time
proc = [
    [3, 4],   # Job 0: 3 on M0, then 4 on M1
    [5, 2],   # Job 1: 5 on M0, then 2 on M1
    [2, 6],   # Job 2: 2 on M0, then 6 on M1
]
num_jobs     = len(proc)
num_machines = len(proc[0])
horizon      = sum(sum(row) for row in proc)

# ── Step 1: variables ──────────────────────────────────
starts    = [[None]*num_machines for _ in range(num_jobs)]
ends      = [[None]*num_machines for _ in range(num_jobs)]
intervals = [[None]*num_machines for _ in range(num_jobs)]

for j in range(num_jobs):
    for m in range(num_machines):
        s  = model.new_int_var(0, horizon, f's{j}_{m}')
        e  = model.new_int_var(0, horizon, f'e{j}_{m}')
        iv = model.new_interval_var(s, proc[j][m], e, f'iv{j}_{m}')
        starts[j][m] = s; ends[j][m] = e; intervals[j][m] = iv

# ── Step 2: no-overlap per machine ────────────────────
for m in range(num_machines):
    model.add_no_overlap([intervals[j][m] for j in range(num_jobs)])

# ── Step 3: precedence within each job ────────────────
for j in range(num_jobs):
    for m in range(num_machines - 1):
        model.add(starts[j][m + 1] >= ends[j][m])

# ── Objective ──────────────────────────────────────────
makespan = model.new_int_var(0, horizon, 'makespan')
model.add_max_equality(makespan, [ends[j][num_machines-1] for j in range(num_jobs)])
model.minimize(makespan)

status = solver.solve(model)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print(f'Makespan: {solver.value(makespan)}')
    for j in range(num_jobs):
        row = '  '.join(
            f'M{m}:[{solver.value(starts[j][m])},{solver.value(ends[j][m])})'
            for m in range(num_machines)
        )
        print(f'  Job {j}: {row}')

CP-SAT Output — 2 machines, 3 jobs Makespan = 14

Problem Type 04

Job Shop Scheduling

Each job has its own unique route through the machines. The most general and most studied model. NP-hard even with 2 machines and 3 jobs. This is the benchmark problem for metaheuristics — and CP-SAT handles it well for moderate sizes.

Difference from flow shop: In a flow shop, every job visits machines in the same order. In a job shop, each job has its own routing — Job 0 might go M0→M1→M2 while Job 1 goes M2→M0→M1.

Job shop — 3 jobs × 3 machines — minimize makespan

from ortools.sat.python import cp_model

model  = cp_model.CpModel()
solver = cp_model.CpSolver()

# jobs_data[job] = list of (machine, duration) in order of processing
jobs_data = [
    [(0, 3), (1, 2), (2, 2)],   # Job 0: M0 → M1 → M2
    [(1, 3), (0, 2), (2, 3)],   # Job 1: M1 → M0 → M2
    [(2, 2), (0, 3), (1, 2)],   # Job 2: M2 → M0 → M1
]
num_machines = 3
horizon      = sum(d for job in jobs_data for _, d in job)

# ── Build task variables ───────────────────────────────
all_tasks            = {}   # (job, task_id) → (start, end, interval)
machine_to_intervals = {}   # machine → list of intervals

for j, job in enumerate(jobs_data):
    for task_id, (m, dur) in enumerate(job):
        s  = model.new_int_var(0, horizon, f's{j}_{task_id}')
        e  = model.new_int_var(0, horizon, f'e{j}_{task_id}')
        iv = model.new_interval_var(s, dur, e, f'iv{j}_{task_id}')
        all_tasks[(j, task_id)] = (s, e, iv)
        machine_to_intervals.setdefault(m, []).append(iv)

# ── No-overlap per machine ─────────────────────────────
for m, ivs in machine_to_intervals.items():
    model.add_no_overlap(ivs)

# ── Precedence within each job ────────────────────────
for j, job in enumerate(jobs_data):
    for task_id in range(len(job) - 1):
        model.add(
            all_tasks[(j, task_id + 1)][0] >= all_tasks[(j, task_id)][1]
        )

# ── Objective ──────────────────────────────────────────
makespan = model.new_int_var(0, horizon, 'makespan')
model.add_max_equality(
    makespan,
    [all_tasks[(j, len(job)-1)][1] for j, job in enumerate(jobs_data)]
)
model.minimize(makespan)

status = solver.solve(model)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print(f'Optimal makespan: {solver.value(makespan)}')
    for j, job in enumerate(jobs_data):
        for task_id, (m, _) in enumerate(job):
            s, e, _ = all_tasks[(j, task_id)]
            print(f'  Job {j} on M{m}: [{solver.value(s)}, {solver.value(e)})')

CP-SAT Output — by machine Optimal makespan = 10

Horizon matters a lot for job shop. A tight upper bound (e.g., run a greedy heuristic first and use its value as the initial horizon) dramatically reduces solver time. You can also provide a warm-start hint with model.add_hint(var, value) for each start variable.

Problem Type 05

Resource-Constrained Project Scheduling

Tasks have precedence dependencies and consume shared renewable resources. The critical path (longest dependency chain) sets the minimum makespan — but resource limits can push it further. Used in construction, software delivery, and R&D planning.

Precedence constraints

Task B cannot start until Task A finishes. Model the dependency network as starts[B] >= ends[A] for every (A → B) edge.

Resource constraints

Each task demands some quantity of a shared resource (workers, machines, budget). At every time point, total demand across active tasks must not exceed capacity.

RCPSP — 4 tasks, 1 resource (capacity 4), minimize makespan

from ortools.sat.python import cp_model

model  = cp_model.CpModel()
solver = cp_model.CpSolver()

# Task definitions: (duration, resource_demand)
tasks = [
    {'duration': 3, 'demand': 2},   # Task 0
    {'duration': 5, 'demand': 3},   # Task 1
    {'duration': 2, 'demand': 1},   # Task 2
    {'duration': 4, 'demand': 2},   # Task 3
]
# Precedences: (i, j) means task j cannot start before task i finishes
precedences = [(0, 1), (0, 2), (1, 3), (2, 3)]
capacity    = 4                     # total available resource units

horizon     = sum(t['duration'] for t in tasks)

# ── Variables ──────────────────────────────────────────
starts    = [model.new_int_var(0, horizon, f's{i}') for i in range(len(tasks))]
ends      = [model.new_int_var(0, horizon, f'e{i}') for i in range(len(tasks))]
intervals = [
    model.new_interval_var(starts[i], tasks[i]['duration'], ends[i], f'iv{i}')
    for i in range(len(tasks))
]

# ── Precedence constraints ─────────────────────────────
for i, j in precedences:
    model.add(starts[j] >= ends[i])

# ── Resource constraint ────────────────────────────────
demands = [t['demand'] for t in tasks]
model.add_cumulative(intervals, demands, capacity)

# ── Objective ──────────────────────────────────────────
makespan = model.new_int_var(0, horizon, 'makespan')
model.add_max_equality(makespan, ends)
model.minimize(makespan)

status = solver.solve(model)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print(f'Project duration: {solver.value(makespan)}')
    for i, task in enumerate(tasks):
        print(f'  Task {i} (demand={task["demand"]}): '
              f'[{solver.value(starts[i])}, {solver.value(ends[i])})')

CP-SAT Output — with resource utilisation Makespan = 12

Critical path vs resource-feasible path: The critical path (T0→T1→T3 = 3+5+4 = 12) already sets the lower bound here. When resources are tighter, the feasible makespan can be significantly longer than the critical path — that gap is what RCPSP solvers are working to minimize.

Problem Type 06

Sequence-Dependent Setup Times

When the time between two jobs depends on which job ran before, simple no-overlap is no longer enough — the solver must decide the order and the gaps simultaneously. This is the norm in real manufacturing: colour-change washdowns, tool swaps, allergen changeovers.

Why add_no_overlap is not enough

The ordering matters

With setup times, the gap between job i and job j changes based on which one runs first. add_no_overlap prevents overlap but knows nothing about order. You need a constraint that can say: "if j runs right after i, then start[j] ≥ end[i] + setup[i][j]" — and that condition depends on which arc the solver chooses.

The fix

add_circuit — sequence as a graph

model.add_circuit(arcs)

Model the job sequence as a directed Hamiltonian circuit. Each possible "job i → job j" transition is a Boolean arc. The circuit constraint picks exactly one valid path through all jobs. When an arc is true, you conditionally enforce the setup gap with .only_enforce_if(lit).

How the circuit works

Think of jobs as nodes in a directed graph, plus one dummy node (n) that acts as the schedule's "start/end". add_circuit picks exactly one outgoing and one incoming arc per node, forming a single Hamiltonian cycle. For scheduling, the dummy node's arc just marks which job is first and which is last — no timing constraint is attached to those arcs. For real job-to-job arcs, you attach starts[j] ≥ ends[i] + setup[i][j] guarded by the arc's Boolean literal.

Single machine — sequence-dependent setups — minimize makespan

from ortools.sat.python import cp_model

model  = cp_model.CpModel()
solver = cp_model.CpSolver()

durations = [3, 5, 2, 4]           # processing time per job
# setup[i][j] = changeover time when job i is immediately followed by job j
setup = [
    [0, 2, 3, 1],                   # from Job 0
    [2, 0, 1, 4],                   # from Job 1
    [3, 1, 0, 2],                   # from Job 2
    [1, 4, 2, 0],                   # from Job 3
]
n       = len(durations)
horizon = sum(durations) + sum(max(row) for row in setup)  # safe upper bound

# ── Variables ──────────────────────────────────────────
starts    = [model.new_int_var(0, horizon, f's{i}') for i in range(n)]
ends      = [model.new_int_var(0, horizon, f'e{i}') for i in range(n)]
intervals = [
    model.new_interval_var(starts[i], durations[i], ends[i], f'iv{i}')
    for i in range(n)
]

# ── Circuit constraint — encodes the job sequence ─────
arcs = []
for i in range(n):
    # Dummy node n → job i  (job i can be scheduled first)
    arcs.append((n, i, model.new_bool_var(f'first_{i}')))
    # Job i → dummy node n  (job i can be scheduled last)
    arcs.append((i, n, model.new_bool_var(f'last_{i}')))
    for j in range(n):
        if i == j:
            continue
        lit = model.new_bool_var(f'succ_{i}_{j}')
        arcs.append((i, j, lit))
        # Only enforce setup when this arc is active
        model.add(starts[j] >= ends[i] + setup[i][j]).only_enforce_if(lit)

model.add_circuit(arcs)
model.add_no_overlap(intervals)     # helps solver propagate faster

# ── Objective ──────────────────────────────────────────
makespan = model.new_int_var(0, horizon, 'makespan')
model.add_max_equality(makespan, ends)
model.minimize(makespan)

# ── Solve ──────────────────────────────────────────────
status = solver.solve(model)
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print(f'Makespan: {solver.value(makespan)}')
    order = sorted(range(n), key=lambda i: solver.value(starts[i]))
    print('Sequence:', ' → '.join(f'J{i}' for i in order))
    prev = None
    for i in order:
        if prev is not None:
            gap = solver.value(starts[i]) - solver.value(ends[prev])
            print(f'  [setup {setup[prev][i]} → {gap}t idle]')
        print(f'  Job {i}: [{solver.value(starts[i])}, {solver.value(ends[i])})')
        prev = i

CP-SAT Output — optimal sequence J2 → J1 → J0 → J3 Makespan = 18 Total setup = 4

Without setup awareness: any sequence gives makespan = 14 (sum of durations). The worst sequence for this matrix adds 10 units of setup (e.g., J0→J2→J1→J3 = 3+1+4 = 8), pushing makespan to 22. CP-SAT finds the optimal sequence (total setup = 4) automatically — no need to enumerate permutations.

Multi-machine extension: Create one circuit per machine. Use optional intervals per (job, machine) pair and only activate the arc literal when the job is assigned to that machine. This cleanly handles both assignment and sequencing simultaneously.

Scale note: add_circuit creates O(n²) Boolean variables per machine. For n > ~50 jobs on a single machine, solver time grows quickly. Above that, consider warm-starting with a greedy nearest-neighbour sequence and using it as an add_hint.

Going Further

Advanced Patterns

Common real-world constraints that extend the base models.

Release Dates — jobs not available until a given time

A job cannot start before its release date. Just add a lower bound to the start variable.

release_dates = [0, 4, 2, 7, 1]

for i in range(num_jobs):
    # Simple lower bound — the solver will never schedule before this
    model.add(starts[i] >= release_dates[i])

Hard Deadlines — jobs must finish by a given time

An upper bound on the end variable. If a deadline is impossible to meet, the model becomes infeasible — use soft deadlines (tardiness penalty) for more flexibility.

deadlines = [20, 26, 10, 26, 15]

for i in range(num_jobs):
    model.add(ends[i] <= deadlines[i])   # hard deadline

Machine Breaks — planned downtime, maintenance windows

Model a break as a fixed-duration interval on the machine and include it in the no-overlap constraint. Nothing can run during the break.

# Machine has a maintenance break from t=10 to t=14
break_start    = model.new_constant(10)
break_end      = model.new_constant(14)
break_interval = model.new_fixed_size_interval_var(break_start, 4, 'break')

# Include the break in the machine's no-overlap list
all_machine_intervals = intervals + [break_interval]
model.add_no_overlap(all_machine_intervals)

Sequence-Dependent Setup Times

When switching from job type A to job type B requires a setup time that depends on the pair. Use circuit constraints or disjunctive pairs.

# setup_time[i][j] = time required between job i and job j
setup_times = [[0, 2, 3], [1, 0, 2], [3, 1, 0]]

# For each ordered pair (i, j): if i runs before j, enforce the gap
for i in range(num_jobs):
    for j in range(num_jobs):
        if i == j:
            continue
        setup = setup_times[i][j]
        if setup > 0:
            # i precedes j (boolean) → start[j] >= end[i] + setup
            i_before_j = model.new_bool_var(f'order_{i}_{j}')
            model.add(starts[j] >= ends[i] + setup).only_enforce_if(i_before_j)
            model.add(starts[i] >= ends[j]).only_enforce_if(i_before_j.Not())

Optional Jobs — schedule only the most valuable subset

When not every job must be scheduled, use optional intervals. Maximize total value of scheduled jobs.

values    = [10, 25, 8, 15, 20]
durations = [3,   8, 2,  5,  6]
horizon   = 15    # only 15 time units available

intervals  = []
presences  = []
starts_opt = []

for i, (dur, val) in enumerate(zip(durations, values)):
    is_sched = model.new_bool_var(f'scheduled_{i}')
    s  = model.new_int_var(0, horizon, f's{i}')
    e  = model.new_int_var(0, horizon, f'e{i}')
    iv = model.new_optional_interval_var(s, dur, e, is_sched, f'iv{i}')
    intervals.append(iv)
    presences.append(is_sched)
    starts_opt.append(s)

model.add_no_overlap(intervals)

# Maximize value of scheduled jobs
model.maximize(sum(values[i] * presences[i] for i in range(len(values))))

Quick Reference

Constraint Cheatsheet

The complete set of CP-SAT primitives used for scheduling, with when to reach for each one.

Method	What it does	Use when
new_interval_var(s, d, e, name)	Creates a fixed-duration interval. Enforces e = s + d.	Every job in every model
new_optional_interval_var(s, d, e, b, name)	Like interval_var but only active when boolean b is True.	Machine assignment, optional jobs
new_fixed_size_interval_var(s, d, name)	Interval with literal start variable and fixed duration — no end var needed.	Machine breaks, maintenance windows
add_no_overlap(intervals)	No two intervals overlap on the timeline.	Single machine, any exclusive resource
add_no_overlap_2d(x_ivs, y_ivs)	No two rectangles (defined by x and y intervals) overlap in 2D space.	Scheduling on a grid, 2D bin packing
add_cumulative(ivs, demands, cap)	At every time point, sum of active demands ≤ capacity.	Workers, machines as pools, RCPSP
add_max_equality(var, exprs)	var = max of a list of expressions.	Computing makespan from end times
add_exactly_one(bools)	Exactly one boolean in the list is True.	Machine assignment per job
add(expr).only_enforce_if(b)	Constraint is active only when boolean b is True.	Conditional precedence, setup times
add_hint(var, value)	Provides a starting solution hint for the solver.	Warm-starting from a greedy heuristic

Objective Patterns

Objective	CP-SAT expression	Optimal rule (if known)
Makespan (Cmax)	`model.minimize(makespan)` where `add_max_equality(makespan, ends)`	Any order (1 machine)
Total completion (ΣCj)	`model.minimize(sum(ends))`	SPT — shortest first
Weighted completion (ΣwjCj)	`model.minimize(sum(w[i]*ends[i] for i...))`	WSPT — shortest weighted first
Max lateness (Lmax)	`model.minimize(lmax)` where `add_max_equality(lmax, [e-d for e,d...])`	EDD — earliest due date first
Total tardiness (ΣTj)	`model.minimize(sum(tard))` where `add_max_equality(tard[i], [ends[i]-due[i], 0])`	NP-hard — use CP-SAT
Late job count (ΣUj)	Binary variable per job: 1 if `end > due`, minimize sum	Moore's algorithm (1 machine)

Performance

Making the Solver Faster

CP-SAT is powerful, but large scheduling problems can still be slow. These techniques can cut solve time by orders of magnitude.

🎯

Tighten the horizon

Use the tightest valid upper bound. Run a greedy heuristic (LPT, EDD) first and use that solution's makespan as the horizon. Fewer values in each variable = faster search.

🌡️

Warm-start with hints

Provide a feasible starting solution using model.add_hint(var, value). CP-SAT will try to improve from there rather than starting blind.

⏱️

Set a time limit

solver.parameters.max_time_in_seconds = 60.0. For production use, accept a near-optimal solution rather than waiting for a proof of optimality.

🔁

Break symmetry

Identical machines create symmetric solutions. Force an ordering (e.g., machine 0 always gets the first job) to eliminate redundant branches from the search tree.

🧵

Use multiple workers

solver.parameters.num_search_workers = 8. CP-SAT runs a portfolio of parallel search strategies. More workers = faster on large problems.

📡

Stream solutions as found

Implement a CpSolverSolutionCallback to collect improving solutions as the solver finds them. Use the best available rather than waiting for optimality proof.

Solution callback — print every improving solution found

class SolutionPrinter(cp_model.CpSolverSolutionCallback):
    def __init__(self, makespan_var):
        super().__init__()
        self._makespan = makespan_var
        self._count    = 0

    def on_solution_callback(self):
        self._count += 1
        print(f'  Solution {self._count}: makespan = {self.value(self._makespan)}')

solver.parameters.max_time_in_seconds   = 30.0
solver.parameters.num_search_workers    = 8
solver.parameters.log_search_progress   = True   # prints solver log

cb     = SolutionPrinter(makespan)
status = solver.solve(model, cb)
print(f'Status: {solver.status_name(status)}')

Integer domains only: CP-SAT works with integer variables. If your durations are floats (e.g., 1.5 hours), multiply everything by 10 or 100 to convert to integers. Rescale the output at the end.

Scheduling withCP-SAT Solvers

Setup & Install

Three Core Primitives

Single Machine Scheduling

Parallel Machine Scheduling

Flow Shop Scheduling

Job Shop Scheduling

Resource-Constrained Project Scheduling

Sequence-Dependent Setup Times

Advanced Patterns

Constraint Cheatsheet

Objective Patterns

Making the Solver Faster

When Scheduling Meets Reality

Scheduling with
CP-SAT Solvers