Scheduling

Short note. A compact reference, correct as far as it goes. It will be expanded into a full guide with a worked example and an interactive demonstration.

Problem

A set of jobs, each made of an ordered sequence of operations, needs to run across a set of machines that can only do one thing at a time. Find a schedule minimizing makespan (or lateness, or another time-based objective).

When to use it

Manufacturing floor scheduling, CNC/machine scheduling, any “shared resource, ordered tasks” problem — including software build/CI pipelines if you squint at it right.

Formulation

For each operation (j, o) define a start time s_jo. Two kinds of constraints: precedence (within a job, operations run in order) and disjunctive (on a shared machine, only one operation runs at a time — this needs a binary to pick the order):

minimize   makespan
subject to:
  s_j,o+1 >= s_jo + p_jo                       # precedence within a job
  s_jo >= s_kl + p_kl - M*(1 - y_jokl)         # disjunctive pair on same machine
  s_kl >= s_jo + p_jo - M*y_jokl
  makespan >= s_jo + p_jo   for all (j, o)

y_jokl is a binary picking which of the two conflicting operations goes first — this is exactly the Big-M pattern applied to a scheduling conflict.

Code sketch

from ortools.sat.python import cp_model

model = cp_model.CpModel()
horizon = sum(p for job in jobs for _, p in job)

starts, ends, intervals = {}, {}, {}
for j, job in enumerate(jobs):
    for o, (machine, dur) in enumerate(job):
        start = model.NewIntVar(0, horizon, f"start_{j}_{o}")
        end = model.NewIntVar(0, horizon, f"end_{j}_{o}")
        interval = model.NewIntervalVar(start, dur, end, f"interval_{j}_{o}")
        starts[j, o], ends[j, o], intervals[j, o] = start, end, interval
        if o > 0:
            model.Add(start >= ends[j, o - 1])

for machine_id in machines:
    model.AddNoOverlap([intervals[j, o] for j, o in ops_on(machine_id)])

makespan = model.NewIntVar(0, horizon, "makespan")
model.AddMaxEquality(makespan, list(ends.values()))
model.Minimize(makespan)

Pitfalls

• Hand-writing the disjunctive Big-M constraints (as in the math above) is a good learning exercise, but in practice use a CP-SAT solver’s NoOverlap / interval variables (as in the code sketch) — it’s built exactly for this and scales far better than the raw MILP formulation.
• Job shop scheduling is NP-hard and even 10x10 instances (10 jobs, 10 machines) can be genuinely hard to solve to optimality — set a time limit and accept a good incumbent rather than waiting for proof of optimality.
• Setup times and machine maintenance windows are common real-world additions — model them as extra intervals reserved on the machine’s NoOverlap list rather than bolting on separate logic.