💻 computer science

Modelling Reinforcement Learning Scheduling Agents: Action spaces, reward designs, and expert demonstrations

Dit artikel onderzoekt hoe modelleringskeuzes in Deep Reinforcement Learning de planningsbeleid voor het Flexible Job-shop Scheduling Problem beïnvloeden, waarbij wordt aangetoond dat het integreren van optimaliteitsgrenzen afgeleid van Constraint Programming en expertdemonstraties in een multi-agent framework het beloningsontwerp aanzienlijk verbetert en de convergentie versnelt om superieure, real-time planningsprestaties te bereiken.

Oorspronkelijke auteurs: Alexandre Jesus, Arthur Corrêa, Miguel Vieira, Catarina Marques, Cristóvão Silva, Samuel Moniz

Gepubliceerd 2026-09-07

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Alexandre Jesus, Arthur Corrêa, Miguel Vieira, Catarina Marques, Cristóvão Silva, Samuel Moniz

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

In het hart van de moderne productie speelt zich elke seconde een stille en complexe puzzel af. Fabrieken moeten beslissen in welke volgorde duizenden taken worden uitgevoerd op een beperkt aantal machines. Sommige taken kunnen alleen op één specifieke machine worden uitgevoerd, terwijl andere door verschillende machines kunnen worden afgehandeld, waarbij elke machine net een andere tijd in beslag neemt. Het doel is eenvoudig te formuleren maar ongelooflijk moeilijk op te lossen: al het werk zo snel mogelijk voltooien. Deze uitdaging, bekend als het flexibele job-shop scheduling probleem, is een klassieke test van efficiëntie. Decennialang hebben experts vertrouwd op rigide wiskundige regels of trial-and-error-methoden om goede oplossingen te vinden. Echter, deze traditionele methoden worstelen vaak wanneer de fabrieksvloer verandert of wanneer het aantal mogelijkheden te groot wordt om snel te berekenen. In de afgelopen jaren is er een nieuwe aanpak ontstaan: computers leren door te doen. Deze methle, genaamd reinforcement learning (versterkend leren), stelt een kunstmatige intelligentie in staat om miljoenen scenario's te verkennen en haar eigen strategieën te ontdekken voor het organiseren van werk, wat belooft beslissingen sneller en adaptiever te maken dan ooit tevoren.

Een team van onderzoekers van universiteiten in Portugal heeft nu een nadere blik geworpen op hoe deze lerende machines worden gebouwd, en stelde een fundamentele vraag: doet de manier waarop we ze onderwijzen er meer toe doen dan de intelligentie van de machine zelf? Ze richtten zich op twee specifieke keuzes die ontwerpers maken bij het creëren van deze planningsagenten. De eerste keuze is het detailniveau dat de agent ziet. Kijkt de agent naar de gehele opdracht en beslist welke hij als volgende moet starten, of zoomt hij in om elke individuele stap van elke opdracht te zien en precies te beslissen welke stap moet worden uitgevoerd? De tweede keuze is het beloningssysteem, de feedbackloop die de agent vertelt of hij een goed werk levert. Wordt de agent geprezen voor het simpelweg snel voltooien van een taak, of wordt hij beloond voor hoe die taak past in het algemene plaatje van de fabriek? Om de antwoorden te vinden, lieten de onderzoekers hun agenten niet zomaar gokken. In plaats daarvan gebruikten ze een krachtige, traditionele wiskundige solver om perfecte of bijna perfecte schema's te genereren voor een breed scala aan fabrieksscenario's. Ze gebruikten deze expertoplossingen vervolgens als referentiepunt, een gouden standaard, om te meten hoe goed hun lerende agenten daadwerkelijk presteerden.

De onderzoekers ontdekten dat de beste aanpak volledig afhangt van de aard van de fabrieksvloer. Wanneer de opdrachten allemaal erg vergelijkbaar zijn, werkt een eenvoudiger overzicht het best. In die gevallen is het efficiënt en effectief om de agent naar de hele opdracht te laten kijken en de volgende te laten kiezen die moet draaien. Echter, wanneer de fabriek vol variatie is — waar sommige opdrachten lang en complex zijn terwijl andere kort zijn, en waar machines zeer verschillende snelheden hebben — faalt het eenvoudige overzicht. In deze chaotische omgevingen moet de agent de fijne details zien. Hij moet elke individuele operatie bekijken en precies beslissen welke machine deze moet afhandelen. De studie toonde aan dat het negeren van deze details in een complexe fabriek leidt tot aanzienlijk slechtere resultaten, wat bewijst dat er geen enkele "one-size-fits-all" manier is om deze lerende agenten te ontwerpen.

Het team vond ook dat de manier waarop ze de agenten beloonden nog kritischer was dan het detailniveau dat ze zagen. Veel eerdere studies vertrouwden op een globale beloning, waarbij de agent pas feedback kreeg wanneer de totale tijd om alle opdrachten te voltooien veranderde. Dit is als een coach die pas aan het woord komt wanneer de eindscore verandert, waardoor de speler halverwege de wedstrijd moet raden wat hij wel of niet goed deed. De onderzoekers ontdekten dat deze aanpak de agenten vaak in verwarring liet, vooral in complexe omgevingen. In plaats daarvan ontwierpen ze een nieuw beloningssysteem dat onmiddellijke, lokale feedback gaf. De agent werd beloond op basis van hoe efficiënt hij de specifieke machine gebruikte waar hij aan werkte, vergeleken met de andere machines die beschikbaar waren voor die specifieke taak. Deze constante, onmiddellijke feedback fungeerde als een vaste hand op de schouder, die de agent stap voor stap begeleidde. Wanneer ze deze lokale begeleiding combineerden met het globale plaatje, leerden de agenten veel sneller en produceerden ze schema's die veel dichter bij de perfecte oplossingen van de traditionele wiskundige solver lagen.

Om de prestaties nog verder te verbeteren, introduceerden de onderzoekers een hybride methode. Ze realiseerden zich dat het inefficiënt is om een agent vanaf nul te laten beginnen. Dus, voordat de agent aan zijn eigen leerproces begon, toonden ze hem een duizend voorbeelden van perfecte schema's gecreëerd door de expert wiskundige solver. Dit proces, bekend als leren van demonstraties, gaf de agent een voorsprong, waardoor hij de vroege, onhandige fase van willekeurig gokken kon overslaan. Het resultaat was een systeem dat niet alleen sneller leerde, maar ook stabieler en betrouwbaarder werd. In hun tests verminderde deze hybride aanpak de kloof tussen het schema van de agent en het perfecte schema met ongeveer vijf procent vergeleken met standaard leermethoden. Misschien wel het belangrijkste: dit hoge prestatieniveau kwam zonder de noodzaak voor complexe, zware computerarchitecturen. Het systeem bleef lichtgewicht en snel, in staat om beslissingen te nemen in minder dan een seconde.

De studie concludeert dat het geheim van het bouwen van effectieve planningsagenten niet alleen ligt in het algoritme zelf, maar in het zorgvuldig afstemmen van het ontwerp op het specifieke probleem dat voorhanden is. Door expertoplossingen te gebruiken om het leerproces te begeleiden en door de beloningssignalen af te stemmen op de specifieke mix van machines en opdrachten, is het mogelijk om intelligente systemen te creëren die zowel krachtig als praktisch zijn. Deze bevindingen suggereren dat de toekomst van fabrieksbeheer niet onmogelijk complexe AI vereist, maar eerder een doordachte combinatie van traditionele wiskundige precisie en moderne leermethoden. Het resultaat is een hulpmiddel dat fabrieken kan helpen om in realtime aan te passen aan veranderingen, waardoor de stroom van productie soepel blijft, zelfs wanneer de wereld om hen heen allesbehalve stabiel is.

Technische Samenvatting: Modellering van Reinforcement Learning Scheduling Agents

Probleemdefinitie

Dit onderzoek behandelt het Flexible Job-shop Scheduling Problem (FJSP), een combinatorisch optimalisatieprobleem dat centraal staat in de moderne productie. Het FJSP breidt het klassieke Job-shop Scheduling Problem (JSP) uit door operaties toe te staan op meerdere kandidaatmachines te worden verwerkt, wat twee beslissingslagen introduceert: operatieallocatie (het selecteren van de machine) en machine-sequencing (het bepalen van de volgorde). Het doel is om de makespan ( $C_{max}$ ) te minimaliseren, gedefinieerd als de voltooiingstijd van de laatste operatie.

Hoewel exacte methoden zoals Mixed-Integer Linear Programming (MILP) en Constraint Programming (CP) optimale oplossingen kunnen vinden, hebben zij vaak moeite met de computationele kosten in grootschalige of dynamische omgevingen. Daarentegen biedt Deep Reinforcement Learning (DRL) lage inferentietijden en adaptiviteit, maar lijdt het aan een gebrek aan systematisch begrip over hoe modelleringskeuzes (actieruimtes, beloningsfuncties) interageren met specifieke probleemstructuren (bijv. job-heterogeniteit, machineflexibiliteit). Bestaande DRL-studies vertrouwen vaak op trial-and-error ontwerp of heuristische baselines, en missen een rigoureuze verbinding met optimaliteitsgrenzen.

Methodologie

De auteurs stellen een multi-agent Deep Q-Learning (DQL) framework voor dat opereert onder een Centralized Learning with Decentralized Execution (CLDE) paradigma. Elke agent representeert een machine op de fabrieksvloer en neemt lokale beslissingen op basis van gedeeltelijke observaties.

1. Integratie van Constraint Programming (CP)

Een state-of-the-art interval-gebaseerd CP-model (gebruikmakend van IBM CP Optimizer) vervult twee afzonderlijke rollen:

Analytische Baseline: CP wordt gebruikt om optimaliteitsgrenzen (ondergrenzen) en hoogwaardige oplossingen voor benchmark-instanties te berekenen. Deze dienen als de grondwaarheid om de optimaliteitskloof van DRL-policies te evalueren.
Expert Demonstraties: CP-oplossingen worden gedecomposeerd in state-action transities om de DRL-agent voor te trainen, waarbij ze fungeren als "expert demonstraties".

2. Multi-Agent DQL Architectuur

Het framework maakt gebruik van een waarde-gebaseerde benadering waarbij agents een enkel Deep Q-Network (DQN) beleid delen.

State Representatie: Agents observeren gedeeltelijke systeemtoestanden, inclusief wachtende operaties, verwerkingstijden, actiegeschiedenis, resterende operaties, machinebenutting en wachtrijdichtheid.
Actieruimtes: Twee granulariteiten worden geëvalueerd:
- Operatie-niveau ( $L_O$ ): Agents selecteren specifieke operaties uit de wachtrij.
- Job-niveau ( $L_J$ ): Agents selecteren een job, waarna de omgeving de volgende operatie plant.
Beloningsontwerp: De studie evalueert systematisch verschillende beloningsfuncties, waaronder:
- Globale signalen: Het bestraffen van makespan-incrementen ( $r_{MI}$ ).
- Lokale signalen: Het bestraffen van de totale tijd tussen acties ( $r_{TBA}$ ) of inactiviteit ( $r_{IT}$ ).
- Voorgestelde Hybride Signalen: Nieuwe beloningen ( $r_Q$ , $r_{OE}$ ) die inefficiënte machinekeuze bestraffen door de gekozen verwerkingstijd te vergelijken met de snelste beschikbare kandidaat voor die operatie.

3. Hybride Leerstrategie (DQL-D)

De auteurs introduceren DQL-D, een hybride methode die Deep Q-Learning from Demonstrations (DQLfD) incorporeert.

Pre-training: De DQN wordt geïnitialiseerd met behulp van transities afgeleid van CP-oplossingen (de top 5 oplossingen per instantie).
Prioritized Experience Replay: De replay buffer bevat zowel expert demonstraties als door de RL zelf gegenereerde transities. Transities worden gesampled op basis van verlies, waarbij prioriteit wordt gegeven aan toestanden waar de agent de expert-gedrag nog niet beheerst.
Training: De agent blijft leren via standaard DQL, waardoor het in staat is om verder te exploreren dan het expert-beleid terwijl het profiteert van de stabiliteit van de initiële begeleiding.

Belangrijkste Bijdragen

Systematische Analyse van Modelleringskeuzes: Het artikel biedt een rigoureuze evaluatie van hoe de granulariteit van acties en de reikwijdte van beloningen interageren met de structurele eigenschappen van instanties (job-heterogeniteit, machineflexibiliteit en variabiliteit in verwerkingstijd).
Nieuwe Beloningsfuncties: De auteurs ontwerpen beloningsfuncties ( $r_Q$ en $r_{OE}$ ) die expliciet rekening houden met machine-heterogeniteit. Deze signalen presteren beter dan bestaande globale of puur lokale beloningen, waardoor de optimaliteitskloof in scenario's met hoge heterogeniteit met ongeveer 10% wordt verkleind.
Hybride DQL-D Framework: De integratie van CP-afgeleide demonstraties in een multi-agent DQL-architectuur versnelt convergentie en verbetert de stabiliteit zonder complexe graph encoders of attention mechanismen te vereisen.

Experimentele Resultaten

De methodologie werd getest op drie standaard FJSP benchmark-datasets (FMJdata, BRdata, DPdata) met variërende schalen en flexibiliteitsniveaus.

Actie-granulariteit: In instanties met homogene job-structuren presteerden job-niveau acties ( $L_J$ ) vergelijkbaar met operatie-niveau acties ( $L_O$ ). Echter, in heterogene job-structuren (veelvoorkomend in BRdata en DPdata), leverden operatie-niveau acties ( $L_O$ ) significant lagere optimaliteitskloven op (ongeveer 5% verbetering in mediane fout).
Beloningsontwerp:
- Standaard globale beloningen ( $r_{MI}$ ) en totale tijd-beloningen ( $r_{TBA}$ ) leidden vaak tot hogere optimaliteitskloven.
- De voorgestelde lokale efficiëntiebeloning ( $r_Q$ ) presteerde consequent beter dan andere, met een gemiddelde kloof tot CP van 13,62% over alle instanties en een reductie van de optimaliteitskloof met ongeveer 10% in scenario's met hoge heterogeniteit vergeleken met standaard baselines. Deze beloning normaliseert de kwaliteit van acties effectief over agents met verschillende werklasten.
Prestaties van DQL-D:
- Convergentie: DQL-D bereikte snellere convergentie en een lagere variantie dan standaard DQL. Het verminderde de optimaliteitskloof met ongeveer 5% ten opzichte van de standaard DQL-baseline.
- Vergelijking: DQL-D behaalde competitieve prestaties tegenover state-of-the-art graph-gebaseerde DRL-methoden (HGNN en MPGN, en presteerde vaak beter in instanties waar die methoden minder geschikt waren.
- Efficiëntie: Het lichtgewicht DQL-D framework bereikte inferentietijden die 3 tot 9 keer sneller zijn (sub-seconde) dan complexe graph-gebaseerde architecturen, wat het zeer geschikt maakt voor real-time scheduling.

Betekenis en Claims

Het artikel claimt dat optimaliteits-gestuurde DRL-modellering, gecombineerd met expert demonstraties, de creatie van lichtgewicht, snelle en betrouwbare scheduling agents mogelijk maakt.

Modelleringsinzichten: De studie toont aan dat een "one-size-fits-all" DRL-aanpak onvoldoende is; actieruimtes en beloningsfuncties moeten worden afgestemd op de specifieke structurele eigenschappen van de scheduling-instantie (bijv. het gebruik van operatie-niveau acties voor heterogene jobs en lokale efficiëntiebeloningen voor heterogene machines).
Praktische Levensvatbaarheid: Door CP te gebruiken voor pre-training en een eenvoudige waarde-gebaseerde architectuur te gebruiken, laten de auteurs zien dat complexe representatie-lering (zoals Graph Neural Networks) niet strikt noodzakelijk is om state-of-the-art prestaties te behalen. Dit biedt een praktische oplossing voor productiesystemen die decentrale besluitvorming met strikte real-time beperkingen vereisen.
Toekomstige Richting: Het werk suggereert dat hybride frameworks die exacte methoden (CP) combineren met DRL, de kloof tussen theoretische optimaliteit en praktische implementatie kunnen overbruggen, wat de weg vrijmaakt voor dynamische en online scheduling varianten.