A Genetic Algorithm with Critical‑Path‑Driven Dual‑Neighborhood Search for Flexible Job Shop Scheduling

Technische Samenvatting: Een Genetisch Algoritme met een Critical-Path-gestuurde Duale Buurtzoekopdracht voor Flexibele Job Shop Scheduling

Probleemdefinitie
Het artikel behandelt het Flexible Job Shop Scheduling Problem (FJSP), een sterk NP-hard optimalisatievraagstuk dat veel voorkomt in de moderne productie. In tegenstelling tot het klassieke Job Shop Scheduling Problem (JSP), waarbij operaties vaste machineto assignments hebben, staat FJSP toe dat elke operatie op elke machine uit een set alternatieve kandidaten kan worden verwerkt, vaak met variërende verwerkingstijden. Het primaire doel is het minimaliseren van de maaktijd ($C_{max}$), gedefinieerd als de maximale voltooiingstijd van alle jobs. Het probleem behelst zowel het bepalen van de machinekeuze voor elke operatie als de verwerkingsvolgorde op elke machine, terwijl aan precedentvoorwaarden en machinebeschikbaarheid wordt voldaan.

Methodologie: HGVNSA
De auteurs stellen een Hybrid Genetic Variable Neighborhood Search Algorithm (HGVNSA) voor die een Genetisch Algoritme (GA) voor globale exploratie integreert met een Critical-Path-gestuurde Variable Neighborhood Search (VNS) voor lokale exploitatie.

1. Codering en Decodering: De oplossing wordt gerepresenteerd met behulp van een twee-laagse codering: een Operatievolgorde (OS) vector en een Machinekeuze (MS) vector. Een actieve decoderingsstrategie wordt gebruikt om haalbare schema's te genereren.
2. Populatie-initialisatie: Om kwaliteit en diversiteit te balanceren, wordt de initiële populatie gegenereerd met behulp van een hybride strategie: Globale Selectie (60%, minimalisering van de globale lastincrement), Lokale Selectie (30%, balanceren van de last binnen jobs) en Random Selectie (10%).
3. Genetische Operaties:
   • Crossover: Er wordt een Path-Relinking (PR) gebaseerde crossover-operator geïntroduceerd. In plaats van willekeurige gen-swaps, transformeert het systematisch één ouder-oplossing naar een andere, waarbij tussenliggende oplossingen worden vastgelegd en geëvalueerd om de zoekruimte tussen ouders te exploiteren.
   • Mutatie: Een adaptief mutatiemechanisme past waarschijnlijkheden aan op basis van individuele fitness en het aantal generaties. Twee typen mutatie worden gebruikt: OS-mutatie (het door elkaar husselen van de volgorde van operaties) en MS-mutatie (het wijzigen van machine-to assignments).
   • Behoud van Diversiteit: Een strategie gebaseerd op de Hamming-afstand wordt toegepast om de populatiediversiteit te behouden en voortijdige convergentie te voorkomen.
4. Critical-Path-gestuurde Duale Buurt VNS: Deze lokale zoekopdracht, ingebed in het GA-framework, richt zich op operaties die zich op het kritieke pad bevinden (het langste pad in de disjunctieve graaf). Het maakt gebruik van twee complementaire buurtstructuren:
   • N8 Buurt: Optimaliseert de volgorde van operaties op de zelfde machine. Het breidt traditionele N5-N7 bewegingen uit door toe te staan dat kritieke operaties buiten kritieke blokken naar de eindpunten van blokken of naar posities vóór/na een blok worden verplaatst.
   • k-Insertion Buurt: Heralloceert kritieke operaties naar andere machines. Dit houdt in dat men door alternatieve machines traverseert en de operatie op haalbare posities invoegt, waarbij gecontroleerd wordt op cyclische afhankelijkheden.
   • Zoekstrategie: Het VNS-proces geeft prioriteit aan de N8-buurt (lagere computationele kosten) en schakelt over naar k-insertion (hogere kosten, bredere zoekopdracht) alleen als er geen verbetering wordt gevonden, wat zorgt voor een balans tussen efficiëntie en diepte van exploratie.

Belangrijkste Bijdragen
Het artikel schetst vijf fundamentele bijdragen:

1. Hybride Framework: Het vestigt een synergetisch "globale exploratie eerst, lokale exploitatie daarna" framework, dat de balans tussen oplossing nauwkeurigheid en computationele efficiëntie effectief beheert.
2. Integratie van Duale Buurten: Het is de eerste die de N8 en k-insertion buurten integreert binnen een verenigd VNS-framework voor FJSP. Deze combinatie adresseert zowel intra-machine sequencing als inter-machine herallocatie, wat de lokale zoekcapaciteit aanzienlijk verbetert.
3. Verbeterde Genetische Operatoren: De introductie van de Path-Relinking crossover en adaptieve mutatie-waarschijnlijkheden versterkt het vermogen van het algoritme om de oplossingsruimte te verkennen en convergentiestabiliteit te behouden.
4. Benchmark Prestaties: Op de Brandimarte MK benchmark-set bereikt HGVNSA consistent bekende optimale oplossingen in 6 van de 10 instanties (MK01-MK04, MK08-MK09) en behaalt het de laagste gemiddelde Relative Percentage Deviation (RPD) van 0,06% onder de vergeleken algoritmen (HGWO, HLO-PSO, HA, SLGA, ISLGA).
5. Real-World Toepassing: Het algoritme werd toegepast op een scenario voor de verwerking van een tandas bij Bedrijf A. Vergeleken met een traditioneel Genetisch Algoritme verbeterde HGVNSA de productie-efficiëntie met 8,81%, wat de technische praktische bruikbaarheid aantoont.

Resultaten en Validatie

• Benchmark Testing: Uitgebreide experimenten op de MK01-MK10 instanties toonden aan dat HGVNSA andere vergelijking-algoritmen overtrof in termen van oplossingskwaliteit en stabiliteit. Ablatie-studies bevestigden dat het verwijderen van de VNS-component, de duale buurtstructuur of de adaptieve mechanismen leidde tot significante prestatieverslechtering (bijv. het verwijderen van VNS verhoogde de gemiddelde maaktijd op MK02 van 26 naar 30,4).
• Case Study: In de Bedrijf A case study, betrokken bij 10 jobs en 59 operaties over 15 machines, reduceerde het algoritme de maaktijd van 522 (traditionele GA) naar 476.
• Convergentie: Convergentie-analyse gaf aan dat terwijl andere algoritmen stagneerden na een initiële snelle convergentie, HGVNSA de oplossingen bleef verfijnen door zijn lokale zoekmechanismen, waardoor het lokale optima doorbrak in latere iteraties.

Betekenis
Het artikel beweert dat HGVNSA een efficiënt en robuust oplossingframework biedt voor de FJSP, waarbij het effectief de uitdagingen aanpakt van het balanceren van globale en lokale zoekopdrachten en het ontwerpen van effectieve buurtstructuren. De studie valideert dat het combineren van critical-path-gestuurde lokale zoekopdrachten met genetische evolutie superieure resultaten oplevert in zowel theoretische benchmarks als praktische industriële omgevingen. De auteurs suggereren dat dit werk een fundament legt voor toekomstig onderzoek naar gedistribueerde planning en het gebruik van deep reinforcement learning voor intelligente buurtselectie, hoewel zij niet beweren dat deze uitbreidingen in de huidige studie zijn geïmplementeerd.