An Analysis of the Coordination Gap between Joint and Modular Learning for Job Shop Scheduling with Transportation Resources

1. Probleemdefinitie

Het artikel behandelt het Job Shop Scheduling Problem met Transportmiddelen (JSSPT), een complexe variant van het klassieke Job Shop Scheduling Problem (JSSP).

• Context: In moderne "gedecentraliseerde fabrieken" moeten productieoperaties worden gecoördineerd met materiaalbehandeling met behulp van Automatic Guided Vehicles (AGV's).
• Doel: Minimaliseren van de makespan ($C_{max}$), gedefinieerd als de voltooiingstijd van de laatste taak bij de losmachine.
• Beperkingen:
  • Productie: Taken volgen vaste routevolgorde; machines verwerken één bewerking tegelijk zonder onderbreking.
  • Transport: AGV's hebben een eenheidscapaciteit (één taak tegelijk) en kunnen niet worden onderbroken. Een bewerking kan pas beginnen nadat het transport is voltooid, en transport kan pas beginnen nadat de vorige bewerking is beëindigd.
  • Buffers: Invoerbuffers zijn onbeperkt (FIFO); uitvoerbuffers zijn onbeperkt zonder volgordebeperkingen.
• De Kernuitdaging: Traditionele methoden (Dispatching Rules, Genetische Algoritmen) worstelen met real-time aanpasbaarheid of rekenkosten. Hoewel Multi-Agent Reinforcement Learning (MARL) een oplossing biedt, is het onduidelijk wanneer Gecombineerde Training (gelijktijdige training van taak- en AGV-agenten) noodzakelijk is versus wanneer Modulaire Training (onafhankelijke training gevolgd door integratie) volstaat.

2. Methodologie

A. Multi-Agent Reinforcement Learning Framework

De auteurs formuleren het probleem als een Markov Beslissingsproces (MDP) met twee distincte agenten:

1. Taakplanner Agent: Beslist welke bewerking als volgende wordt gepland.
2. AGV-planner Agent: Beslist welke AGV wordt toegewezen aan de geselecteerde bewerking.

Staatrepresentatie:

• Taakstaat ($S^o_t$): Weergegeven als een Disjunctieve Grafiek ($G=\{V, E\}$).
  • Hoekpunten: Bewerkingen en Machines.
  • Kenmerken: Binaire indicatoren voor planningsstatus, machinetype en een Ondergrens (LB)-scalar die de minimale resterende tijd voor een taak vertegenwoordigt. Machinewerkpunten omvatten de verhouding van geplande bewerkingen.
  • Architectuur: Gecodeerd met behulp van een Graph Isomorphism Network (GIN) om grafiektopologie en berichtdoorvoer vast te leggen.
• AGV-staat ($S^{agv}_t$): Een vector van zes scalairen per AGV, inclusief vroegste ophaaltijd, reistijden en machinebeschikbaarheid.
  • Architectuur: Gecodeerd met behulp van een Multi-Layer Perceptron (MLP).

Actieruimte:

• Gecombineerde Actie: Een paar $(a_o, a_{agv})$ waarbij $a_o$ de geselecteerde bewerking is en $a_{agv}$ de toegewezen AGV.
• Beleid: Het AGV-beleid is conditioneel op de actie van het taakbeleid ($\pi(a_{agv}|S^{agv}_t, a_o)$).

Beloningsfunctie:

• Spaarzame beloning gebaseerd op de negatieve makespan ($-C_{max}$), genormaliseerd door een ondergrens. Dit dwingt agenten om het globale doel te optimaliseren in plaats van lokale efficiëntie.

B. Trainingsmodaliteiten

De studie vergelijkt twee distincte trainingsstrategieën:

1. Gecombineerde Training: Beide agenten zijn leerbare parameters die gelijktijdig worden getraind met MAPPO (Multi-Agent Proximal Policy Optimization). Ze leren coöperatief gedrag end-to-end.
2. Modulaire Training: Agenten worden onafhankelijk getraind. De ene agent is een leerbaar beleid (GNN of MLP), terwijl de andere een vaste Dispatching Rule (DR) is (bijvoorbeeld Shortest Processing Time, First Come First Serve). De beste modulaire combinaties worden achteraf geïdentificeerd.

C. Experimenteel Ontwerp

• Basislijnen: 10 selectieregels voor bewerkingen $\times$ 4 selectieregels voor AGV's = 40 DR-combinaties.
• Sensitiviteitsanalyse: De auteurs introduceren twee belangrijke metrieken om de "Coördinatiekloof" (prestatieverschil tussen Gecombineerd en Modulair) te analyseren:
  • Ressourcenschaarste ($\rho$): Verhouding van AGV's tot Taken ($k/n$).
  • Temporele Dominantie ($\tau^*$): Een genormaliseerde index die de balans tussen verwerkingstijd en transporttijd vertegenwoordigt.
• Evaluatie: Prestaties worden gemeten met behulp van Relative Percentage Increase (RPI) ten opzichte van de beste DR-basislijn en Win Rate (WR).

3. Belangrijkste Bijdragen

1. Nieuw Trainingskader: Een flexibele architectuur die onafhankelijk agentleren toelaat terwijl compatibiliteit voor gecombineerde evaluatie wordt behouden, waardoor een directe vergelijking van trainingsmodaliteiten mogelijk is.
2. Systematische Sensitiviteitsanalyse: De eerste rigoureuze kwantificering van de "coördinatiekloof" in JSSPT, waarbij specifieke omgevingscondities worden geïdentificeerd waarbij gecombineerde training essentieel is.
3. Karakterisering van Onderlinge Afhankelijkheid: Een wiskundige karakterisering van hoe ressourcenschaarste en temporele dominantie niet-lineair de effectiviteit van gecombineerd versus modulair leren beïnvloeden.
4. Praktische Richtlijnen: Empirisch bewijs dat besluitvormers leidt over wanneer te investeren in complexe gecombineerde training versus eenvoudigere modulaire benaderingen.

4. Resultaten

A. Algemene Prestaties

• Gecombineerde Superieure: De Gecombineerde Oplosser ($J_0 A_0$) presteert consequent beter dan alle modulaire oplossers en Dispatching Rule-basislijnen.
• Gemiddelde Winst: De gecombineerde oplosser bereikt een gemiddelde 4,2% verbetering in makespan vergeleken met de beste globale DR-combinatie.
• Modulaire Variantie: Modulaire oplossers vertonen hoge variantie; hun succes hangt sterk af van de specifieke heuristische koppeling die tijdens onafhankelijke training is gebruikt.

B. De Coördinatiekloof & Omgevingsfactoren

De studie identificeert een niet-lineair verband tussen omgevingscondities en het voordeel van gecombineerde training:

• Gebalanceerde Omgevingen (Hoge Coördinatiekloof): In regimes waarin middelen noch schaars noch overvloedig zijn, en verwerking/transporttijden in balans zijn, levert gecombineerde training de hoogste winsten op (tot 8,5% RPI). Hier vertrouwt het systeem op de koppeling tussen taakplanning en AGV-toewijzing.
• Bottleneck-omgevingen (Lage Coördinatiekloof):
  • Transport-beperkt: Ernstige AGV-schaarste ($\rho < 0,4$).
  • Proces-beperkt: Dominante verwerkingstijden met overvloedige AGV's ($\rho > 0,8$).
  • Vinding: In deze regimes wordt de prestatiekloof aanzienlijk smaller (dalend tot 0,6% - 1,5%). Wanneer een enkele bottleneck het systeem domineert, neemt de marginale winst van holistische coördinatie af omdat het systeem door die enkele factor wordt beperkt, ongeacht de samenwerking tussen agenten.

C. Statistische Validatie

• Regressieanalyse: Een Ordinary Least Squares (OLS)-model bevestigt dat Bottleneck-dominantie (enkele taakbeperking) en Taakbalans de coördinatiekloof significant voorspellen ($R^2 = 0,67$).
• Belangrijk Inzicht: Negatieve coëfficiënten voor bottleneckvariabelen geven aan dat naarmate een enkele taak domineert, het voordeel van gecombineerde training afneemt. Positieve coëfficiënten voor de balansmetriek geven aan dat gebalanceerde systemen het meest profiteren van gecombineerd leren.

5. Betekenis en Implicaties

• Strategische Ressourcetoewijzing: Het artikel biedt een beslissingskader voor industriële praktici. Als een fabriek opereert in een bottleneck-regime (bijvoorbeeld chronisch AGV-tekort of extreem trage machines), is de rekenkosten van gecombineerde MARL-training mogelijk niet gerechtvaardigd; een goed afgestemde modulaire aanpak (of zelfs geavanceerde dispatching rules) kan volstaan.
• Optimalisatie in Flexibele Fabrieken: In gebalanceerde, flexibele omgevingen (typisch voor hoogwaardige productie) is gecombineerde training essentieel om het volledige potentieel van gedecentraliseerde systemen te ontsluiten door de complexe wisselwerking tussen productie en logistiek te optimaliseren.
• Toekomstige Richtingen: Het werk legt de basis voor het uitbreiden van MARL naar complexere scenario's, zoals flexibele jobshops met machine-selectieagenten en multi-objectieve optimalisatie (energie, kosten, vertraging).

Kortom, het artikel toont aan dat terwijl Gecombineerde Training over het algemeen superieur is, het voordeel contextafhankelijk is. De "coördinatiekloof" is het grootst wanneer productie en logistiek nauw gekoppeld en gebalanceerd zijn, en het kleinst wanneer het systeem wordt gedomineerd door een enkele, ernstige beperking.