Job shop scheduling, Taillard's open 30x20 instances

# Job shop scheduling, Taillard's open 30x20 instances ## Goal A **job shop** has `n` jobs and `m` machines. Each job is a fixed sequence of `m` operations, one per machine, each with an integer duration; a machine processes one operation at a time; no preemption. The **makespan** is the time the last operation finishes. Minimise it. Taillard's 1993 benchmark set has 80 instances. Fifty years of tabu search, constraint programming and hybrids have closed most of them, but the ten **30-job, 20-machine** instances `ta41`-`ta50` are all still open: for each the best-known schedule is strictly above the best proven lower bound (by 2 to 94 units). Those ten are the whole benchmark here. Any schedule shorter than a best-known one is a new upper bound on a problem people have attacked since 1993. ## Solver interface `schedule.py` exposes schedule(name: str, jobs: list[list[tuple[int, int]]], time_budget: float, seed: int) -> list[list[int]] - `name` is the instance name (`"ta41"` ...), `jobs[j]` is job `j`'s routing in processing order: `jobs[j][k] = (machine, duration)` for its `k`-th operation, machines numbered `0..m-1`, every job visiting every machine exactly once. You receive a private copy; mutate it if you like. - Return **one list per machine, in machine order 0..m-1**: `result[i]` is the list of the `n` job indices in the order machine `i` processes them (a permutation of `range(n)`). That is the whole encoding: no start times, no makespan. The eval rebuilds the earliest-start (semi-active) schedule from your orders plus the routings and measures the makespan itself. - A set of machine orders that contradicts the routings (a cycle in the disjunctive graph), a missing machine, a repeated or out-of-range job, a non-integer: all `wrong_answer`, and one bad instance fails the whole run. Every 30x20 instance is shipped as `instances/<name>.txt` in the standard JSPLIB / OR-Library layout (`n m` on the first line, then a line per job of `machine duration` pairs). Those files are read by the eval, not by you (`open` is not allowed in a solver); the data reaches you as `jobs`. ## Metric metric = mean over instances of best_known(name) / makespan(name) so 1.0 means matching every best-known makespan and any per-instance ratio above 1.0 is a new record. Per-instance makespans, records, lower bounds and ratios are in the eval output (`per_instance`); instances you beat are listed under `records_beaten`. Environment knobs (both honoured by `eval.py`): - `ZT_EVAL_SEED` only changes the `seed` handed to your solver. The instance set is fixed; the hub verifies with a held-out seed, so make your method robust to its starting point, and deterministic given `seed` (`random.Random(seed)`). - `ZT_EVAL_INSTANCES` is a comma-separated subset of instance names (default all ten). Use it to iterate on one instance quickly, e.g. `ZT_EVAL_INSTANCES=ta45,ta50`. - `ZT_EVAL_PER_INSTANCE_SECONDS` is the `time_budget` handed to each call (default 10, so a full eval is about 100 s). The eval fails a call that runs past `1.25 * budget + 3` s. Use the whole budget: on these instances more search time is still worth roughly 1 % of makespan. ## Records Best-known makespans (upper bounds) and lower bounds from Oleg Shylo's bounds page for Taillard's instances, https://optimizizer.com/TA.php, last updated 2026-06-29, read 2026-09-07. Every upper bound in this table was re-verified for this pack by decoding the solution posted on that page against the instance data with this pack's own eval. None is proven optimal. | instance | size | best-known makespan (source) | lower bound (source) | gap | |---|---|---|---|---| | ta41 | 30x20 | 2006 (Shylo & Pardalos 2008, parallel GES) | 1912 (Heinz, Hanzálek & Vilím 2024) | 94 | | ta42 | 30x20 | 1939 (Hernandez-Constantino & Segura 2019, parallel memetic) | 1887 (Heinz, Hanzálek & Vilím 2024) | 52 | | ta43 | 30x20 | 1846 (Peng, Lü & Cheng 2015, TS/path relinking) | 1809 (Vaessens 1995) | 37 | | ta44 | 30x20 | 1978 (Liu, Li & Gao 2026, to appear) | 1952 (Heinz, Hanzálek & Vilím 2024) | 26 | | ta45 | 30x20 | 1999 (Liu, Li & Gao 2026, to appear) | 1997 (Vaessens 1995) | 2 | | ta46 | 30x20 | 2002 (Liu, Li & Gao 2026, to appear) | 1966 (Heinz, Hanzálek & Vilím 2024) | 36 | | ta47 | 30x20 | 1889 (Peng, Lü & Cheng 2015, TS/path relinking) | 1816 (Heinz, Hanzálek & Vilím 2024) | 73 | | ta48 | 30x20 | 1937 (Shylo & Shams 2018, guided tabu, arXiv:1808.10813) | 1915 (Heinz, Hanzálek & Vilím 2024) | 22 | | ta49 | 30x20 | 1960 (Li, Hao & Wu 2024, hash-based tabu + pattern mining) | 1934 (Heinz, Hanzálek & Vilím 2024) | 26 | | ta50 | 30x20 | 1923 (Peng, Lü & Cheng 2015, TS/path relinking) | 1837 (Heinz, Hanzálek & Vilím 2024) | 86 | Sources, as cited on that page: Shylo & Pardalos (2008), parallel implementation of global equilibrium search; Hernandez-Constantino & Segura (2019), a parallel memetic algorithm with explicit diversity control; Peng, Lü & Cheng (2015), *A tabu search/path relinking algorithm to solve the job shop scheduling problem*, Computers & Operations Research 53; Shylo & Shams (2018), *Boosting binary optimization via binary classification: a case study of job shop scheduling*, arXiv:1808.10813; Li, Hao & Wu (2024), *Combining hash-based tabu search and frequent pattern mining for job-shop scheduling*; Liu, Li & Gao (2026, to appear), a knowledge-driven decoupling and coordinated optimisation framework; lower bounds from Heinz, Hanzálek & Vilím (2024), *Reinforcement learning for search tree size minimization in constraint programming*, SSRN 4938242, and Vaessens (1995) as listed on Taillard's page. Cross-check: Weise's survey table (github.com/thomasWeise/jsspInstancesAndResults, 2020-11-24) lists ta41 = 2005 (Vilím, Laborie & Shaw 2015 detailed results) and ta42 = 1937 (Gonçalves & Resende 2014); those two schedules are not posted anywhere we could decode, so this pack pins the verified 2006 and 1939 instead. If you reach 2005 or 1937 you have matched a literature claim; below it you have a record. Instance data: `tamy0612/JSPLIB` on GitHub (`instances/ta41`..`ta50`, commit ac33e816, 2014-04-22), checked operation-for-operation against Taillard's original `tai30_20.txt` (as mirrored in Weise's repository) on 2026-09-07. ## Constraints - Standard library only. No numpy, no scipy, no file or process access. The eval rejects other imports and the names `open`, `exec`, `eval`, `__import__`. - Respect `time_budget` (seconds, per call). Deterministic given `seed`. ## Ideas that are known to matter (check the journal before repeating one) - **Disjunctive graph + critical path.** Evaluate a set of machine orders by a topological pass over job arcs and machine arcs; the makespan is the longest path. Only moves that touch the critical path can improve the makespan, so every good neighbourhood is defined on critical blocks (maximal runs of consecutive critical operations on one machine). - **N5 (Nowicki & Smutnicki 1996):** swap only the first two or last two operations of each critical block. Small, always feasible, and the original *TSAB* tabu search with this neighbourhood, a short tabu list and back-jump tracking to elite solutions was the state of the art for years. **N6 (Balas & Vazacopoulos 1998):** move an operation inside a block to the block's start or end (forward and backward insertions with a feasibility test on head/tail lengths). Larger and stronger; used by Zhang et al.'s TS/SA hybrid and by Peng, Lü & Cheng's tabu search / path relinking, which set three of the records above. - **Fast move evaluation.** Recomputing the whole schedule per neighbour costs O(nm); computing heads (longest path from the source) and tails (to the sink) once lets you bound a swap's new makespan in O(1) (Taillard's estimate), so you evaluate the whole neighbourhood and recompute only for the chosen move. - **Shifting bottleneck (Adams, Balas & Zawack 1988):** sequence machines one at a time, each as a one-machine problem with heads and tails (Carlier's algorithm), re-optimising already sequenced machines after each insertion. Good starting solutions for 30x20; pair with tabu search. - **Starting points and diversification.** Giffler-Thompson active schedules with priority rules (most work remaining, shortest processing time) are cheap; random restarts from them are weak. Path relinking between elite solutions (Peng, Lü & Cheng) and the *big valley* structure (Nowicki & Smutnicki 2005's i-TSAB) are what distinguish record-setting runs from ordinary tabu. - The budget is short. A tabu search with an O(1) move estimate does tens of thousands of iterations per second in plain Python on 600 operations; make the inner loop tight (flat lists, no dicts keyed by tuples) before adding cleverness. Write one honest line in `NOTES.md`: the idea, and which instances it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.