DynaSchedBench: Calibrated Dynamic Scheduling Benchmarks and Observability Limits of LLM Agents

Forum topic · 小凯 · 2026-05-29

Summary

DynaSchedBench (arXiv:2605.27566) is a diagnostic benchmark framework for neural combinatorial optimization on the Dynamic Flexible Job Shop Scheduling Problem (DFJSP). It addresses a methodological tension: static benchmarks encourage overfitting, while uncalibrated generators obscure algorithmic capability with random noise. Instead of parameter sampling, the framework uses a Sequential Event-Space Calibrator (SESC) that computes a novel Schedule Stress Index (SSI) to stratify instances by difficulty. SESC converges reliably to target metrics while being substantially more computationally efficient than evolutionary baselines. Built on this calibrated environment—with modular components for instance generation, snapshot-based simulation, agents, evaluation, and visualization—the study reveals key limitations of LLM scheduling agents: an "observability paradox" in stepwise online dynamic scheduling, where giving agents complete structural information degrades policy performance while concise information works better. Despite heavy token usage, tool augmentation and refinement strategies fail to reliably improve results, and most LLM agents cannot consistently outperform strong heuristic baselines.

Paper Overview

Field: AI / neural combinatorial optimization
Authors: Shijie Cao, Yuan Yuan, Jing Liu
arXiv: 2605.27566

Abstract (translated summary)

Progress in neural combinatorial optimization for the Dynamic Flexible Job Shop Scheduling Problem (DFJSP) is currently hindered by a methodological tension: static benchmarks encourage benchmark overfitting, while uncalibrated generators obscure algorithmic capability with stochastic noise.

To resolve this, the authors introduce DynaSchedBench, a diagnostic framework for DFJSP that rigorously controls the instance-generation process. Instead of relying on parameter sampling, the approach utilizes a Sequential Event-Space Calibrator (SESC) that computes a novel Schedule Stress Index (SSI) to stratify instances by difficulty. SESC is substantially more computationally efficient than evolutionary baselines while converging reliably to the target metrics.

The framework integrates modular components for instance generation, snapshot-based simulation, agents, evaluation, and visualization.

Key Findings

Calibrated difficulty control: SESC reliably targets the desired SSI levels, enabling difficulty-stratified evaluation rather than noisy random instance generation.
Observability paradox: In stepwise online decision-making for dynamic scheduling, giving LLM agents full structural information actually *degrades* policy performance; concise information performs better.
Tool augmentation underperforms: Despite consuming large token budgets, tool-augmented and refinement strategies do not reliably improve scheduling performance.
LLM agents vs. heuristics: Most LLM scheduling agents fail to consistently surpass strong heuristic baselines.