Low-Cost Labels, Reliable Choices: Rollout-Calibrated Hyper-Heuristics for Job Shop Scheduling

Technische Samenvatting: Goedkope Labels, Betrouwbare Keuzes

Probleemstelling
Het artikel behandelt het Job Shop Scheduling Problem (JSSP) door de lens van selectie-hyperheuristieken. Hoewel leerondersteunde hyperheuristieken een middenweg bieden tussen vaste dispatchingregels en volledig geleerde constructoren door haalbaarheid en interpreteerbaarheid te behouden, staan ze voor twee hoofdflessenhals:

1. Kosten van labelgeneratie: Toezichtgeleerd leren vereist labels die worden gegenereerd door kandidaat-dispatchingregels te "rollen" van een gedeeltelijke planning naar een eindtoestand. Een volledige rollout voor elke kandidaatregel op elk beslispunt brengt een rekenkosten met zich mee van $O(|H|T)$, waarbij $|H|$ het aantal regels is en $T$ het aantal resterende beslissingen.
2. Betrouwbaarheid van selectie: Een geleerde selector kan per ongeluk een lichte verbetering voorspellen ten opzichte van een sterke standaardregel vanwege ruis of overfitting. Het blind volgen van de laagste voorspelde score kan leiden tot prestatiedegradeatie in vergelijking met een robuuste vaste regel.

De auteurs beogen de afweging te bestuderen tussen de kosten van het genereren van deze toezichtlabels en de betrouwbaarheid van de resulterende selector, met name gericht op het voorkomen dat een geleerd model afwijkt van een sterke standaardregel tenzij de voorspelde winst geloofwaardig is.

Methodologie
De voorgestelde aanpak, genaamd Rollout-gekalibreerde Hyperheuristieken, integreert drie kerncomponenten:

1. Regret-genormaliseerde Rollout-Labels:
   In plaats van ruwe makespan of ondergrens-genormaliseerde makespan als doel te gebruiken, definiëren de auteurs een per-toestand regret-label:
   $$r(s, h) = \frac{m(s, h) - \min_{h' \in H_s} m(s, h')}{\min_{h' \in H_s} m(s, h')}$$
   waarbij $m(s, h)$ de makespan is die resulteert uit het toepassen van regel $h$ in toestand $s$. Dit transformeert het doel naar een lokaal rangschikkingssein waarbij de beste regel in een specifieke toestand een regret van 0 heeft, waardoor de relatieve prestatie van regels binnen die specifieke context wordt geïsoleerd.

2. Onzekerheids-gestuurde Selectie:
   Het systeem maakt gebruik van een contextuele K-Nearest Neighbors (KNN) regressor om de regret voor elke kandidaatregel te voorspellen. Om betrouwbaarheid te waarborgen, wordt een sturingsmechanisme (gating mechanism) geïntroduceerd. De selector schakelt alleen over van een vaste standaardregel ($h_0$, gekozen als de beste vaste regel op de trainingsset) naar een voorspelde beste regel ($h^*$) als de verwachte verbetering een onzekerheid-gecorrigeerde marge overschrijdt:
   $$\pi_{gated}(s) = \begin{cases} h^* & \text{als } \hat{r}(s, h_0) - \hat{r}(s, h^*) > \lambda \hat{\sigma}(s, h^*) \\ h_0 & \text{anders} \end{cases}$$
   Hierbij is $\hat{\sigma}$ de standaardafwijking van de $k$-naaste buren (dienend als een schatting van onzekerheid), en $\lambda$ een hyperparameter die de agressiviteit van de omschakeling regelt.

3. Rollout-budget Afweging:
   De auteurs variëren expliciet de rollout-breedte ($b$, het aantal geëvalueerde kandidaatregels) en de rollout-diepte ($\kappa$, het aantal stappen dat een kandidaatregel wordt gevolgd voordat er wordt teruggekeerd naar de standaard) om de Pareto-grens te mappen tussen de kosten van labelgeneratie (simulatiestappen/wall-clock tijd) en de uiteindelijke testprestaties (Relative Percentage Deviation, RPD).

Belangrijkste Bijdragen

• Een Conservatief Selectieframework: Het artikel stelt een sturingsmechanisme voor dat prioriteit geeft aan betrouwbaarheid boven agressieve optimalisatie, zodat de geleerde selector sterke vaste regels niet verlaat zonder hoge zekerheid.
• Regret-gebaseerd Toezicht: Door per-toestand regret in plaats van absolute makespan te gebruiken, richt de methode zich op lokale regelrangschikking, wat robuuster is voor besluitvorming in gedeeltelijke planningen.
• Expliciete Kosten-Kwaliteit Analyse: In tegenstelling tot veel werken die labelgeneratie behandelen als een vaste voorverwerkingsstap, varieert deze studie systematisch de rollout-diepte en -breedte om de kosten-kwaliteit afweging te kwantificeren, waardoor praktische richtlijnen worden geboden voor implementatiebudgetten.
• CPU-only Reproduceerbaarheid: De volledige pijplijn, inclusief labelgeneratie, KNN-aanpassing en inferentie, is ontworpen om op CPU's te draaien zonder GPU-versnelling, in contrast met diepe versterkingsleerbenaderingen.

Experimentele Resultaten
Experimenten werden uitgevoerd op synthetische JSSP-instanties van de maten $6\times6$, $10\times10$ en $15\times10$.

• Prestaties: De Regret-gated selector behaalde de laagste gemiddelde RPD onder alle geleerde methoden over alle schalen. Deze bleef zeer dicht bij de beste vaste dispatchingregel (meestal FIFO of MOPNR in deze synthetische instellingen), met gemiddelde RPD-gaten van respectievelijk 0,70, 0,67 en 0,06.
• Robuustheid: De gated-aanpak verlaagde de gemiddelde RPD van een Random-HH-baseline met meer dan een orde van grootte (van ~36–54% naar ~0,8–2,8%).
• Ablatie: De studie bevestigde dat gating stabieler is dan altijd overschakelen (argmin-selectie). De beste resultaten werden behaald met regret-labels en een zekerheidsdrempel $\lambda=1.0$. Varianten met Lower Confidence Bound (LCB) presteerden slechter, wat suggereert dat onzekerheid beter wordt gebruikt als een schakeltest dan als een directe scorebonus.
• Kostenanalyse: Volledige rollouts ($\kappa=\infty, b=|H|$) leverden de beste kwaliteit op, maar tegen de hoogste kosten. Ondiepe rollouts ($\kappa=1$) resulteerden in aanzienlijk hogere RPD. Intermediaire dieptes boden een levensvatbare afweging, waarbij het aantal simulatiestappen aanzienlijk werd verminderd terwijl de aanvaardbare kwaliteit werd behouden.

Betekenis en Claims
Het artikel bescheiden claimt een reproduceerbaar, CPU-only selector en evaluatieprotocol te bieden voor het bestuderen van labelkosten en conservatief schakelen in leerondersteunde hyperheuristieken.

De auteurs positioneren hun werk als complementair aan gespecialiseerde oplossers, deep-RL dispatchers (zoals L2D, ScheduleNet) en LLM-gedreven programmazoekopdrachten (zoals FunSearch, ReEvo). Terwijl die systemen verschillende punten in de ontwerpruimte targeten (vaak het uitvinden van nieuwe operatoren of end-to-end beleidslijnen), isoleert dit werk het probleem van het selecteren uit bestaande, interpreteerbare regels.

De primaire betekenis ligt in het adresseren van de praktische implementatieuitdaging: hoeveel simulatiebudget moet worden besteed aan het genereren van labels, en hoe kan worden gegarandeerd dat een geleerde selector de prestaties niet degradeert door te vaak te schakelen. De auteurs merken op dat hun bevindingen specifiek zijn voor de geteste synthetische, statische en deterministische regimes. Zij erkennen dat schalen naar industriële instanties of dynamische omgevingen (bijvoorbeeld machinestoringen, online aankomsten) andere kosten-kwaliteit afwegingen en mogelijk andere dynamieken voor labelgeneratie zou vereisen. Het werk claimt niet het JSSP algemeen op te lossen, maar biedt eerder een gecontroleerde studie om leerondersteunde hyperheuristieken betrouwbaar en kosteneffectief te maken.