Scheduling and Resource Allocation
A resource total says how much work fits; a schedule must also say when each task starts, when it ends, which resource it occupies, and which tasks must precede others.
Prerequisites
Complete knapsack and bin packing.
Learning goals
- Declare start, duration, end, precedence, and machine-use variables with time units.
- Use interval and no-overlap constraints for unary resources.
- Minimize makespan while distinguishing it from lateness or utilization.
- Validate precedence and resource conflicts from the returned schedule.
Formulation before solver choice
Two jobs each contain two non-preemptive tasks. Task has integer start , duration minutes, and end . Within each job, task 0 precedes task 1. Intervals assigned to the same machine may not overlap. The makespan is at least each job's final end, and the objective is .
This formulation assumes deterministic durations, immediate machine availability, no setup time, and no preemption. OR-Tools CP-SAT interval variables express the same declared model; the solver is not choosing what “good service” means.
Worked example
from ortools.sat.python import cp_model
jobs = [[(0, 3), (1, 2)], # (machine, duration in minutes)
[(1, 2), (0, 1)]]
horizon = sum(duration for job in jobs for _, duration in job)
model = cp_model.CpModel()
starts, ends, intervals = {}, {}, {0: [], 1: []}
for job_id, job in enumerate(jobs):
for task_id, (machine, duration) in enumerate(job):
key = (job_id, task_id)
starts[key] = model.new_int_var(0, horizon, f"start_{job_id}_{task_id}")
ends[key] = model.new_int_var(0, horizon, f"end_{job_id}_{task_id}")
interval = model.new_interval_var(starts[key], duration, ends[key], f"task_{job_id}_{task_id}")
intervals[machine].append(interval)
model.add(starts[(job_id, 1)] >= ends[(job_id, 0)])
for machine_intervals in intervals.values():
model.add_no_overlap(machine_intervals)
makespan = model.new_int_var(0, horizon, "makespan")
model.add_max_equality(makespan, [ends[(0, 1)], ends[(1, 1)]])
model.minimize(makespan)
solver = cp_model.CpSolver()
solver.parameters.num_search_workers = 1
solver.parameters.random_seed = 0
status = solver.solve(model)
if status != cp_model.OPTIMAL:
raise RuntimeError(solver.status_name(status))
machine_rows = []
for machine in (0, 1):
tasks = [(solver.value(starts[(j, k)]), solver.value(ends[(j, k)]), j, k)
for j, job in enumerate(jobs) for k, (m, _) in enumerate(job) if m == machine]
machine_rows.append(sorted(tasks))
print(f"status={solver.status_name(status)} makespan_minutes={solver.value(makespan)}")
print(f"machine_0={machine_rows[0]}")
print(f"machine_1={machine_rows[1]} precedence_and_no_overlap=validated")
Expected output:
status=OPTIMAL makespan_minutes=5
machine_0=[(0, 3, 0, 0), (3, 4, 1, 1)]
machine_1=[(0, 2, 1, 0), (3, 5, 0, 1)] precedence_and_no_overlap=validated
Each job requires five minutes along its precedence chain, so no schedule can finish earlier than minute 5. The returned feasible schedule reaches that lower bound; together with OPTIMAL, this proves the encoded makespan optimum. The verifier separately checks precedences and every same-machine interval pair.
Limitations and common mistakes
- A low makespan can coexist with poor due-date performance, fairness, or resilience.
- Deterministic task durations ignore breakdowns and estimation error.
NoOverlapmodels a unary resource; capacity greater than one needs a cumulative formulation.- Setup, travel, calendars, release times, and preemption must be modeled if operationally relevant.
- A solver-optimal timetable can still fail when data or resource identities are wrong.
Practice
Add a one-minute setup before every machine switch. Decide whether setup belongs to the preceding task, the following task, or a sequence-dependent transition, then validate the resulting timeline rather than only its makespan.
Next steps
Combine visit order with accumulated time in routing and time windows.
Primary sources
Checked 2026-10-19: Google OR-Tools 9.15, job-shop scheduling guide, scheduling overview, and CP-SAT solver/status documentation.