Technische Samenvatting: DynaSchedBench

Probleemstelling

Het vakgebied van Neuronale Combinatorische Optimalisatie (NCO) voor het Dynamisch Flexibel Werkplaatsplanningsprobleem (DFJSP) kampt met een methodologische spanning die vooruitgang belemmert. Bestaande statische benchmarks (bijv. Taillard, DMU) stimuleren overfitting, waarbij agenten specifieke instantiestructuren memoriseren in plaats van generaliseerbare beleidsregels te leren. Omgekeerd vertrouwen pogingen om dynamische instanties te genereren vaak op ongekalibreerde procedurale steekproeven, waarbij moeilijkheid ontstaat als een ongecontroleerd nevenproduct van willekeurige zaden. Dit introduceert een hoge-variatie "stochastische mist", waardoor het onmogelijk is om echte algoritmische innovatie te onderscheiden van gunstige reeksen dynamische gebeurtenissen. Bovendien ontbreekt er voor de opkomst van Groot Taalmodellen (LLM's) als planningsagenten een rigoureus evaluatiekader om hun redeneervermogen te toetsen tegen gevestigde oplossingsmethoden in een gecontroleerde, distributief sounde omgeving.

Methodologie: DynaSchedBench Framework

De auteurs introduceren DynaSchedBench, een diagnostisch kader dat is ontworpen om gekalibreerde, theoretisch onderbouwde benchmarkinstanties voor DFJSP te genereren. Het kader bestaat uit vier kerncomponenten:

1. Sequentiële Gebeurtenisruimte-Kalibrator (SESC)

In plaats van generatieve hyperparameters te optimaliseren in een parameterruimte (wat rekenkundig duur en vatbaar voor instabiliteit is), maakt DynaSchedBench gebruik van SESC. Deze module opereert direct op de gerealiseerde discrete-gebeurtenisstroom $E$. Het past een reeks lokale structurele transformaties (operatoren) toe om de gebeurtenisstroom aan te passen aan doelmetrieken.

• Aanpassingsstrategieën: Het kader maakt gebruik van een catalogus van strategieën, waaronder Aanpassing van aankomststructuur (rate-correctie, hernieuwde resampling), Adaptieve slack-schaalvergroting (aanpassen van de strakheid van levertermijnen), Isomorphe verwerkingstijd-resampling (variabiliteit corrigeren terwijl de totale werklast behouden blijft) en Flessenhals-engineering (fijnmazige controle over capaciteitsverlies).
• Kalibratielus: Een greedy-zoekopdracht selecteert operatoren die de genormaliseerde foutvector tussen waargenomen metrieken en doelmetrieken minimaliseren, terwijl metrieken die al binnen de tolerantie vallen behouden blijven.

2. Planning Stress Index (SSI)

Om de moeilijkheidsgraad van instanties te kwantificeren, stellen de auteurs de Planning Stress Index (SSI) voor. Deze metriek mapt ruwe empirische metrieken om naar een viercomponenten-moeilijkheidsvector:

• Congestie ($C$): Gebaseerd op Kingman-achtige benaderingen voor zware verkeerssituaties, met gebruikmaking van natuurlijke bottleneckbenutting en variabiliteit.
• Tijdsdruk ($P$): De inverse van empirische slack.
• Structurele Complexiteit ($K$): Een genormaliseerde maat voor het aantal machines en de diepte van bewerkingen.
• Disruptie-intensiteit ($S$): Een genormaliseerde maat voor gerealiseerde verstoringverhoudingen (bijv. storingen).
  Deze componenten worden log-comprimeerd en gemiddeld om een scalair moeilijkheidsscore $d \in [0, 100]$ te produceren.

3. Modulaire Simulatie- en Evaluatiestapel

Het kader biedt een Gym-compatibele omgeving met:

• Snapshot-gebaseerde simulatie: Zorgt voor onveranderlijke observaties voor agenten, wat zowel geheugenloze beleidsregels als vooruitkijkende planners ondersteunt.
• Traject-gebaseerde engine: Bewaart uitvoeringssporen voor reproduceerbare constraintverificatie (precedentie, niet-overlappende resources) en berekening van prestat metrieken.
• Observatieniveaus: Definieert drie niveaus van informatie-toegang voor agenten:
  • L1: Lokale weergave (klaarstaande taken, machinebeschikbaarheid).
  • L2: L1 + lokale statistieken (wachtrijlengtes, slackfactoren).
  • L3: L2 + structurele priors (bottleneck-scores, ontwerptargets).

4. Evaluatie van LLM-agenten

Het kader evalueert op LLM gebaseerde agenten met behulp van diverse promptmodi (Direct, Chain-of-Thought, Tool-augmented) en verfijningstrategieën (Reflectie, Best-of-N). Het meet prestaties via de genormaliseerde makespan ($C_{max}$) ten opzichte van de beste waargenomen planning en houdt tokenverbruik bij om kosten-prestatie-trade-offs te beoordelen.

Belangrijkste Resultaten

Kalibratieprestaties

• Efficiëntie en Stabiliteit: SESC presteert significant beter dan evolutionaire baselines (Multi-Objective Optimization en Hybride benaderingen) op het gebied van rekenkundige efficiëntie en stabiliteit. SESC bereikt een mediaan kalibratietijd van 0,2 seconden, vergeleken met 57,9 seconden voor MOO en 185,8 seconden voor Hybride.
• Nauwkeurigheid: SESC vertoont superieure algoritmische stabiliteit met een lagere gemiddelde genormaliseerde verlieswaarde ($\tilde{\ell}_2 \approx 0,0539$) en minimale zaad-tot-zaad-dispersie in vergelijking met baselines.
• Moeilijkheidscorrelatie: De SSI-score correleert positief met de planningskloof tussen een willekeurige planner en de beste vaste heuristiek ($\rho = 0,563$), wat de bruikbaarheid ervan als proxy voor planningsmoeilijkheid valideert.

Bevindingen over LLM-planning

• Het Observabiliteitsparadox: Het verstrekken van volledige structurele priors (L3) aan agenten verslechtert de prestaties ten opzichte van beknopte statistische samenvattingen (L2). L2 CoT-agenten behaalden een gemiddelde genormaliseerde excess makespan van 0,7%, terwijl L3 CoT-agenten degradeerden naar 1,66%. Dit suggereert dat huidige LLM's moeite hebben om bruikbare signalen te destilleren uit hoogdimensionale structurele ruis.
• Inefficiëntie van Actieve Probing: Tool-augmented strategieën (L1+Tool) veroorzaakten een drievoudige toename in tokenverbruik zonder de prestaties te verbeteren ten opzichte van standaard L1 CoT, wat wijst op een "informatie-integratiebottleneck".
• Heuristische Pariteit: Ondanks aanzienlijke token-overhead en geavanceerde redeneerstrategieën (Reflectie, Best-of-N) slagen LLM's er niet in om consequent sterke, handgemaakte Prioriteit Dispatching Rules (PDR's) te overtreffen. Top-LLM's (bijv. Qwen3-8B) presteerden statistisch niet onderscheidbaar van de beste vaste heuristieken (bijv. LIFO+LIT), wat hen karakteriseert als robuuste heuristische benaderingen in plaats van superieure optimalisatoren.

Betekenis en Claims

Het artikel claimt de evaluatiecrisis in dynamische planning op te lossen door een principieel kader te bieden voor het genereren van distributief gecontroleerde benchmarks. De primaire betekenis ligt in:

1. Methodologische Strengh: Het vervangen van ongekalibreerde steekproeven door een deterministisch, gebeurtenisruimte-kalibratieproces dat systematische stratificatie van instantiemoeilijkheid mogelijk maakt.
2. Diagnostisch Inzicht: Het blootleggen van het "Observabiliteitsparadox", wat de aanname uitdaagt dat meer informatie (structurele priors) leidt tot betere besluitvorming bij op LLM gebaseerde agenten voor combinatorische problemen.
3. Realistische Verwachtingen: Het vaststellen dat huidige LLM's, zelfs met geavanceerde prompting en toolgebruik, voornamelijk fungeren als robuuste benaderingen van klassieke heuristieken in plaats van transformatieve optimalisatoren, wat suggereert dat onderzoek moet verschuiven naar meervoudige trajectplanning in plaats van reactieve dispatching.

De auteurs concluderen dat zonder dergelijke gekalibreerde omgevingen het vakgebied de redeneervermogens van opkomende agenten niet betrouwbaar kan benchmarken, en dat de huidige generatie LLM's wordt begrensd door het prestatiedak van klassieke heuristieken in dynamische planningscontexten.