🤖 AI

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

This paper introduces DynaSchedBench, a calibrated benchmarking framework for Dynamic Flexible Job Shop Scheduling that utilizes a Sequential Event-Space Calibrator to generate rigorously controlled instances, revealing an "Observability Paradox" where full information access and tool-augmentation often degrade LLM-based agent performance, causing them to underperform strong dispatching baselines.

Original authors: Shijie Cao, Yuan Yuan, Jing Liu

Published 2026-05-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Shijie Cao, Yuan Yuan, Jing Liu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to manage a busy factory floor where machines break down, new orders arrive randomly, and deadlines keep shifting. This is called Dynamic Flexible Job Shop Scheduling.

The paper argues that we've been trying to teach these robots using the wrong kind of "practice tests." Here is a breakdown of their new approach and what they discovered, using simple analogies.

1. The Problem: Bad Practice Tests

Currently, researchers test scheduling AI on two types of problems:

Static Benchmarks: These are like giving a student a fixed list of 50 math problems. The student might just memorize the answers to those specific 50 problems rather than learning how to do math. When they face a new problem, they fail.
Random Generators: Others try to create infinite random problems. But this is like rolling dice to create a test. Sometimes the dice roll a "super easy" test by luck, and the AI looks smart. Other times, it rolls a "super hard" test, and the AI looks dumb. You can't tell if the AI is actually good or just lucky/unlucky.

The Result: We don't know if the AI is truly smart or just memorizing the test or getting lucky with the dice.

2. The Solution: DynaSchedBench (The "Calibrated Gym")

The authors built a new framework called DynaSchedBench. Think of this as a smart gym for scheduling robots.

Instead of just rolling dice, they use a special tool called the Sequential Event-Space Calibrator (SESC).

How it works: Imagine you want to test a runner's speed on a track with a specific amount of wind resistance. Instead of hoping the wind blows just right, this tool adjusts the wind machine until the resistance is exactly what you asked for.
The "Stress Index" (SSI): They created a "difficulty score" (like a video game level). They can now generate a "Level 5" problem that is guaranteed to be harder than a "Level 4" problem, but easier than a "Level 6" one. This removes the luck factor.

3. The Big Discovery: The "Observability Paradox"

The researchers tested Large Language Models (LLMs)—the same kind of AI that writes essays and chats with you—to see if they could act as the factory manager. They gave the AI three different ways to "see" the factory:

Level 1 (The Local View): "Here is the machine right in front of you. It's free. Do you want to use it?" (Simple facts).
Level 2 (The Stats View): "Here is the machine, plus a summary of how busy the whole factory is." (Simple facts + a dashboard).
Level 3 (The Oracle View): "Here is the machine, the dashboard, AND the secret blueprint of the factory, the future schedule, and the hidden bottlenecks." (Everything).

The Surprise:
You would think giving the AI more information (Level 3) would make it smarter. It didn't.

The AI performed best with the simple dashboard (Level 2).
When given the "Oracle" view with all the complex blueprints (Level 3), the AI actually got worse.

The Analogy: Imagine you are driving a car.

Level 2 is looking at the road and your speedometer. You drive well.
Level 3 is giving you the entire traffic report, the weather patterns for the next week, the engine's internal temperature, and the GPS history of every car on the road.
The Paradox: The extra data overwhelmed the driver. They got confused by the noise and made worse decisions than if they had just looked at the road. The paper calls this the "Observability Paradox."

4. The "Tool" Trap

They also tried giving the AI special tools to "simulate" what would happen if it made a move (like a chess computer looking ahead).

The Result: Using these tools cost a lot of "tokens" (computing power/money) but didn't actually make the AI any better at scheduling. It was like paying for a fancy GPS that just gave you the same directions you could have guessed yourself.

5. The Final Verdict: Good at Guessing, Bad at Optimizing

The paper concludes that current AI scheduling agents are not super-optimizers.

They are robust approximators. This means they are good at making "safe," decent guesses that are almost as good as a human expert's quick rule-of-thumb.
They cannot consistently beat the best traditional, hand-crafted rules (heuristics). They are stuck in a "performance ceiling."

Summary

The paper says: "Stop testing AI on random or memorized problems. Use our new 'Calibrated Gym' to test them fairly. When you do, you'll find that giving AI too much information actually confuses them, and they are currently just very good guessers, not geniuses."

Technical Summary: DynaSchedBench

Problem Statement

The field of Neural Combinatorial Optimization (NCO) for the Dynamic Flexible Job Shop Scheduling Problem (DFJSP) faces a methodological tension that hinders progress. Existing static benchmarks (e.g., Taillard, DMU) encourage overfitting, where agents memorize specific instance structures rather than learning generalizable policies. Conversely, attempts to generate dynamic instances often rely on uncalibrated procedural sampling, where difficulty emerges as an uncontrolled byproduct of random seeds. This introduces high-variance "stochastic fog," making it impossible to distinguish genuine algorithmic innovation from favorable sequences of dynamic events. Furthermore, the emergence of Large Language Models (LLMs) as scheduling agents lacks a rigorous evaluation framework to test their reasoning capabilities against established solvers in a controlled, distributionally sound environment.

Methodology: DynaSchedBench Framework

The authors introduce DynaSchedBench, a diagnostic framework designed to generate calibrated, theoretically grounded benchmark instances for DFJSP. The framework consists of four core components:

1. Sequential Event-Space Calibrator (SESC)

Instead of optimizing generative hyperparameters in a parameter space (which is computationally expensive and prone to instability), DynaSchedBench employs SESC. This module operates directly on the realized discrete-event stream $E$ . It applies a sequence of local structural transformations (operators) to adjust the event stream to match target metrics.

Adjustment Strategies: The framework utilizes a catalog of strategies including Arrival-structure adjustment (rate correction, renewal resampling), Adaptive slack scaling (modifying due-date tightness), Isomorphic processing-time resampling (correcting variability while preserving total workload), and Bottleneck engineering (fine-grained control over capacity loss).
Calibration Loop: A greedy search selects operators that minimize the normalized error vector between observed metrics and target metrics while preserving metrics already within tolerance.

2. Schedule Stress Index (SSI)

To quantify instance difficulty, the authors propose the Schedule Stress Index (SSI). This metric maps raw empirical metrics into a four-component difficulty vector:

Congestion ( $C$ ): Based on Kingman-style heavy-traffic approximations, utilizing natural bottleneck utilization and variability.
Time Pressure ( $P$ ): The inverse of empirical slack.
Structural Complexity ( $K$ ): A normalized measure of machine count and operation depth.
Disruption Intensity ( $S$ ): A normalized measure of realized disturbance ratios (e.g., breakdowns).
These components are log-compressed and averaged to produce a scalar difficulty score $d \in [0, 100]$ .

3. Modular Simulation and Evaluation Stack

The framework provides a Gym-compatible environment with:

Snapshot-based Simulation: Ensures immutable observations for agents, supporting both memoryless policies and lookahead planners.
Trajectory-based Engine: Persists execution traces for reproducible constraint verification (precedence, resource non-overlapping) and performance metric computation.
Observability Levels: Defines three levels of information access for agents:
- L1: Local view (ready jobs, machine availability).
- L2: L1 + local statistics (queue lengths, slack factors).
- L3: L2 + structural priors (bottleneck scores, design targets).

4. LLM Agent Evaluation

The framework evaluates LLM-based agents using various prompting modes (Direct, Chain-of-Thought, Tool-augmented) and refinement strategies (Reflection, Best-of-N). It measures performance via normalized makespan ( $C_{max}$ ) relative to the best observed schedule and tracks token consumption to assess cost-performance trade-offs.

Key Results

Calibration Performance

Efficiency and Stability: SESC significantly outperforms evolutionary baselines (Multi-Objective Optimization and Hybrid approaches) in computational efficiency and stability. SESC achieves a median calibration runtime of 0.2 seconds compared to 57.9 seconds for MOO and 185.8 seconds for Hybrid.
Accuracy: SESC demonstrates superior algorithmic stability with lower mean normalized loss ( $\tilde{\ell}_2 \approx 0.0539$ ) and minimal seed-to-seed dispersion compared to baselines.
Difficulty Correlation: The SSI score is positively correlated with the scheduling gap between a random scheduler and the best fixed heuristic ( $\rho = 0.563$ ), validating its utility as a proxy for scheduling difficulty.

LLM Scheduling Findings

The Observability Paradox: Providing agents with full structural priors (L3) degrades performance compared to concise statistical summaries (L2). L2 CoT agents achieved a mean normalized excess makespan of 0.7%, whereas L3 CoT agents degraded to 1.66%. This suggests current LLMs struggle to distill useful signals from high-dimensional structural noise.
Inefficiency of Active Probing: Tool-augmented strategies (L1+Tool) incurred a three-fold increase in token consumption without improving performance over standard L1 CoT, highlighting an "information integration bottleneck."
Heuristic Parity: Despite substantial token overhead and advanced reasoning strategies (Reflection, Best-of-N), LLMs fail to consistently surpass strong, hand-crafted Priority Dispatching Rules (PDRs). Top LLMs (e.g., Qwen3-8B) performed statistically indistinguishably from the best fixed heuristics (e.g., LIFO+LIT), characterizing them as robust heuristic approximators rather than superior optimizers.

Significance and Claims

The paper claims to resolve the evaluation crisis in dynamic scheduling by providing a principled framework for generating distributionally controlled benchmarks. Its primary significance lies in:

Methodological Rigor: Replacing uncalibrated sampling with a deterministic, event-space calibration process that allows for the systematic stratification of instance difficulty.
Diagnostic Insight: Uncovering the "Observability Paradox," which challenges the assumption that more information (structural priors) leads to better decision-making in LLM-based agents for combinatorial problems.
Realistic Expectations: Establishing that current LLMs, even with advanced prompting and tool use, act primarily as robust approximators of classical heuristics rather than transformative optimizers, suggesting a need to pivot research toward multi-step trajectory planning rather than reactive dispatching.

The authors conclude that without such calibrated environments, the field cannot reliably benchmark the reasoning capabilities of emerging agents, and that the current generation of LLMs is bounded by the performance ceiling of classical heuristics in dynamic scheduling contexts.