RESCHED: Rethinking Flexible Job Shop Scheduling from a Transformer-based Architecture with Simplified States

Dit paper introduceert RESCHED, een minimalistisch deep reinforcement learning-framework dat de Flexible Job Shop Scheduling-problemen oplost door de state-representatie te reduceren tot vier essentiële kenmerken en een aangepaste Transformer-architectuur te gebruiken, wat leidt tot superieure prestaties en betere generalisatie dan bestaande methoden.

De kern

RESCHED: Een Slimme Chef die de Keuken in Orde Houdt

Stel je een enorme, drukke keuken voor. Je hebt veel verschillende gerechten (de jobs) die elk uit meerdere stappen bestaan (de operaties). Je hebt ook een team van koks (de machines). Het probleem is: sommige stappen kunnen door elke kok gedaan worden, maar andere alleen door specifieke experts. En elke kok heeft een eigen snelheid voor elk gerecht.

De uitdaging is om te beslissen: Welke kok doet welke stap, en in welke volgorde? Als je dit verkeerd doet, staat de hele keuken vast, wachten klanten lang, en is de laatste maaltijd pas laat klaar. Dit noemen wetenschappers het Flexible Job Shop Scheduling Problem (FJSP).

Tot nu toe probeerden computers dit op te lossen met complexe systemen die leken op een super-geavanceerde, maar rommelige notitieblok. Ze hielden honderden details bij: "Wie deed wat 5 minuten geleden?", "Hoe snel was de vorige kok?", "Wat is de gemiddelde snelheid?" enzovoort. Het was alsof je een kok probeert te leren die niet alleen moet koken, maar ook de hele geschiedenis van de keuken uit zijn hoofd moet kennen. Dat maakt het leren erg moeilijk en traag.

De Nieuwe Oplossing: RESCHED

De auteurs van dit paper hebben een nieuwe manier bedacht, genaamd RESCHED. Ze zeggen: "Waarom houden we al die oude notities bij? Laten we gewoon kijken naar wat er nu gebeurt."

Hier is hoe ze het doen, vertaald in simpele termen:

1. De "Korte Notitie" (De Minimalistische Staat)

In plaats van een dik boek met 20+ details te gebruiken, heeft RESCHED besloten om zich te beperken tot 4 essentiële feiten op elk moment:

1. Hoe laat is de kok klaar? (Beschikbaarheid machine)
2. Hoe laat is de vorige stap klaar? (Beschikbaarheid operatie)
3. Hoe lang duurt deze stap? (Duur)
4. Wat is de snelste mogelijke tijd? (Minimale duur)

De Analogie:
Stel je voor dat je een chef bent. Je hoeft niet te weten wat er gisteren is gebeurd of wie er gisteren heeft gekookt. Je hoeft alleen te weten: "Is kok A vrij? Is het ingrediënt B klaar? Hoe lang duurt het?" Als je die vier dingen weet, kun je de perfecte beslissing nemen. RESCHED verwijdert alle "ruis" en kijkt alleen naar het nu.

2. De "Super-Chef" (De Transformer Architectuur)

Vroeger gebruikten computers netwerken die leken op een groep mensen die in een kring staan en fluisteren (dit noemen ze Graph Neural Networks). Dit werkt goed, maar is traag als de groep groot wordt.

RESCHED gebruikt in plaats daarvan een Transformer (dezelfde technologie die achter ChatGPT zit).

• De Zelf-Aandacht (Self-Attention): Dit is alsof de chef naar zijn eigen team kijkt en ziet: "Stap 1 moet klaar zijn voordat Stap 2 begint." Ze gebruiken een slim trucje (RoPE) om de volgorde binnen een gerecht perfect te onthouden zonder extra notities.
• De Kruis-Aandacht (Cross-Attention): Dit is de verbinding tussen de koks en de gerechten. Omdat er vaak veel meer gerechten zijn dan koks (bijvoorbeeld 100 gerechten voor 10 koks), wordt het lastig om te zien wie wat doet. RESCHED gebruikt een slimme methode om ervoor te zorgen dat elke kok zijn eigen kracht behoudt, zelfs als er een storm aan gerechten op hem afkomt.

3. Het Leren door Proberen (Reinforcement Learning)

RESCHED leert niet door een boek te lezen, maar door te proberen.

• Het maakt een plan.
• Het kijkt of het plan goed is (wordt de laatste maaltijd sneller klaar?).
• Als het plan goed is, krijgt het een beloning. Als het slecht is, een straf.
• Door dit miljoenen keren te doen, wordt de chef steeds slimmer.

Waarom is dit zo cool?

• Het is sneller: Omdat het niet alle oude notities hoeft te lezen, is het veel sneller in het maken van beslissingen.
• Het is flexibeler: Het werkt niet alleen voor de keuken (FJSP), maar ook voor andere situaties waar dingen in een rij moeten (zoals fabrieken of het plannen van taken in de cloud). Het is als een "algemene chef" die elke keuken kan runnen, in plaats van een chef die alleen pizza's kan maken.
• Het is beter: In tests bleek RESCHED betere plannen te maken dan de beste menselijke regels en zelfs beter dan de slimste computers die we tot nu toe hadden.

Samenvattend:
RESCHED is een slimme manier om complexe planningsproblemen op te lossen door te stoppen met het bijhouden van onnodige details en te focussen op wat er nu echt belangrijk is. Het gebruikt de kracht van moderne AI (zoals ChatGPT) om te leren hoe je een chaotische keuken in een perfect geoliede machine verandert, en dat allemaal in een fractie van de tijd die andere methoden nodig hebben.

Het is alsof je een oude, zware landkaart hebt vervangen door een slimme GPS die alleen de weg naar voren toont. Je komt sneller aan, met minder stress.

Technische samenvatting

Titel: RESCHED: Heroverweging van Flexibele Job Shop Scheduling vanuit een Transformer-architectuur met Vereenvoudigde Staten

Publicatie: ICLR 2026 (Conference Paper)
Auteurs: Xiangjie Xiao, Cong Zhang, Wen Song, Zhiguang Cao

---

1. Het Probleem: Flexibele Job Shop Scheduling (FJSP)

De Flexibele Job Shop Scheduling Problem (FJSP) is een fundamenteel combinatorisch optimalisatieprobleem met toepassingen in productie, edge computing en logistiek. In tegenstelling tot de klassieke Job Shop Scheduling Problem (JSSP), waar elke bewerking aan één specifieke machine is toegewezen, kent de FJSP flexibiliteit: elke bewerking kan worden uitgevoerd op een van meerdere compatibele machines.

Het oplossen van FJSP vereist twee gekoppelde beslissingen:

1. Toewijzing: Welke machine wordt gekozen voor elke bewerking?
2. Volgorde: In welke volgorde worden de bewerkingen op elke machine uitgevoerd?

Het doel is om de makespan (de totale tijd om alle taken te voltooien) te minimaliseren.

Huidige uitdagingen:
Bestaande Deep Reinforcement Learning (DRL) methoden voor FJSP lijden vaak onder:

• Complexe staten: Ze vertrouwen op zwaar ge-engineerde, handgemaakte kenmerken (vaak >20 features) en historische data, wat de generalisatie beperkt.
• Architecturale bias: Ze gebruiken voornamelijk Graph Attention Networks (GATs), die starre inductieve biases hebben en moeite hebben met lange-afstandsafhankelijkheden zonder diepe stapeling.
• Heuristische beperkingen: Veel methoden gebruiken handmatige heuristieken om de actie-ruimte te verkleinen, wat de generalisatievermogen van het beleid kan schaden.

---

2. Methodologie: Het RESCHED Framework

RESCHED introduceert een minimalistisch DRL-framework dat de probleemformulering en het modelontwerp fundamenteel heroverweegt.

A. Vereenvoudigde State Representatie (MDP Formulering)

In plaats van de volledige geschiedenis van het schema bij te houden, definieert RESCHED de toestand ($S_t$) op basis van een subprobleem-perspectief. De auteurs bewijzen dat de optimale beslissing op stap $t$ uitsluitend afhangt van de huidige toestand, niet van het pad dat erheen leidde (Markov-eigenschap).

De state wordt gereduceerd tot slechts vier essentiële kenmerken:

1. Beschikbare tijd van bewerkingen (Operation Available Time): Wanneer kan de bewerking starten (gebaseerd op de voltooiing van voorgangers)?
2. Beschikbare tijd van machines (Machine Available Time): Wanneer is de machine vrij?
3. Duur (Duration): De verwerkingstijd van een bewerking op een specifieke machine.
4. Minimale duur (Minimum Duration): De kortste mogelijke verwerkingstijd voor een bewerking over alle beschikbare machines (als proxy voor moeilijkheid).

Belangrijke innovatie: Historische afhankelijkheden en redundante features worden verwijderd. De graafstructuur encodeert expliciet de O2O-afhankelijkheden (bewerking-naar-bewerking) en O2M-verbindingen (bewerking-naar-machine).

B. Transformer-architectuur met Aangepaste Mechanismen

RESCHED vervangt GNNs door een Transformer-backbone met twee complementaire takken, aangepast voor scheduling-taken:

1. Operation Branch (Zelf-attention met RoPE):

   • Modelleren van intra-job afhankelijkheden (O2O).
   • Gebruik van Rotary Positional Embedding (RoPE) om de relatieve volgorde van bewerkingen binnen een taak direct te modelleren zonder extra leerbare parameters. Dit is cruciaal omdat de volgorde binnen een job strikt is, maar de volgorde tussen jobs vrij kan zijn.

2. Machine Branch (Cross-attention met Edge-in-Attention):

   • Aggregeren van informatie van bewerkingen naar machines.
   • Edge-in-Attention: In tegenstelling tot eerdere werken die randkenmerken (zoals duur) indirect verwerken, embedt RESCHED de randkenmerken direct in de waarde-vectoren. Dit zorgt ervoor dat de duur de uiteindelijke representatie beïnvloedt, niet alleen de attention-weights.
   • Self-based Cross-attention: Om het onevenwicht op te lossen tussen het grote aantal bewerkingen en het kleine aantal machines (vaak >10:1), attends elke machine ook op haar eigen representatie. Dit voorkomt dat kritieke machine-informatie wordt verdund door de overvloed aan operatie-berichten.

C. Beleidsnetwerk en Training

• Actie: Selecteren van een geldig (bewerking, machine)-paar.
• Beloning: Gebaseerd op de negatieve verandering in de geschatte ondergrens van de makespan ($\Delta$-makespan lower bound).
• Algoritme: Gebruik van REINFORCE (in plaats van PPO) om de impact van de state- en architectuurontwerpen te isoleren van RL-algoritme-optimalisaties.

---

3. Belangrijkste Bijdragen

1. Minimale State Representatie: Een compacte toestand met slechts vier kernfeatures, die historische tracking elimineert en redundantie verwijdert, terwijl de Markov-eigenschap behouden blijft.
2. Dual-Branch Transformer: Een nieuwe architectuur die RoPE gebruikt voor intra-job volgorde en een innovatieve cross-attention module introduceert die randkenmerken direct integreert en het onbalans tussen bewerkingen en machines oplost via self-attention.
3. Universele Generalisatie: Het framework is niet specifiek voor FJSP ontworpen, maar generaliseert naadloos naar varianten zoals JSSP (Job Shop) en FFSP (Flexible Flow Shop) zonder architecturale wijzigingen.

---

4. Resultaten

Uitgebreide experimenten tonen aan dat RESCHED state-of-the-art (SOTA) prestaties levert:

• FJSP Prestaties: RESCHED overtreft zowel klassieke dispatching-regels (zoals FIFO, SPT) als de beste bestaande DRL-methoden (HGNN, DANIEL, DOAGNN) op synthetische datasets (SD1, SD2) en standaard benchmarks (Brandimarte, Hurink).
  • Op uitdagende SD2-instanties (15x10) verkleint RESCHED de kloof met de beste concurrent (DANIEL) met 30%.
  • Het presteert zelfs beter dan OR-Tools (exacte solver) in inferentiële tijd op grote schaal.
• Generalisatie:
  • JSSP: Getraind op synthetische 10x10 data, presteert het beter dan gespecialiseerde JSSP-methoden (L2D, RL-GNN) op benchmarks tot 100x20.
  • FFSP: Getraind op grootte 20, bereikt het de beste resultaten op grotere instanties (50, 100), terwijl gespecialiseerde methoden (MatNet) vaak per grootte opnieuw getraind moeten worden.
• Efficiëntie: De inferentiële tijd is vergelijkbaar met andere DRL-methoden, maar levert aanzienlijk betere oplossingskwaliteit.
• Robuustheid: Ablatiestudies bevestigen dat elke component (RoPE, Edge-in-Attention, Self-based CA, minimale state) essentieel is voor de prestaties.

---

5. Betekenis en Impact

RESCHED bewijst dat minimalisme in state-representatie gecombineerd met expressieve modellering (Transformers) superieur kan zijn aan complexe, zwaar ge-engineerde benaderingen.

• Vereenvoudiging: Het elimineert de noodzaak voor honderden handgemaakte features en complexe historische tracking.
• Schaalbaarheid: Door het gebruik van Transformers en KV-cache (theoretisch haalbaar), is het framework zeer geschikt voor grootschalige schedulingproblemen.
• Unificatie: Het biedt een unificerend raamwerk voor diverse schedulingvarianten (FJSP, JSSP, FFSP), wat de weg vrijmaakt voor bredere toepassing in real-world systemen zoals edge computing en dynamische logistiek.

Kortom, RESCHED zet een nieuwe standaard voor neurale combinatorische optimalisatie in de scheduling, waarbij het bewijst dat een goed ontworpen, minimalistisch model beter generaliseert dan zware, gespecialiseerde netwerken.