An agent-written scheduler beats commercial solvers: 525,515 on a 100,000-operation job shop, below OptalCP, Hexaly and CP Optimizer
Synopsis
A frontier large language model, used as a coding agent with open-source tools only, reformulated shop-scheduling problems and wrote its own heuristic solvers. On the 100,000-operation instance tai_100_1000_1 its solver reached 525,515, below OptalCP, Hexaly and CP Optimizer; with equal budgets on one workstation it ended 0.0–1.8% above the lower bound across ten instances of the family, against 2.6–5.8% for CP Optimizer and 2.4–4.4% for Hexaly. On transport-robot MKT instances it improved seven of ten, but on Chambers–Barnes instances, where processing times dominate travel times, it was weaker than a CP Optimizer approach.
Interpretation
A frontier large language model used as a coding agent, with open-source tools only, can write solvers that outperform commercial solvers on large job-shop instances. Commercial solvers are the standard tool for such difficult scheduling problems but require paid licenses, while open-source solvers are often weaker on large instances. On the 100,000-operation tai_100_1000_1, the agent-written solver reached 525,515 with a 16-core budget, below the published values of OptalCP, Hexaly and CP Optimizer.
The agent did not apply one fixed algorithm; it analyzed each instance's structure and then changed the formulation or designed the search accordingly. On tai_100_1000_1 the agent started from a greedy schedule of 593,321, and four solvers minimizing makespan reached at best 592,865. At minute 42 the agent switched to a corridor search that fixes a target makespan and gives each operation a time window, leaving only machine conflicts; the first corridor prototype found 540,999 after about 60 s, and a worker of the C version found 527,000 around minute 77.
The agent-written solver transfers unchanged to instances of the same family and yields new best-known values that can be re-checked. All ten instances of the tai_100_1000 family were open in JSPLib before this work. Run unchanged on all ten, the corridor solver went below the previous best-known upper bound on every instance within 10 minutes, and reached the lower bound on tai_100_1000_2 and _3, closing them; with one core and 30 minutes the agent solver ended 0.0–1.8% above the lower bound, against 3.7–5.8% for CP Optimizer and 2.7–4.4% for Hexaly.
Perspective
The conclusions rest on three published benchmark families: the Da Col and Teppan job shops, the Behnke–Geiger flexible job shops, and the Homayouni and Fontes flexible job shops with transport robots; every schedule is verified by an independent checker that shares no code with the solvers, and instances, schedules, checkers, solver source and logs are public. The authors propose a standardized benchmark covering many problem classes, with task text, tools, compute and time budget held fixed across model families, as the next step.
Only models from one provider were tested, and controlled comparisons across models and problem classes are still needed; benchmark generators can impose regular structure, and industrial problems are often less regular and carry extra constraints, so the conclusions may not hold there. The agents raised no lower bound on any job-shop or Behnke instance, and tai_100_1000_1 and behnke16 remain open; the transfer runs used short budgets and few seeds, and the commercial solvers used standard models with default parameters. MKT10 served as the main development instance of the transport solver, which may favor it; three of the five lower MKT values reported by Dong et al. fall below the new lower bound, and the other two came without schedules and could not be checked.
