Riepilogo Tecnico: DynaSchedBench

Enunciato del Problema

Il campo dell'Ottimizzazione Combinatoria Neurale (NCO) per il Problema di Programmazione Dinamica e Flessibile dei Laboratori (DFJSP) affronta una tensione metodologica che ostacola i progressi. I benchmark statici esistenti (ad esempio, Taillard, DMU) incoraggiano l'overfitting, dove gli agenti memorizzano strutture di istanza specifiche anziché apprendere politiche generalizzabili. Al contrario, i tentativi di generare istanze dinamiche spesso si basano su campionamento procedurale non calibrato, dove la difficoltà emerge come un sottoprodotto non controllato dei semi casuali. Ciò introduce una "nebbia stocastica" ad alta varianza, rendendo impossibile distinguere l'innovazione algoritmica genuina da sequenze favorevoli di eventi dinamici. Inoltre, l'emergere dei Modelli Linguistici su Larga Scala (LLM) come agenti di schedulazione manca di un quadro di valutazione rigoroso per testare le loro capacità di ragionamento contro solutori consolidati in un ambiente controllato e distribuzionalmente valido.

Metodologia: Framework DynaSchedBench

Gli autori introducono DynaSchedBench, un quadro diagnostico progettato per generare istanze di benchmark calibrate e teoricamente fondate per il DFJSP. Il framework è composto da quattro componenti principali:

1. Calibratore dello Spazio degli Eventi Sequenziali (SESC)

Invece di ottimizzare gli iperparametri generativi in uno spazio dei parametri (che è computazionalmente costoso e soggetto a instabilità), DynaSchedBench impiega il SESC. Questo modulo opera direttamente sul flusso di eventi discreti realizzato $E$. Applica una sequenza di trasformazioni strutturali locali (operatori) per adattare il flusso di eventi ai metrici target.

• Strategie di Aggiustamento: Il framework utilizza un catalogo di strategie che include aggiustamento della struttura di arrivo (correzione del tasso, risampionamento di rinnovo), scalatura adattiva del margine (modifica della rigidità delle date di scadenza), risampionamento isomorfo dei tempi di elaborazione (correzione della variabilità preservando il carico di lavoro totale) e ingegneria dei colli di bottiglia (controllo granulare sulla perdita di capacità).
• Ciclo di Calibrazione: Una ricerca greedy seleziona gli operatori che minimizzano il vettore di errore normalizzato tra i metrici osservati e i metrici target, preservando al contempo i metrici già entro la tolleranza.

2. Indice di Stress della Programmazione (SSI)

Per quantificare la difficoltà dell'istanza, gli autori propongono l'Indice di Stress della Programmazione (SSI). Questa metrica mappa i metrici empirici grezzi in un vettore di difficoltà a quattro componenti:

• Congestione ($C$): Basata su approssimazioni del traffico intenso in stile Kingman, utilizzando l'utilizzo e la variabilità naturali del collo di bottiglia.
• Pressione Temporale ($P$): L'inverso del margine empirico.
• Complessità Strutturale ($K$): Una misura normalizzata del numero di macchine e della profondità delle operazioni.
• Intensità di Interruzione ($S$): Una misura normalizzata dei rapporti di disturbo realizzati (ad esempio, guasti).
  Queste componenti vengono compresse in scala logaritmica e mediate per produrre un punteggio di difficoltà scalare $d \in [0, 100]$.

3. Stack di Simulazione e Valutazione Modulare

Il framework fornisce un ambiente compatibile con Gym con:

• Simulazione basata su Snapshot: Garantisce osservazioni immutabili per gli agenti, supportando sia politiche senza memoria che pianificatori con lookahead.
• Motore basato su Traiettorie: Mantiene le tracce di esecuzione per la verifica riproducibile dei vincoli (precedenza, sovrapposizione nulla delle risorse) e il calcolo delle metriche di prestazione.
• Livelli di Osservabilità: Definisce tre livelli di accesso alle informazioni per gli agenti:
  • L1: Vista locale (lavori pronti, disponibilità delle macchine).
  • L2: L1 + statistiche locali (lunghezze delle code, fattori di margine).
  • L3: L2 + priori strutturali (punteggi dei colli di bottiglia, obiettivi di progettazione).

4. Valutazione degli Agenti LLM

Il framework valuta gli agenti basati su LLM utilizzando varie modalità di prompting (Diretto, Catena di Pensiero, Potenziato da Strumenti) e strategie di raffinamento (Riflessione, Best-of-N). Misura le prestazioni attraverso il makespan normalizzato ($C_{max}$) rispetto alla migliore schedulazione osservata e traccia il consumo di token per valutare i compromessi costo-prestazioni.

Risultati Chiave

Prestazioni di Calibrazione

• Efficienza e Stabilità: Il SESC supera significativamente le basi evolutive (Ottimizzazione Multi-Obiettivo e approcci Ibridi) in termini di efficienza computazionale e stabilità. Il SESC raggiunge un tempo di esecuzione mediano di calibrazione di 0,2 secondi rispetto a 57,9 secondi per MOO e 185,8 secondi per Ibrido.
• Accuratezza: Il SESC dimostra una stabilità algoritmica superiore con una perdita normalizzata media inferiore ($\tilde{\ell}_2 \approx 0,0539$) e una dispersione minima da seme a seme rispetto alle basi.
• Correlazione con la Difficoltà: Il punteggio SSI è positivamente correlato al divario di schedulazione tra un programmatore casuale e la migliore euristica fissa ($\rho = 0,563$), validando la sua utilità come proxy per la difficoltà di schedulazione.

Risultati sulla Schedulazione con LLM

• Il Paradosso dell'Osservabilità: Fornire agli agenti priori strutturali completi (L3) degrada le prestazioni rispetto a sintesi statistiche concise (L2). Gli agenti CoT L2 hanno raggiunto un makespan eccessivo normalizzato medio dello 0,7%, mentre gli agenti CoT L3 sono degradati all'1,66%. Ciò suggerisce che gli attuali LLM faticano a distillare segnali utili dal rumore strutturale ad alta dimensionalità.
• Inefficienza della Sondatura Attiva: Le strategie potenziate da strumenti (L1+Strumento) hanno comportato un aumento triplo del consumo di token senza migliorare le prestazioni rispetto al CoT L1 standard, evidenziando un "collo di bottiglia nell'integrazione delle informazioni".
• Parità con le Euristichhe: Nonostante un sostanziale sovraccarico di token e strategie di ragionamento avanzate (Riflessione, Best-of-N), gli LLM non riescono a superare costantemente le forti Regole di Spedizione per Priorità (PDR) create manualmente. I migliori LLM (ad esempio, Qwen3-8B) hanno prestazioni statisticamente indistinguibili dalle migliori euristichhe fisse (ad esempio, LIFO+LIT), caratterizzandoli come approssimatori euristici robusti piuttosto che ottimizzatori superiori.

Significato e Affermazioni

Il documento afferma di risolvere la crisi di valutazione nella schedulazione dinamica fornendo un quadro principiato per generare benchmark controllati distribuzionalmente. Il suo significato principale risiede in:

1. Rigor Metodologico: Sostituire il campionamento non calibrato con un processo di calibrazione deterministico nello spazio degli eventi che consente la stratificazione sistematica della difficoltà dell'istanza.
2. Insight Diagnostico: Scoprire il "Paradosso dell'Osservabilità", che sfida l'assunzione secondo cui più informazioni (priori strutturali) portano a una migliore presa di decisioni negli agenti basati su LLM per problemi combinatori.
3. Aspettative Realistiche: Stabilire che gli attuali LLM, anche con prompting avanzato e uso di strumenti, agiscono principalmente come approssimatori robusti di euristichhe classiche piuttosto che come ottimizzatori trasformativi, suggerendo la necessità di orientare la ricerca verso la pianificazione di traiettorie multi-step piuttosto che verso la spedizione reattiva.

Gli autori concludono che, senza tali ambienti calibrati, il campo non può valutare in modo affidabile le capacità di ragionamento degli agenti emergenti e che la generazione attuale di LLM è limitata dal tetto di prestazioni delle euristichhe classiche nei contesti di schedulazione dinamica.