Agent-written heuristics versus commercial solvers on unsolved job-shop benchmark instances

Andre Albrecht, Enzo Morosini Frazzon, Leandro C. Coelho, Bruno VieiraarXiv 2026 · arXiv

TL;DR

Researchers have demonstrated that a frontier LLM (Claude Code), acting as an autonomous coding agent, can design custom heuristics that outperform top-tier commercial solvers like Hexaly and IBM ILOG CP Optimizer on massive, unsolved job-shop scheduling benchmarks. By using only open-source tools and its own generated C++/Python code, the agent improved best-known solutions for dozens of instances and closed several long-standing open problems to optimality.

What Problem Does This Paper Address?

Scheduling problems—like the Job-Shop Scheduling Problem (JSP) and its flexible variants—are the bread and butter of manufacturing and logistics. They are also notoriously NP-hard. While commercial solvers are the industry standard, they are expensive and can struggle with "mega-instances" (e.g., 100,000 operations) where general-purpose algorithms fail to exploit specific problem structures.

The authors ask a provocative question: Can an LLM coding agent, given only the problem description and open-source libraries, replace the "expert human in the loop" to design, implement, and run specialized optimization heuristics that beat the best commercial tools?

Methods

The study employed Claude Code (using models like Claude 3.5 Sonnet and Opus) as an autonomous agent. The framework, illustrated in Figure 1, follows an iterative loop: the agent analyzes the instance, writes optimization code (often in C++ for speed), compiles and runs it, evaluates the output, and refines its strategy.

Figure 1. Framework of the study

The researchers tested three modes of interaction:

  • Mode A (Agent as Solver): The agent works autonomously to find a schedule for a single instance.
  • Mode B (Agent as Author): The agent writes a reusable solver (e.g., a Tabu Search or a "corridor" search) that can be applied to similar instances.
  • Mode C (Agent as Campaigner): The agent coordinates a long-running improvement campaign, merging different solvers and tuning parameters without human intervention.

Crucially, the agent only had access to open-source tools like OR-Tools CP-SAT, NumPy, and standard C++ compilers. Every schedule produced was verified by an independent checker to ensure no rules were broken.

Datasets

The study focused on three established, difficult benchmark families (summarized in Figure 2):

  1. Job Shop: The massive tai_100_1000 family (100 jobs, 1,000 machines, 100k operations).
  2. Flexible Job Shop (FJSP): The Behnke–Geiger instances, including many that remained "open" (unsolved to optimality).
  3. FJSP with Transport Robots: The MKT and Chambers–Barnes instances, which add the complexity of moving jobs between machines using AGVs.
Table 1. Selected instances

Key Insights and Ideas

  • Structural Exploitation: Unlike general solvers, the agent analyzed the specific bottlenecks of each instance. For the 100k-operation job shop, it realized machines were idle 90% of the time and developed a "corridor search" that restricted operations to narrow time windows, drastically reducing the search space.
  • Specialization is the Killer App: Commercial solvers must be good at everything. The LLM agent’s strength is its ability to write a hyper-specialized solver for a specific problem structure.
  • Cost-Effectiveness: Developing a custom solver via an LLM session cost roughly $10–$20 in API credits. In contrast, commercial solver licenses can cost hundreds of dollars per user per month.
  • New Lower Bounds: The authors derived new mathematical lower bounds for transport problems, proving that several previously published "best" values were actually impossible to achieve on the standard benchmark files.

Key Results

The agent-written solvers consistently outperformed the baselines. As shown in Figure 4, the agent managed to improve best-known values across all three problem families.

Table 3. All agent runs and re-runs of the agent solvers
  • Job Shop: On the 100,000-operation instance tai_100_1000_1, the agent achieved a gap of only 0.62% from the lower bound, compared to 3.97% for CP Optimizer and 3.31% for Hexaly under the same hardware and time constraints.
  • Closing Instances: The agent closed two previously open job-shop instances and six flexible job-shop instances to optimality.
  • Generalization: A Tabu Search written by the agent for one instance was able to improve 11 out of 32 open Behnke–Geiger instances without any further changes to the code.

Limitations and Future Work

While the results are impressive, the authors note several caveats:

  • Regularity of Benchmarks: Benchmark instances often have a "clean" mathematical structure that LLMs are good at spotting. Real-world industrial data is often messier and may not yield the same "aha!" moments for the agent.
  • Model Dependency: The study focused exclusively on Anthropic’s Claude models. It remains to be seen how other frontier models (like GPT-4o or O1) compare in this specific domain.
  • Human-in-the-loop: While "autonomous" runs were successful, the best results often came from "assisted" runs where humans provided relevant literature or high-level goals.

Future work suggests creating a standardized benchmark specifically for LLM coding agents in optimization to track how these models evolve as "automated experts" in operations research.

Summary updated

Abstract

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.
BibTeX
@misc{albrecht2026agent,
  author = {Andre Albrecht and Enzo Morosini Frazzon and Leandro C. Coelho and Bruno Vieira},
  title = {{Agent-written heuristics versus commercial solvers on unsolved job-shop benchmark instances}},
  year = {2026},
  eprint = {2611.17682},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17682},
}
Figure