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

Technische Zusammenfassung: Ein genetischer Algorithmus mit kritischer Pfad-gesteuerter Dual-Nachbarschaftssuche für die flexible Werkstattplanung

Problemdefinition
Die Arbeit befasst sich mit dem Problem der flexiblen Werkstattplanung (Flexible Job Shop Scheduling Problem, FJSP), einer stark NP-schweren Optimierungsherausforderung, die in der modernen Fertigung weit verbreitet ist. Im Gegensatz zum klassischen Werkstattplanungsproblem (JSP), bei dem Operationen feste Maschinenzuweisungen haben, erlaubt das FJSP jeder Operation, auf jeder Maschine aus einer Menge alternativer Kandidaten verarbeitet zu werden, oft mit variierenden Bearbeitungszeiten. Das primäre Ziel ist die Minimierung der Durchlaufzeit ($C_{max}$), definiert als die maximale Abschlusszeit aller Aufträge. Das Problem umfasst sowohl die Bestimmung der Maschinenwahl für jede Operation als auch die Sequenzierung der Bearbeitung auf jeder Maschine unter Einhaltung von Vorrangbeschränkungen und Maschinenverfügbarkeiten.

Methodik: HGVNSA
Die Autoren schlagen einen hybriden genetischen Variable-Neighborhood-Search-Algorithmus (HGVNSA) vor, der einen Genetischen Algorithmus (GA) zur globalen Exploration mit einer kritischen Pfad-gesteuerten Variable-Neighborhood-Search (VNS) zur lokalen Exploitation integriert.

1. Kodierung und Dekodierung: Die Lösung wird mittels einer zwei-schichtigen Kodierung dargestellt: einem Operationssequenz-Vektor (OS) und einem Maschinenwahl-Vektor (MS). Eine aktive Dekodierungsstrategie wird eingesetzt, um zulässige Zeitpläne zu generieren.
2. Populationsinitialisierung: Um Qualität und Diversität auszubalancieren, wird die Ausgangspopulation mittels einer hybriden Strategie generiert: Globale Selektion (60 %, Minimierung der globalen Lastzunahme), Lokale Selektion (30 %, Ausgleich der Last innerhalb der Aufträge) und Zufallsauswahl (10 %).
3. Genetische Operationen:
   • Crossover: Es wird ein auf Path-Relinking (PR) basierender Crossover-Operator eingeführt. Anstatt zufälliger Gen-Vertauschung transformiert er systematisch eine Elternlösung in eine andere, wobei Zwischenlösungen aufgezeichnet und evaluiert werden, um den Suchraum zwischen den Eltern auszunutzen.
   • Mutation: Ein adaptiver Mutationsmechanismus passt die Wahrscheinlichkeiten basierend auf der Fitness des Individuums und der Generationsanzahl an. Es werden zwei Mutationstypen verwendet: OS-Mutation (Umordnung der Operationsreihenfolge) und MS-Mutation (Änderung der Maschinenzuweisungen).
   • Erhaltung der Diversität: Eine auf dem Hamming-Abstand basierende Strategie wird eingesetzt, um die Populationsdiversität aufrechtzuerhalten und eine vorzeitige Konvergenz zu verhindern.
4. Kritischer Pfad-gesteuerter Dual-Nachbarschafts-VNS: Diese lokale Suche, die in den GA-Rahmen eingebettet ist, konzentriert sich auf Operationen, die auf dem kritischen Pfad (dem längsten Pfad im disjunktiven Graphen) liegen. Sie nutzt zwei komplementäre Nachbarschaftsstrukturen:
   • N8-Nachbarschaft: Optimiert die Sequenz der Operationen auf derselben Maschine. Sie erweitert die traditionellen N5-N7-Bewegungen, indem sie es ermöglicht, kritische Operationen außerhalb kritischer Blöcke an die Endpunkte oder die Vor-/Nach-Positionen eines Blocks zu verschieben.
   • k-Insertion-Nachbarschaft: Reallokiert kritische Operationen auf andere Maschinen. Dies beinhaltet das Durchlaufen alternativer Maschinen und das Einfügen der Operation an zulässigen Positionen unter Prüfung auf zyklische Abhängigkeiten.
   • Suchstrategie: Der VNS-Prozess priorisiert die N8-Nachbarschaft (geringerer Rechenaufwand) und wechselt zur k-Insertion (höherer Aufwand, breitere Suche) erst dann, wenn keine Verbesserung gefunden wurde, um ein Gleichgewicht zwischen Effizienz und Explorationstiefe zu gewährleisten.

Wesentliche Beiträge
Die Arbeit skizziert fünf Hauptbeiträge:

1. Hybrider Rahmen: Sie etabliert einen synergetischen „Global Exploration First, Local Exploitation Thereafter“-Rahmen, der die Genauigkeit der Lösung und die Recheneffizienz effektiv ausbalanciert.
2. Integration der Dual-Nachbarschaft: Es ist die erste Integration der N8- und k-Insertion-Nachbarschaften in einen einheitlichen VNS-Rahmen für FJSP. Diese Kombination adressiert sowohl die Intra-Maschinen-Sequenzierung als auch die Inter-Maschinen-Reallokation und verbessert dadurch die lokale Suchkapazität erheblich.
3. Verbesserte genetische Operatoren: Die Einführung des Path-Relinking-Crossovers und der adaptiven Mutationswahrscheinlichkeiten stärkt die Fähigkeit des Algorithmus, den Lösungsraum zu explorieren und die Konvergenzstabilität aufrechtzuerhalten.
4. Benchmark-Leistung: Im Brandimarte MK-Benchmark-Set erreicht HGVNSA konsistent bekannte optimale Lösungen in 6 von 10 Instanzen (MK01-MK04, MK08-MK09) und erzielt die niedrigste durchschnittliche relative prozentuale Abweichung (RPD) von 0,06 % unter den verglichenen Algorithmen (HGWO, HLO-PSO, HA, SLGA, ISLGA).
5. Reale Anwendung: Der Algorithmus wurde auf ein Szenario der Wellenfertigung bei Unternehmen A angewendet. Im Vergleich zu einem traditionellen Genetischen Algorithmus verbesserte HGVNSA die Produktionseffizienz um 8,81 %, was seine praktische technische Anwendbarkeit demonstrit.

Ergebnisse und Validierung

• Benchmark-Tests: Umfangreiche Experimente an den MK01-MK10 Instanzen zeigten, dass HGVNSA die Vergleichsalgorithmen in Bezug auf Lösungsqualität und Stabilität übertraf. Ablationsstudien bestätigten, dass das Entfernen der VNS-Komponente, der Dual-Nachbarschaftsstruktur oder der adaptiven Mechanismen zu einer signifikanten Leistungsverschlechterung führte (z. B. erhöhte das Entfernen von VNS die durchschnittliche Durchlaufzeit auf MK02 von 26 auf 30,4).
• Fallstudie: In der Fallstudie bei Unternehmen A, die 10 Aufträge und 59 Operationen auf 15 Maschinen umfasst, reduzierte der Algorithmus die Durchlaufzeit von 522 (traditioneller GA) auf 476.
• Konvergenz: Die Konvergenzanalyse ergab, dass andere Algorithmen nach einer anfänglichen schnellen Konvergenz stagnierten, während HGVNSA durch seine lokale Suchmechanik die Lösungen weiter verfeinerte und in späteren Iterationen lokale Optima durchbrach.

Bedeutung
Die Arbeit behauptet, dass HGVNSA einen effizienten und robusten Lösungsrahmen für das FJSP bietet und die Herausforderungen beim Ausgleich von globaler und lokaler Suche sowie beim Design effektiver Nachbarschaftsstrukturen effektiv adressiert. Die Studie validiert, dass die Kombination aus kritischer Pfad-gesteuerter lokaler Suche und genetischer Evolution überlegene Ergebnisse sowohl in theoretischen Benchmarks als auch in praktischen industriellen Umgebungen liefert. Die Autoren legen nahe, dass diese Arbeit eine Grundlage für zukünftige Forschung in den Bereichen verteilte Planung und den Einsatz von Deep Reinforcement Learning für die intelligente Nachbarschaftsauswahl bildet, betonen jedoch, dass diese Erweiterungen im Rahmen der aktuellen Studie nicht implementiert wurden.