Schedule jobs to minimize makespan in Python

A recurring scheduling problem: you have a set of jobs with known durations and several identical machines (or workers, cores, servers), and you want to split the jobs so everything finishes as early as possible. The finish time of the busiest machine is the makespan, and minimizing it is the classic parallel-machine scheduling problem. This is load balancing across machines — the P || Cmax problem — not job-shop or staff rostering.

The obvious approach is to try every way of assigning jobs to machines. The approach that scales is to model it and hand it to a solver — with quicopt that is a few lines of Python.

The brute-force trap

"Try every assignment" means looping over all ways to place N jobs on M machines:

from itertools import product

proc = [3, 1, 6, 4, 2, 5, 7, 2]   # processing time per job
M = 3
N = len(proc)

def makespan(assign):
    load = [0] * M
    for j, m in enumerate(assign):
        load[m] += proc[j]
    return max(load)

print(min(makespan(a) for a in product(range(M), repeat=N)))  # -> 10

Fine for eight jobs on three machines. But the number of assignments is M^N, which explodes:

• 8 jobs, 3 machines → 6,561 (instant)
• 20 jobs, 3 machines → 3,486,784,401
• 20 jobs, 5 machines → 95,367,431,640,625

Enumeration is hopeless the moment the shop is real.

Model it as a MILP

Makespan minimization is a mixed-integer linear program (MILP). A binary variable x[j][m] puts job j on machine m. Each job goes on exactly one machine; one continuous variable makespan is forced to be at least the load of every machine; and we minimize it:

from ortools.math_opt.python import mathopt
from quicopt import Client

# Distribute N jobs across M identical machines to minimize the makespan
# (the finish time of the busiest machine).
proc = [3, 1, 6, 4, 2, 5, 7, 2]   # processing time per job
M = 3
N = len(proc)

model = mathopt.Model(name="scheduling")
x = [[model.add_binary_variable(name=f"x_{j}_{m}") for m in range(M)] for j in range(N)]
makespan = model.add_variable(lb=0.0, name="makespan")

for j in range(N):                                   # each job on exactly one machine
    model.add_linear_constraint(sum(x[j][m] for m in range(M)) == 1)
for m in range(M):                                   # makespan >= load of every machine
    model.add_linear_constraint(sum(proc[j] * x[j][m] for j in range(N)) <= makespan)

model.minimize(makespan)

client = Client("https://try.quicoptapi.pgi.fz-juelich.de")
result = client.solve(model)
print(result.display)

├── status:     optimal
├── feasible:   true
├── objective:  10.0
├── x:          makespan=10, x_0_0=0, x_0_1=0, x_0_2=1, x_1_0=0, x_1_1=1, …  (25 variables)
└── solve_time: 0.0196 s

What you get

status: optimal means the solver proved the makespan can't go below 10. The total work is 30 units over three machines, so 10 is a perfect balance — and the solver found an assignment that hits it, in a fraction of a second.

The difference is scaling. Brute force is O(M^n); a MILP solver prunes the search with bounds instead of enumerating it. The same model that schedules 8 jobs schedules 800 — you change the data, not the approach. (This is the P || Cmax problem, NP-hard in general, which is exactly why a solver beats hand-rolled search.)

Next

• The problem class behind this: MILP
• Related guides: Employee shift scheduling · Assignment
• A runnable model for every supported class: Examples
• Set up the client and solve your first model: Getting started

Reference: R. L. Graham, Bounds on Multiprocessing Timing Anomalies, SIAM Journal on Applied Mathematics, 1969.