← Back to the job shop scheduler

How the job shop scheduler works

A job shop has machines and jobs. Each job is a list of operations in a fixed order (saw, then mill, then drill), each on one machine for a set time. A machine runs one operation at a time and finishes it once started. Choosing the order each machine takes its work in fixes the whole schedule: every operation starts as soon as both its machine and the job's previous step are free. The makespan is when the last job finishes. Finding the order with the shortest makespan is the classic job shop problem, and it is NP-hard: a 10-job, 10-machine instance published in 1963 (Fisher and Thompson's ft10) was only proved optimal in 1989 (Carlier and Pinson, Management Science 35(2)).

1. The schedule as a graph

Each operation is a node. Arrows join each job's steps in order; choosing machine orders adds arrows between operations on the same machine. The makespan is the longest path through the graph, and a set of orders is valid when the graph has no cycle. This is the disjunctive graph of Roy and Sussmann (1964) and Balas (1969, Operations Research 17(6)). For every operation the page computes its head (earliest start) and its tail (the longest path after it ends). An operation whose head, time and tail add up to the makespan is critical: delaying it delays everything.

2. A first schedule from dispatch rules

Giffler and Thompson's algorithm (1960, Operations Research 8(4)) builds an active schedule one operation at a time: find the operation that could finish first, collect the operations on its machine that could start before then, and pick one by a rule. The page tries five rules (most work remaining, shortest operation, most operations remaining, longest operation, first come) and keeps the best. Some optimal schedule is always active, so this is also the branching rule of the exact search below.

3. Tabu search on critical blocks

Only reordering critical operations can shorten the makespan. Along one critical path, consecutive operations on the same machine form blocks. Nowicki and Smutnicki (1996, Management Science 42(6)) used the fact that swaps inside a block cannot shorten the makespan straight away unless they touch its first or last operation, so their N5 neighbourhood only swaps the first two or the last two operations of each block. Swapping two adjacent critical operations never creates a cycle (van Laarhoven, Aarts and Lenstra, 1992). Each candidate swap is scored by Taillard's quick estimate (1994, ORSA Journal on Computing 6(2)) from the heads and tails, without rebuilding the schedule. The page takes the best swap that is not tabu (recently reversed) unless it beats the best schedule so far, and after a long run without improvement it restarts from the best schedule with a few random swaps. Our code is a plain version of these ideas, not a reproduction of the published TSAB algorithm, which adds a back-jump list and is stronger.

4. The lower bound, and when the page says "proved"

If the best schedule's makespan equals the bound, it is optimal and the page says so. On shops of up to 64 operations, the page then runs a depth-first branch and bound over Giffler-Thompson choices, cutting any branch whose one-machine bound (recomputed for the operations left) cannot beat the best schedule. It first runs this search capped at 2,000 nodes, before any tabu search: in a run on 300 random shops of up to 7 jobs and 6 machines, nine in ten of the shops the dispatch rules left unproved were settled within that cap. Only the rest get a short tabu run (at most 300 ms) for a better starting schedule, then the uncapped search until the time limit. If it finishes, the answer is proved by exhaustive search. Otherwise the page shows the best schedule and the bound, and never calls that answer optimal.

5. How it did on the standard benchmarks

JSPLIB collects the 162 job shop instances researchers test on: Fisher and Thompson's ft06, ft10 and ft20 (in Muth and Thompson, 1963), Lawrence's la01 to la40 (1984), Adams, Balas and Zawack's abz5 to abz9 (1988), Applegate and Cook's orb01 to orb10 (1991), Storer, Wu and Vaccari's swv01 to swv20 (1992), Yamada and Nakano's yn1 to yn4 (1992) and Taillard's ta01 to ta80 (1993), from 6 jobs on 6 machines to 100 jobs on 20. Its instances.json records each optimum, or bounds where none was known when it was compiled. bench/jsplib.mjs runs the engine on every instance with the page's default limit of 4 seconds on one thread, checks every schedule with code separate from the solver, and writes bench/jsplib.md.

JSPLIB, 4 s per instanceInstances
Same makespan as JSPLIB's recorded optimum66 of 103
Proved optimal by this engine within the limit54 of 162
Longer than JSPLIB's optimum or best upper bound85
Shorter than JSPLIB's best upper bound1
Mean gap to JSPLIB's optimum or upper bound (152 instances that have one)1.01%

By family: all three Fisher and Thompson instances at their optima, including ft10 (930) and ft20 (1165); Lawrence's la01 to la40 at the optimum on 30 of 40, with a mean gap of 0.19% and the worst 1.7%; Applegate and Cook's orb at 7 of 10. The harder families are further off: abz 2 of 5 (mean gap 1.4%), swv 5 of 20 (2.4%, worst 5.5%), yn 0 of 4 (1.4%) and Taillard's ta01 to ta70 at 1.2% on average, worst 4.4%. Most of the proofs come from the schedule meeting the lower bound, which is common on instances with many more jobs than machines. On Taillard's ten largest (ta71 to ta80, 100 jobs on 20 machines), for which JSPLIB records no value, the engine met its own lower bound, and so proved its schedule optimal, on 9 of 10. On ta29 its 1627 is below JSPLIB's recorded upper bound of 1635; that bound is out of date, and better schedules for ta29 have been published since, so this is not a new record. Published state-of-the-art methods get much closer to the best known values, usually with far longer runs; a plain tabu search at 4 seconds on one browser thread does not, and the table shows where. On every unproved row the page says "best found" and gives the bound.

6. What it does not model

This is the classic problem: each operation on one named machine, fixed times, no setup or changeover times, no transport between machines, every job available at time zero, and the goal is the makespan rather than due dates. Real shops have alternative machines, shifts, breakdowns and rush orders. Use the answer as a sequence to start from and a measure of what the routings allow, and check it on the floor.