Research map / Multi-agent systems and games / LLM agents

DynaSchedBench: Calibrated Dynamic Scheduling Benchmarks and Observability Paradox in LLM-based Scheduling Agents

ICML 2026 · Multi-agent systems and games › LLM agents · approach: Robust and efficient agent execution · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces DynaSchedBench, a calibrated generator (SESC event-space calibrator, Schedule Stress Index) for dynamic flexible job shop benchmarks, and evaluates LLM scheduling agents, finding an "Observability Paradox" and that LLMs only match strong dispatching heuristics.

Problem

Dynamic Flexible Job Shop Scheduling evaluation is hampered by static benchmarks that invite overfitting and uncalibrated stochastic generators whose difficulty is uncontrolled; it is unclear how LLM-based agents compare with classical heuristics under calibrated conditions.

Approach

Calibrate generated dynamic scheduling instances by directly applying greedy, metric-guided transformations to the realized event stream (SESC) rather than sampling generator parameters, and stratify difficulty with a four-component Schedule Stress Index.

Key results

• SESC reaches median L2 calibration error 0.0539 with median runtime 0.2 s, versus 57.9 s for MOO and 185.8 s for Hybrid.
• L2 CoT (observability level 2) achieves mean relative makespan gap 0.65% versus 1.66% for L3 CoT, the Observability Paradox.
• Best LLM (Qwen3-8B, 1.01%) is statistically indistinguishable from the best fixed heuristic LIFO+LIT, with best heuristic at 1.11% mean gap.

Surprising findings

• Providing full structural priors (L3) degrades LLM scheduling performance relative to concise statistical summaries (L2).
• Tool-augmented and reflection strategies consume several times more tokens without reliable gains.

Limitations

• Open-weight models served locally; closed API models evaluated only through APIs with matched prompts; results on a single DFJSP setting.
• Processing SCV calibration remains the hardest metric; SESC failure rate around 40%.
• Strict calibration success only 48% for SESC, comparable to Hybrid.

Experimental setup

Datasets: DynaSched-Grid DynaSched-Sweep DynaSched-Subset Taillard DMU

Benchmarks: DynaSched-Grid DynaSched-Sweep DynaSched-Subset

Metrics: normalized makespan Cmax gap calibration L2 error strict/relaxed calibration success rate runtime total tokens Spearman correlation

Baselines: MOO calibrator (NSGA-II parameter-space) Hybrid calibrator priority dispatching rules (SPT, LPT, FIFO, LIFO, etc.)

Builds on: NSGA-II Kingman heavy-traffic approximation chain-of-thought reflection

Closest papers by meaning

• Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling (ICLR 2025 · similarity 0.86)
• Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling (NeurIPS 2025 · similarity 0.85)
• Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems (AAAI 2025 · similarity 0.84)
• PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (ICML 2026 · similarity 0.84)
• Evaluating Test-Time Scaling of General LLM Agents (NeurIPS 2026 · similarity 0.83)
• Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice (NeurIPS 2026 · similarity 0.83)