Job-shop scheduling

The problem

A workshop has several machines and a list of jobs. Each job is a fixed sequence of operations, and each operation needs one specific machine for a known time: a bike frame is cut, then welded, then painted. A machine works on one operation at a time, an operation can't be interrupted once started, and a job's operations must run in order. Find a schedule that finishes everything as early as possible. The finishing time of the last operation is the makespan.

Factories are the classic setting, but the same structure appears whenever tasks with an internal order compete for shared resources: operating rooms and surgical teams, test rigs in a lab, compute jobs on a cluster, or a print shop where every order passes through different presses. With due dates added, the goal often shifts from makespan to lateness.

Formal model

Give each operation o a start time S_o and duration p_o. Then:

That "or" is what makes it hard, and it has a beautiful picture: the disjunctive graph. Every operation is a node. Arrows fixed by job order are always there; every pair of operations on the same machine is joined by an undirected edge that must be turned into an arrow one way or the other. Pick a direction for every such edge without creating a cycle and you've picked a schedule. Its makespan is the length of the longest path through the graph, which is exactly the critical path the lab highlights in amber.

Why it's hard

A schedule is fixed by choosing the order of operations on each machine. With n jobs that each visit all m machines, that's (n!)^m combinations: about 1.4 × 10¹⁷ for the 6 × 6 instance ft06, and 4 × 10⁶⁵ for its 10 × 10 sibling ft10. Many are infeasible, many are equivalent, but no known method avoids exponential effort in the worst case. The problem is strongly NP-hard.

ft10 was published in 1963 and its optimum, 930, wasn't proven until 1989. Benchmark instances from the early 1990s still include some whose optimum nobody has proven. Job-shop scheduling is famous for being hard in practice, not just in theory.

Data structures

The disjunctive graph as arrays

Tabu search stores a schedule as one array per machine listing its operations in order. Together with each job's fixed order, that defines a directed acyclic graph. A topological sort (Kahn's algorithm, using an in-degree count and a queue) visits the operations so that each one's predecessors are done first, and the earliest start of each is the larger of its job predecessor's and machine predecessor's finish times. That's the longest path, computed in O(N) for N operations. If the sort can't visit every node, the orders contain a cycle and the schedule is impossible.

Ready times and a waiting set

Dispatching keeps, for every job and every machine, the time it becomes free, plus the set of operations whose job predecessor is done. Each round computes earliest start and finish for every waiting operation, so a round costs O(n) and the whole schedule O(n² · m).

The tabu list

Tabu search's short-term memory is a hash map from an ordered pair of operations to the iteration until which swapping them back is forbidden. Checking a move is a single lookup.

The algorithms

Giffler–Thompson with priority rules

The Giffler–Thompson algorithm builds an active schedule, one where no operation could start earlier without delaying another. Some optimal schedule is always active, so the method never rules out the best answer by construction. In each round it finds the waiting operation that could finish first, looks at its machine, and collects every operation that wants that machine and could start before that finish time. Only those genuinely compete; a priority rule picks the winner:

None of them is best on every instance, which is why the comparison chart is worth a look on each example.

Tabu search on the critical path

Only the critical path determines the makespan, so only reordering operations on it can shorten the schedule. The neighborhood used here, from van Laarhoven, Aarts and Lenstra, swaps two adjacent operations that share a machine on the critical path. Such a swap can never create a cycle, so every neighbor is a valid schedule. Each iteration moves to the best neighbor, even if it is worse, and forbids undoing the move for a few iterations. That forced exploration is what lets it climb out of local optima. On ft06 it reaches the proven optimum of 55.

Beyond this lab

• Constraint programming. Today's strongest exact solvers, such as Google's CP-SAT and IBM's CP Optimizer, reason about time windows on each machine and prune huge parts of the search with clever propagation.
• Shifting bottleneck. Adams, Balas and Zawack's 1988 heuristic schedules the most constrained machine first by solving a one-machine problem, then reoptimizes the others.
• Stronger tabu search. Nowicki and Smutnicki's 1996 algorithm restricts swaps to the ends of critical blocks, which cuts the neighborhood without losing good moves. It was state of the art for years.
• Variants. Flow shop, where every job visits the machines in the same order (Johnson's 1954 rule solves the two-machine case exactly); open shop, where the order is free; flexible job shop, where an operation can run on any of several machines; and versions with setup times or due dates.

A little history

Selmer Johnson solved the two-machine flow shop in 1954, one of the first results in scheduling theory. Bernard Giffler and Gerald Thompson described active schedules and how to generate them in 1960. In 1963 Henry Fisher and Gerald Thompson published the test problems now called ft06, ft10 and ft20, and in 1964 Bernard Roy and B. Sussmann introduced the disjunctive graph. Jacques Carlier and Éric Pinson finally proved ft10's optimum with branch and bound in 1989.