💻 computer science

A Benchmarking Suite for Flexible Job Shop Scheduling Problems with Worker Flexibility under Uncertainty

Dieser Beitrag stellt eine umfassende Benchmark-Suite vor, die aus 402 standardisierten Instanzen des Flexible Job Shop Scheduling Problems besteht, die um Arbeiterflexibilität und Unsicherheit erweitert wurden und dazu dienen, eine rigorose, reproduzierbare und domänenübergreifende Vergleichbarkeit verschiedener Optimierungslöser durch einheitliche Metriken, Visualisierungswerkzeuge und Referenzergebnisse zu ermöglichen.

Ursprüngliche Autoren: David Hutter, Thomas Steinberger, Michael Hellwig

Veröffentlicht 2026-05-06

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: David Hutter, Thomas Steinberger, Michael Hellwig

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich einen geschäftigen Fabrikboden vor. Sie haben eine Reihe von Aufträgen zu erledigen, einen Fuhrpark von Maschinen, die die Arbeit verrichten, und ein Team von Arbeitern, die diese Maschinen bedienen. Das Ziel ist einfach: Alles so schnell wie möglich fertigstellen. Doch in der realen Welt wird es kompliziert. Eine Maschine mag bei einer Aufgabe schneller sein als bei einer anderen, ein Arbeiter bei einer anderen Aufgabe schneller, und manchmal fällt eine Maschine aus oder ein Arbeiter meldet sich krank.

Dieser Beitrag stellt ein neues "Gymnasium" für Computerprogramme (genannt Solver) vor, die versuchen, dieses Planungsproblem zu lösen. Genau wie Athleten eine standardisierte Bahn benötigen, um ihre Geschwindigkeiten zu vergleichen, benötigen diese Planungsprogramme einen fairen, konsistenten Satz von Problemen, um zu beweisen, welches das beste ist.

Hier ist eine Aufschlüsselung dessen, was die Autoren gebaut haben, unter Verwendung einfacher Analogien:

1. Das Problem: Eine chaotische Küche

Stellen Sie sich das Flexible Job Shop Scheduling Problem (FJSSP) als eine gehobene Restaurantküche vor.

Die Aufträge: Verschiedene Bestellungen, die hereinkommen (z. B. ein Steak, ein Salat, eine Suppe).
Die Maschinen: Die Öfen, Grills und Mixer.
Der Twist: Im Gegensatz zu einer einfachen Küche, in der der Grill nur Steaks zubereitet, kann hier der Grill auch den Salat zubereiten, wenn der Koch schnell genug ist. Dies ist "Maschinenflexibilität".

Fügen Sie nun Arbeiterflexibilität (FJSSP-W) hinzu.

Die Arbeiter: Die Köche.
Der neue Twist: Nicht nur kann der Grill den Salat zubereiten, sondern es ist auch wichtig, welcher Koch den Spatel hält. Koch A benötigt vielleicht 5 Minuten, um ein Steak zu grillen, während Koch B 7 Minuten braucht. Der Computer muss nicht nur herausfinden, welche Maschine zu verwenden ist, sondern auch, welcher spezifische Arbeiter sie bedienen soll, um den Auftrag am schnellsten zu erledigen.

2. Der alte Weg: Spielen mit verschiedenen Regeln

Zuvor waren Forscher, die versuchten, bessere Planungscomputer zu entwickeln, wie Menschen, die versuchen, Läufer auf verschiedenen Bahnen zu vergleichen.

Ein Forscher testete sein Programm auf einer kleinen, leichten Bahn.
Ein anderer testete seines auf einem riesigen, schlammigen Feld.
Einige verwendeten "perfektes Wetter" (keine Ausfälle), während andere "Regen und Wind" (Unsicherheit) einsetzten.

Da die Testbahnen so unterschiedlich waren, konnte man nicht sagen, ob ein Läufer tatsächlich schneller war oder einfach nur einen leichteren Kurs hatte. Dies machte es schwierig zu wissen, welches Computerprogramm wirklich das beste war.

3. Die neue Lösung: Ein standardisiertes "Olympiastadion"

Die Autoren schufen eine Benchmarking-Suite. Stellen Sie sich dies als ein riesiges, standardisiertes Olympiastadion mit 402 verschiedenen Bahnen vor.

Die Sammlung: Sie nahmen 402 bestehende Fabrik-Szenarien und aktualisierten sie alle, um die Regel "Arbeiterflexibilität" einzuschließen. Dies schafft eine riesige, einsatzbereite Bibliothek von Problemen.
Die "Unsicherheits"-Wetterstation: Echte Fabriken sind nicht perfekt. Maschinen brechen zusammen, und Arbeiter werden müde. Diese neue Suite ermöglicht es Forschern, "Chaos" in den Test einzuspeisen. Sie können simulieren:
- Verarbeitungszeit-Rauschen: Ein Arbeiter ist vielleicht etwas schneller oder langsamer als üblich (wie ein Läufer an einem guten oder schlechten Tag).
- Maschinenausfälle: Eine Maschine hört plötzlich auf zu arbeiten (wie ein Läufer, der stolpert).
- Arbeiterunverfügbarkeit: Ein Arbeiter kann nicht erscheinen (wie ein Läufer, der sich verletzt).

4. Wie es funktioniert: Die "Anzeigetafel"

Die Suite ist nicht nur eine Liste von Problemen; es ist ein komplettes Werkzeugset:

Der Filter: Sie können bestimmte Arten von Bahnen auswählen (z. B. "Zeige mir nur die Fabriken mit 10 Maschinen und hoher Arbeiterflexibilität"). Dies hilft Forschern, bestimmte Teile ihrer Programme zu testen.
Die Basislinie: Die Suite kommt mit einem "Goldstandard"-Ergebnis. Es gibt Ihnen die bestmögliche Zeit an, die bisher von erstklassigen Programmen erreicht wurde. Wenn Ihr neues Programm dieses Ergebnis nicht schlagen kann, ist es nicht bereit für die Olympischen Spiele.
Die Visualisierungen: Es verwandelt die Ergebnisse in leicht lesbare Diagramme und Grafiken, damit Sie auf einen Blick sehen können, welches Programm der "Olympiasieger" ist.

5. Das erste Rennen: Wer hat gewonnen?

Die Autoren testeten einige verschiedene Computerprogramme auf diesem neuen Stadion, um zu sehen, wie es funktioniert:

Der "Gierige" Solver: Dies ist wie ein Läufer, der einfach die nächste verfügbare Bahn wählt, ohne vorauszudenken. Er war der langsamste.
Der "MILP" Solver: Dies ist ein sehr strenger, mathematischer Läufer, der versucht, jede einzelne Möglichkeit zu berechnen. Er war genau, blieb aber bei den großen, komplexen Bahnen stecken (Speichermangel).
Der "CP" Solver (Constraint Programming): Dieser Läufer war der klare Gewinner. Er bewältigte die Komplexität der Zuweisung von Arbeitern und Maschinen viel besser als die anderen.
Der "GA" Solver (Genetischer Algorithmus): Dieser Läufer belegte einen starken zweiten Platz und verwendete eine Methode, die von der Evolution inspiriert war (Versuch und Irrtum), um gute Lösungen zu finden.

Warum dies wichtig ist

Vor diesem Papier schrien Forscher ins Leere und behaupteten jeweils, ihr Programm sei das beste, basierend auf ihren eigenen winzigen, einzigartigen Tests. Dieses Papier baut eine gemeinsame Sprache und ein faires Spielfeld auf.

Es ermöglicht Wissenschaftlern zu sagen: "Mein Programm ist besser als Ihres, weil wir beide auf exakt denselben 402 Bahnen unter exakt denselben Wetterbedingungen gelaufen sind." Dies hilft dem gesamten Feld, sich schneller vorwärts zu bewegen, was zu besserer Software führt, die schließlich echten Fabriken helfen kann, effizienter zu laufen, selbst wenn Dinge schiefgehen.

Kurz gesagt: Sie bauten ein standardisiertes, faires und chaotisches "Gymnasium", in dem Planungscomputer endlich auf Augenhöhe konkurrieren können, um zu sehen, wer wirklich der Beste darin ist, eine geschäftige Fabrik zu organisieren.

Technischer Überblick: Eine Benchmark-Suite für Flexible Job-Shop-Scheduling-Probleme mit Arbeiterflexibilität unter Unsicherheit

Problemdefinition
Der Beitrag behandelt das Flexible Job-Shop-Scheduling-Problem (FJSSP) und seine Erweiterung, das Flexible Job-Shop-Scheduling-Problem mit Arbeiterflexibilität (FJSSP-W). Während das klassische FJSSP die Zuweisung von Operationen zu geeigneten Maschinen umfasst, um eine Kostenfunktion (typischerweise die Durchlaufzeit) zu minimieren, integriert das FJSSP-W zusätzlich die Zuweisung der Arbeitskräfte. Bei diesem erweiterten Problem muss eine Operation nicht nur einer spezifischen Maschine, sondern auch einem geeigneten Arbeiter zugewiesen werden, wobei die spezifische Kombination aus Maschine und Arbeiter die Bearbeitungszeit bestimmt.

Eine signifikante Lücke, die in der Literatur identifiziert wurde, ist das Fehlen einer standardisierten, systematischen Benchmark-Umgebung für diese Probleme, insbesondere bei der Einbeziehung von Unsicherheit (z. B. stochastische Bearbeitungszeiten, Maschinenausfälle und Arbeitsunfähigkeit). Bestehende Forschung stützt sich häufig auf fragmentierte, ad-hoc Instanzsätze oder spezifische reale Fälle, die einen domänenübergreifenden Vergleich zwischen Lösungsverfahren aus verschiedenen Optimierungsparadigmen (Mathematische Programmierung, Constraint Programming und simulationsbasierte Optimierung) behindern.

Methodik und Aufbau der Benchmark
Die Autoren schlagen eine umfassende, quelloffene Benchmark-Suite vor, die in Python implementiert ist. Die Methodik umfasst drei Hauptkomponenten:

Sammlung und Erweiterung von Instanzen:
- Die Suite basiert auf einer kuratierten Sammlung von 402 distincten FJSSP-Instanzen, die aus zehn etablierten Quellen stammen (z. B. Brandimarte, Hurink, Kacem).
- Diese Instanzen werden systematisch erweitert, um FJSSP-W-Instanzen zu erstellen. Der Erweiterungsprozess weist jeder Maschinen-Operation-Kombination eine Menge von Arbeitern ( $W$ ) zu.
- Logik der Arbeiterzuweisung: Für jedes Maschinen-Operations-Paar wird eine zufällige Anzahl geeigneter Arbeiter gesampelt. Bearbeitungszeiten für diese neuen Kombinationen werden durch Sampling aus einer Verteilung generiert, die um die ursprüngliche Maschinenbearbeitungszeit zentriert ist (Standardbereich: 90 % bis 110 % der Basiszeit).
- Charakterisierung: Die Suite dokumentiert spezifische Instanzmerkmale, einschließlich der Anzahl der Aufträge ( $n$ ), Maschinen ( $m$ ), Arbeiter ( $w$ ), Operationen ( $N$ ), Flexibilität ( $\beta$ ) und der Vielfalt der Dauer ( $d_v$ ), was eine Filterung auf Basis von Merkmalen ermöglicht.
Unsicherheitsmodellierung durch diskrete Ereignissimulation (DES):
- Die Umgebung unterstützt die Simulation von drei Arten von Unsicherheit: Variabilität der Bearbeitungszeiten, Maschinenausfälle und Arbeitsunfähigkeit.
- Bearbeitungszeiten: Werden mittels Beta-Verteilungen modelliert, um inkonsistente Arbeitsgeschwindigkeiten zu simulieren.
- Maschinenausfälle: Werden mittels Exponentialverteilungen für das Auftreten (im Durchschnitt ein Ausfall pro Plan) und Weibull-Verteilungen für die Dauer (mindestens 10 % der durchlaufzeitfreien Durchlaufzeit) modelliert.
- Arbeitsunfähigkeit: Wird ebenfalls mit Exponentialverteilungen (geringere Frequenz) und Weibull-Verteilungen (längere Dauer, mindestens 50 % der durchlaufzeitfreien Durchlaufzeit) modelliert.
- Lösungen werden als gerichtete azyklische Graphen (DAGs) dargestellt, um die Durchquerung und Simulation dieser stochastischen Ereignisse zu erleichtern.
Bewertungsrahmen:
- Die Suite bietet APIs zum Laden von Instanzen, zur Übersetzung von Kodierungen (z. B. zwischen FJSSP und FJSSP-W) und zur Bewertung der Leistung.
- Metriken: Das primäre Ziel ist die Minimierung der Durchlaufzeit. Für Unsicherheitssimulationen wird die robuste Durchlaufzeit ( $C_r$ ) als durchschnittliche tatsächliche Durchlaufzeit über mehrere Simulationsläufe berechnet.
- Statistische Analyse: Der Rahmen enthält Tools für statistische Rangordnungen (Friedman- und Nemenyi-Tests) und Visualisierung (z. B. Nemenyi-Diagramme), um die Leistung von Lösungsverfahren rigoros zu vergleichen.

Hauptbeiträge

Standardisierte Benchmark-Sammlung: Die Erstellung eines festen Portfolios von 402 FJSSP-W-Instanzen, das Reproduzierbarkeit und Vergleichbarkeit über Studien hinweg sicherstellt.
Quelloffene Suite: Eine Python-basierte Umgebung, die mehrere Optimierungsparadigmen (MILP, CP, evolutionäre Algorithmen) unterstützt, indem sie notwendige Modellrepräsentationen und Bewertungsfunktionen bereitstellt.
Integration von Unsicherheit: Eine systematische Methode zur Einführung von Stochastik in Probleminstanzen, die die Entwicklung und Bewertung robuster Optimierungsstrategien ermöglicht.
Basisergebnisse: Bereitstellung von „best-known"-Ergebnissen, die von state-of-the-art-Lösungsverfahren (Gurobi, IBM CPLEX/OR-Tools und genetische Algorithmen) unter einem standardisierten Zeitlimit (20 Minuten) und einer standardisierten Hardware-Konfiguration abgeleitet wurden.

Experimentelle Ergebnisse
Die Autoren demonstrierten die Suite durch den Vergleich von vier Lösungsverfahren an den 402 FJSSP-W-Instanzen:

Constraint Programming (CP): Übertraf andere Ansätze signifikant und erreichte eine relative Abweichung ( $\delta_{rel}$ ) von weniger als 0,25 bei über 80 % der Instanzen.
Genetischer Algorithmus (GA): Leistete gut und übertraf MILP und Greedy-Ansätze signifikant, blieb jedoch hinter CP zurück.
Mixed-Integer Linear Programming (MILP): Hatte Schwierigkeiten mit dem Maßstab des Problems; viele Instanzen konnten aufgrund von Speicherbeschränkungen und Variablenanzahl nicht innerhalb des Zeitlimits gelöst werden.
Greedy-Algorithmus: Diente als Basislinie und schnitt am schlechtesten ab.

In Robustheitssimulationen (unter Verwendung der Instanz Fattahi20) visualisierte der Rahmen erfolgreich die Verschlechterung von Plänen unter Unsicherheit, berechnete die robuste Durchlaufzeit und den Robustheitsquotienten ( $R$ ), um die Stabilität von Plänen zu bewerten.

Bedeutung und Behauptungen
Der Beitrag behauptet, dass diese Arbeit eine Grundlage für die gezielte Algorithmenentwicklung und konsistente Leistungsbewertung in der Produktionsplanungsforschung legt. Durch die Behebung der Fragmentierung in aktuellen Benchmark-Praktiken ermöglicht die Suite:

Faire Vergleichbarkeit: Eine rigorose, reproduzierbare Bewertung über verschiedene Lösungsverfahren und Problem-Teilbereiche hinweg.
Algorithmenentwicklung: Unterstützung bei der Entwicklung von Operatoren für spezifische Problemgruppen durch Instanzfilterung.
Robustheitsbewertung: Die Fähigkeit zu bewerten, wie Lösungsverfahren mit realen Unsicherheiten umgehen, und damit über deterministische Optimierung hinauszugehen.

Die Autoren betonen, dass die Suite zwar primär für simulationsbasierte Optimierung (SBO) und evolutionäre Algorithmen konzipiert ist, ihre Bereitstellung von Modellrepräsentationen für MILP und CP jedoch einen domänenübergreifenden Vergleich ermöglicht. Sie plädieren für die Verwendung des festen Instanzsatzes, um wissenschaftliche Reproduzierbarkeit zu gewährleisten, und fordern Transparenz bei der Berichterstattung über experimentelle Parameter und Hardware-Spezifikationen, um zukünftige Forschung zu erleichtern.