The assignment problem: six orders, six machines, and the price of each
Chapter 11 of Korte & Vygen opens with the assignment problem. In a box plant it is the morning question: which converting order goes on which machine this shift. Here it is solved the way the book solves it, as a minimum-cost flow by successive shortest paths, on an instance you can step through. Watch the algorithm re-route work it already placed, and then read the prices that prove the answer.
The instance
Six orders staged for the day shift. Six machines: two flexo folder-gluers (FFG-1 is new and fast, FFG-2 is older), two rotary die cutters (RDC-1, RDC-2), a flatbed die cutter (FBD) and a printer-slotter (PS). Each cell is the machine-minutes that order would take on that machine, setup plus run at the machine's speed. A dash means the machine cannot run the order: a die cutter has no gluer, a folder-gluer has no die.
Each machine takes one order. Assign all six to minimize total machine-minutes. There are 6! = 720 assignments; a scheduler does this by instinct in about two minutes and is usually close. The algorithm takes six steps and is provably not just close.
Why the obvious shortcut fails
The shortcut everyone reaches for is cheapest-first: sort every (order, machine) pair by cost, take the cheapest, cross out its row and column, repeat.
Greedy's second pick hands FFG-1 to order E, the cheapest cell left on the table, and its fourth gives A the other folder-gluer. Order C, which can only run on a folder-gluer, has nowhere to go. It isn't suboptimal; it's infeasible. Instinct avoids that particular trap because the scheduler knows C needs a gluer. But instinct makes the same kind of mistake quietly whenever the cheapest local choice uses up a machine something else needed more, and nobody notices because the shift still runs.
The book's move: it is a flow
Korte and Vygen don't give the assignment problem its own algorithm. They point out that it is a special case of something already solved. Draw a source s with an arc to every order, an arc from every order to every machine that can run it, with the minutes as its cost, and an arc from every machine to a sink t. Every arc has capacity 1. A flow of value 6 from s to t is a perfect matching, and its cost is the total minutes. Minimum-cost flow of value 6 is the answer, and section 9.4 already has the algorithm: successive shortest paths.
The algorithm starts with nothing assigned and repeats six times: find the cheapest s→t path in the residual graph, push one unit of flow along it. The residual graph is where it gets interesting. Once an order is matched to a machine, the arc between them can be traversed backwards at negative cost, which means un-matching it. So a shortest path can run: free order → machine already taken → back to the order that held it → a different machine. That is a re-route, and it is the whole reason the method is exact where greedy isn't. Greedy never takes anything back.
Two more details make it fast. Backward arcs have negative costs, which breaks Dijkstra, so the algorithm keeps a potential π on every node and runs Dijkstra on reduced costs c(u,v) + π(u) − π(v), which stay non-negative if π is updated with the Dijkstra distances after each step. Six augmentations, each one a Dijkstra: O(n(m + n log n)), the Hungarian method in modern dress.
Step through it
For three steps the algorithm and greedy agree: F to the flatbed, E to FFG-1, B to RDC-1, the three cheapest free cells. Step 4 is where they part. Greedy would put A on FFG-2 for 138 and move on. The shortest path instead runs A → FFG-1 → back along E's arc → FFG-2: 85 − 55 + 89 = 119. It takes the fast folder-gluer away from E and moves E to the slow one, because that is 19 minutes cheaper than leaving E alone. Step 5 is the long one. C can only run on the two folder-gluers and both are taken, so the path is C → FFG-1 → A → FFG-2 → E → PS: C takes FFG-1 from A, A takes FFG-2 from E, E goes to the printer-slotter, 115 − 85 + 138 − 89 + 116 = 195, and two orders move in a single step. Step 6 re-routes B to make room for D. Six augmentations, 686 minutes, and brute force over all 720 permutations agrees.
The prices
The potentials are not bookkeeping; they are the dual solution, and the dual is what makes 686 a proof rather than a result. Write ui for a price on each order and vj for a price on each machine. Any prices with ui + vj ≤ cij on every feasible cell give a lower bound: no assignment can cost less than Σu + Σv, because each assigned cell costs at least its two prices. When the algorithm stops, the potentials give prices whose sum is exactly 686, and every assigned cell is tight: ui + vj = cij. Switch the table above to slack and look: the chosen cells are the zeros, every other cell is positive, and the margins sum to the total. That table is the certificate. Anyone can check it in a minute without re-running anything.
The prices mean something on the floor, too. The slack on a cell is the premium you'd pay to force that order onto that machine. Order C on FFG-2 has slack 23: if the superintendent insists on it, that is the cost of the insistence, and the algorithm has already priced it. Order D on the flatbed has slack 345; nobody should ever insist on that.
Where it shows up in a plant
- Orders to machines per shift, as here. With more orders than machines, add a cost for leaving an order until tomorrow and the same flow solves it; machines that can take two orders get capacity 2 on their arc to the sink.
- Trucks to dock doors, cost = forklift travel from the door to where that load is staged.
- Crews to machines, cost = expected waste or speed loss for that crew on that machine, from the shift data.
- Rolls to roll stands on the corrugator, cost = the trim that roll would leave against the next order.
And where it stops: the moment the cost of running an order depends on what ran before it, setups become sequence-dependent and this is no longer an assignment problem. That is a scheduling problem with a traveling-salesman inside it, which is why the corrugator scheduler needed branch and bound and this post needed six Dijkstras.
The Python
The core of assignment.py, which also carries the brute-force check and runs 400 random instances against it. The JavaScript behind the figures is the same algorithm; the show the code dropdown under each one has it.
def successive_shortest_paths(cost):
n = len(cost)
S, T, N = 2*n, 2*n + 1, 2*n + 2 # source, sink, node count
match_l, match_r = [-1]*n, [-1]*n # order -> machine, machine -> order
pi = [0.0]*N # potentials: reduced costs stay >= 0
total = 0.0
def residual(x): # (neighbour, cost) under the current matching
if x == S:
for i in range(n):
if match_l[i] == -1: yield i, 0.0
elif x < n: # order: forward to any machine it isn't on
for j in range(n):
if cost[x][j] is not None and match_l[x] != j: yield n + j, cost[x][j]
elif x < 2*n: # machine: to the sink if free, else BACK to its order
j = x - n
if match_r[j] == -1: yield T, 0.0
else: yield match_r[j], -cost[match_r[j]][j]
for _ in range(n):
dist, prev = [INF]*N, [-1]*N # 1. Dijkstra on reduced costs
dist[S] = 0.0; heap = [(0.0, S)]
while heap:
d, x = heapq.heappop(heap)
if d > dist[x]: continue
for y, c in residual(x):
nd = d + c + pi[x] - pi[y]
if nd < dist[y]:
dist[y], prev[y] = nd, x; heapq.heappush(heap, (nd, y))
if dist[T] == INF: raise ValueError("no perfect matching")
y = T # 2. augment: flip the path's order-machine arcs
while y != S:
x = prev[y]
if x < n and n <= y < 2*n:
match_l[x], match_r[y - n] = y - n, x
y = x
D = max(d for d in dist if d < INF) # 3. potentials += distances
pi = [p + (d if d < INF else D) for p, d in zip(pi, dist)]
total = sum(cost[i][match_l[i]] for i in range(n))
u = [-pi[i] for i in range(n)] # the dual: u_i + v_j <= c_ij, tight on the matching,
v = [pi[n + j] for j in range(n)] # and sum(u) + sum(v) == total
return match_l, total, u, vThe test that matters is the last three lines: after every solve, the code asserts u[i] + v[j] <= cost[i][j] on every feasible cell, equality on the matched ones, and sum(u) + sum(v) == total. If any of those fails, the matching might still be optimal, but the program could no longer prove it, and a result without its certificate is a guess with good manners.