Agent-written heuristics versus commercial solvers on unsolved job-shop benchmark instances
Authors: Andre Albrecht, Enzo Morosini Frazzon, Leandro C. Coelho, Bruno Vieira
Organizations: ProLogIS – Production and Logistics Intelligent Systems, Department of Production Engineering, Federal University of Santa Catarina (UFSC), Florianópolis, SC, 88040-900, Brazil · CIRRELT and Canada Research Chair in Integrated Logistics, Université Laval, Québec, QC, G1V 0A6, Canada · Department of Industrial Engineering, Federal Institute of Santa Catarina (IFSC), Caçador, SC, 89503-550, Brazil
Commercial solvers are the standard tool for difficult scheduling problems. We study whether a frontier large language model, used as a coding agent with open-source tools only, can match them in quality and speed. We report every run, and independent checkers verify every schedule. On the 100,000-operation job shop tai_100_1000_1, an agent-written solver reached 525,515, below OptalCP, Hexaly, and CP Optimizer. Unchanged, it improved all ten instances of the family and closed two. With equal budgets on the same workstation, it ended 0.0-1.8% above the lower bound, against 2.6-5.8% for CP Optimizer and 2.4-4.4% for Hexaly. On the Behnke-Geiger flexible job shops, an agent-written tabu search improved 11 of 32 open instances. With two transport robots, an agent-written solver improved seven of ten MKT instances. New lower bounds show that four published MKT values cannot be attained on the distributed instance files. Agent-run improvement campaigns closed eight further instances.
Figures & tables
Problem
Instance(s)
Jobs
Machines
Operations
LB / UB
Status
Job shop
tai_100_1000_1
100
1,000
100,000
522,298 / 533,080
open
Flexible job shop
behnke16
100
20
500
391 / 412
open
behnke14
50
20
250
221 / 230
open
behnke31
50
40
250
226 / 226
closed ∗
Flexible job shop, 2 AGVs
MKT01–MKT10
10–20
4–15
55–240
e.g. MKT10: 386.8 / 525
open
21 Chambers–Barnes
10–15
11–18
100–225
see Table 9
7 open
Table 1: Selected instances
Figure 1: Framework of the study
Item
Value
Agent
Claude Code ( Anthropic, 2026a ) , version 2.1, in all sessions
Models of record
claude-opus-5 (Claude Opus 5) and claude-sonnet-5 (Claude Sonnet 5): job shop and flexible job shop, accessed 5–10 August 2026; claude-opus-5-5 (Claude Opus 5.5): transport robots, accessed 25–26 September 2026, and job shop in mode C, 19–20 October 2026; claude-fable-5-1 (Claude Fable 5.1): flexible job shop in mode C, 19–20 October 2026. Public release ( Anthropic, 2026b ) : Claude Sonnet 5, 30 June 2026; Claude Opus 5, 24 July 2026; Claude Fable 5.1, 1 September 2026; Claude Opus 5.5, 22 September 2026. Default decoding settings of Claude Code; the provider does not expose sampling seeds.
Autonomous runs
Harbor task framework ( Harbor Framework, 2026 ) ; one Docker container per run; quota of 4 CPUs (three runs: 8 CPUs) and 4 GB of memory, although the container reported the 32 hardware threads of the host; budget 18,000 s (5 h)
Container software
Python 3.12.3, GCC 13.3.0, NumPy 2.4.6; OR-Tools only if the agent installed it
Developing optimization models for production scheduling requires substantial expert effort. Research on large language models (LLMs) has followed two directions: specialized approaches for automated modeling, mostly for mixed-integer linear programming, which often rely on dedicated training or problem-specific architectures that limit industrial deployment; and agentic artificial intelligence for operational decision support, which generally assumes that the optimization model already exists. This study bridges both directions by assessing whether general-purpose LLMs, orchestrated as agents without task-specific training, can formulate and implement constraint programming models from natural-language problem descriptions. Singleagent and multi-agent architectures are integrated with a Model Context Protocol server that provides context-aware retrieval of solver documentation to mitigate hallucinations during implementation. Both are compared with a direct LLM baseline on six industry-oriented problems covering flow-shop, job-shop, flexible job-shop and resource-constrained warehouse scheduling, using three LLMs and assessing modeling accuracy, execution success, latency and token consumption. Formulation proves largely within reach of current LLMs, whereas implementation is the main barrier. The multi-agent workflow raises the share of scripts that run correctly as generated from 14.8% with a direct LLM call to 59.3%, reaching 80.6% on the four less complex problems, while tightly coupled intralogistics models remain an open challenge.
Ángel Sánchez-Fernández, Javier Pernas-Álvarez, Diego Crespo-Pereira
Universidade da Coru˜na, Campus Industrial de Ferrol, CITENI, Grupo Integrado de Ingenier´ıa, Esteiro s/n, Ferrol, 15403.
Large language models are increasingly deployed as autonomous agents for multi-step tasks in executable environments, yet their ability to perform realistic operations research (OR) work remains unclear. Existing OR evaluations often decouple modeling from solving, rely on pre-formalized or text-only instances, and rarely test the full workflow from operational artifacts to validated decisions. In this work, we introduce ORAgentBench, an execution-grounded benchmark for evaluating autonomous agents on challenging end-to-end operations research tasks. It contains 107 human-reviewed tasks across diverse operational scenarios, each packaged in an isolated environment with a natural-language brief, multi-file data, configuration artifacts, and a required submission schema. Agents must write and run solution code, and their submissions are evaluated by hidden validators for schema validity, hard-constraint feasibility, and normalized objective quality. Experiments with fourteen frontier agent-model configurations show that current agents remain far from reliable OR practice. The best agent passes only 35.51% of all tasks and 20.59% of hard tasks, and many feasible submissions still fall below the required quality threshold. Failure analysis further shows that errors are dominated by strategic weaknesses, including missed operational rules, brittle formulations, weak feasible-solution construction, and insufficient solution improvement. OR-specific procedural skills increase hard-task feasibility, but do not reliably improve solution quality or pass rate. These results suggest that progress in OR agents requires moving beyond plausible optimization code toward dependable, high-quality operational decision-making.
Jiajun Li, Mingshu Cai, Yixuan Li +5
School of Computer Science and Engineering, Southeast University · Waseda University · Nanyang Technological University +1
Many optimization problems are solved repeatedly on instances drawn from the same underlying distribution. In this setting, a system can begin with a general-purpose solver and use experience from previous instances to learn a cheaper way to solve future ones. We formalize this as distribution-aware programming: samples from an unknown deployment distribution are used to produce executable solver code whose quality and runtime generalize to new instances. A simple analysis shows how sample access interpolates between distribution-oblivious and distribution-informed algorithm design, and when the offline cost of specialization is recovered through lower deployment cost. We instantiate this framework with an LLM agent that proposes structural hypotheses, analyzes training instances, and synthesizes specialized solver code; the LLM is used only before deployment. Across 21 structured combinatorial-optimization distributions, the synthesized solvers achieve high quality while often replacing generic search or optimization with smaller distribution-specific computations. Against released PACE competition solvers, our method remains competitive while using substantially less runtime: 75--125× less on PACE 2025 Dominating Set, 80--96× less on Hitting Set, and more than 34,000× less on the PACE 2024 OCM exact track. More broadly, the results suggest using AI not only to solve optimization problems, but to learn how recurring distributions should be solved.