💻 computer science

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

Dit artikel introduceert een uitgebreide benchmarksuite bestaande uit 402 gestandaardiseerde instances van het Flexible Job Shop Scheduling-probleem, uitgebreid met werknemersflexibiliteit en onzekerheid, die is ontworpen om rigoureuze, reproduceerbare en domeinoverschrijdende vergelijkingen van diverse optimalisatieoplossers mogelijk te maken via uniforme metrieken, visualisatietools en basisresultaten.

Oorspronkelijke auteurs: David Hutter, Thomas Steinberger, Michael Hellwig

Gepubliceerd 2026-05-06

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: David Hutter, Thomas Steinberger, Michael Hellwig

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://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

Stel je een drukke fabrieksvloer voor. Je hebt een hoop taken die moeten worden uitgevoerd, een vloot machines om het werk te doen, en een team van werknemers om die machines te bedienen. Het doel is simpel: alles zo snel mogelijk afmaken. Maar in de echte wereld wordt het ingewikkeld. Een machine kan sneller zijn in de ene taak dan in de andere, een werknemer kan sneller zijn in een andere taak, en soms gaat een machine stuk of belt een werknemer ziek.

Dit artikel introduceert een nieuwe "Gym" voor computerprogramma's (zogenaamde solvers) die proberen dit planningsraadsel op te lossen. Net als atleten een gestandaardiseerd parcours nodig hebben om hun snelheden te vergelijken, hebben deze planningsprogramma's een eerlijke, consistente reeks problemen nodig om te bewijzen welke het beste is.

Hier is een uitleg van wat de auteurs hebben gebouwd, met eenvoudige analogieën:

1. Het Probleem: Een Chaotische Keuken

Denk aan het Flexible Job Shop Scheduling Problem (FJSSP) als een high-end restaurantkeuken.

De Taken: Verschillende bestellingen die binnenkomen (bijvoorbeeld een biefstuk, een salade, een soep).
De Machines: De ovens, grillroosters en blenders.
De Twist: In tegenstelling tot een simpele keuken waar het grillrooster alleen biefstukken bakt, kan hier het grillrooster ook de salade bereiden als de chef snel genoeg is. Dit is "machineflexibiliteit".

Voeg nu Werknemerflexibiliteit (FJSSP-W) toe.

De Werknemers: De chefs.
De Nieuwe Twist: Niet alleen kan het grillrooster de salade bereiden, maar het maakt ook uit welke chef het spatel vasthoudt. Chef A kan 5 minuten nodig hebben om een biefstuk te grillen, terwijl Chef B er 7 minuten over doet. De computer moet niet alleen uitzoeken welke machine moet worden gebruikt, maar ook welke specifieke werknemer deze moet bedienen om de taak het snelst te voltooien.

2. De Oude Manier: Spelen met Verschillende Regels

Vroeger waren onderzoekers die probeerden betere planningscomputers te bouwen, als mensen die hardlopers wilden vergelijken op verschillende banen.

De ene onderzoeker testte zijn programma op een klein, makkelijk parcours.
De ander testte het zijne op een enorm, modderig veld.
Sommigen gebruikten "perfect weer" (geen storingen), terwijl anderen "regen en wind" (onzekerheid) gebruikten.

Omdat de testbanen zo verschillend waren, kon je niet zeggen of de ene hardloper echt sneller was of gewoon een makkelijker parcours had. Dit maakte het moeilijk om te weten welk computerprogramma echt het beste was.

3. De Nieuwe Oplossing: Een Gestandaardiseerd "Olympisch Stadion"

De auteurs hebben een Benchmarking Suite gecreëerd. Denk hierbij aan een enorm, gestandaardiseerd olympisch stadion met 402 verschillende banen.

De Collectie: Ze hebben 402 bestaande fabrieksscenario's genomen en ze allemaal geüpgraded om de regel "Werknemerflexibiliteit" toe te voegen. Dit creëert een enorme, direct bruikbare bibliotheek van problemen.
Het Weerstation voor "Onzekerheid": Echte fabrieken zijn niet perfect. Machines gaan stuk en werknemers raken moe. Deze nieuwe suite stelt onderzoekers in staat om "chaos" in de test te injecteren. Ze kunnen simuleren:
- Ruis in Verwerkingstijd: Een werknemer kan iets sneller of langzamer zijn dan normaal (zoals een hardloper die een goede of slechte dag heeft).
- Machinestoringen: Een machine stopt plotseling met werken (zoals een hardloper die struikelt).
- Niet-beschikbaarheid van Werknemers: Een werknemer kan niet komen opdagen (zoals een hardloper die geblesseerd raakt).

4. Hoe Het Werkt: Het "Scorebord"

De suite is niet zomaar een lijst met problemen; het is een complete toolkit:

De Filter: Je kunt specifieke types banen kiezen (bijvoorbeeld "Laat me alleen de fabrieken zien met 10 machines en hoge werknemerflexibiliteit"). Dit helpt onderzoekers om specifieke onderdelen van hun programma's te testen.
De Baseline: De suite wordt geleverd met een "Gouden Standaard" score. Het vertelt je de beste mogelijke tijd die tot nu toe is behaald door topprogramma's. Als je nieuwe programma deze score niet kan verslaan, is het nog niet klaar voor de Olympische Spelen.
De Visualisaties: Het zet de resultaten om in makkelijk te lezen diagrammen en grafieken, zodat je in één oogopslag kunt zien welk programma de "Olympisch Kampioen" is.

5. De Eerste Race: Wie Won?

De auteurs testten een paar verschillende computerprogramma's op dit nieuwe stadion om te zien hoe het werkte:

De "Gierige" Solver: Dit is als een hardloper die gewoon de volgende beschikbare baan kiest zonder vooruit te denken. Het was het langzaamst.
De "MILP" Solver: Dit is een zeer strenge, wiskundige hardloper die probeert elke enkele mogelijkheid te berekenen. Het was accuraat maar bleef hangen op de grote, complexe banen (door een gebrek aan geheugen).
De "CP" Solver (Constraint Programming): Deze hardloper was de duidelijke winnaar. Het ging veel beter om met de complexiteit van het toewijzen van werknemers en machines dan de anderen.
De "GA" Solver (Genetisch Algorithm): Deze hardloper werd een sterke tweede, met een methode geïnspireerd door evolutie (proberen en fouten) om goede oplossingen te vinden.

Waarom Dit Belangrijk Is

Voor dit artikel schreeuwden onderzoekers in de leegte, waarbij elk claimde dat hun programma het beste was op basis van hun eigen kleine, unieke tests. Dit artikel bouwt een gemeenschappelijke taal en een eerlijk speelveld.

Het stelt wetenschappers in staat om te zeggen: "Mijn programma is beter dan het jouwe omdat we allebei op precies dezelfde 402 banen hebben gerend, onder precies dezelfde weersomstandigheden." Dit helpt het hele veld om sneller vooruit te komen, wat leidt tot betere software die uiteindelijk echte fabrieken kan helpen efficiënter te draaien, zelfs als er dingen misgaan.

Kortom: Ze hebben een gestandaardiseerde, eerlijke en chaotische "gym" gebouwd waar planningscomputers eindelijk op gelijke voet kunnen concurreren om te zien wie echt het beste is in het organiseren van een drukke fabriek.

Technische Samenvatting: Een Benchmark Suite voor Flexibele Job Shop Scheduling Problemen met Werknemerflexibiliteit onder Onzekerheid

Probleemdefinitie
Het artikel behandelt het Flexibele Job Shop Scheduling Probleem (FJSSP) en zijn uitbreiding, het Flexibele Job Shop Scheduling Probleem met Werknemerflexibiliteit (FJSSP-W). Waar het klassieke FJSSP het toewijzen van bewerkingen aan in aanmerking komende machines omvat om een kostenfunctie te minimaliseren (doorgaans de doorlooptijd), integreert het FJSSP-W bovendien de toewijzing van personeel. Bij dit uitgebreide probleem moet een bewerking niet alleen aan een specifieke machine worden toegewezen, maar ook aan een in aanmerking komende werknemer, waarbij de specifieke machine-werknemercombinatie de verwerkingstijd bepaalt.

Een aanzienlijke lacune die in de literatuur is geïdentificeerd, is het ontbreken van een gestandaardiseerde, systematische benchmarkomgeving voor deze problemen, met name bij het integreren van onzekerheid (bijvoorbeeld stochastische verwerkingstijden, machinestoringen en werknemersonbeschikbaarheid). Bestaand onderzoek vertrouwt vaak op gefragmenteerde, ad-hoc instantiesets of specifieke real-world gevallen die een vergelijking tussen oplossers uit verschillende optimalisatieparadigma's (Wiskundige Programmering, Constraint Programmering en Simulatiegebaseerde Optimalisatie) over domeinen heen belemmeren.

Methodologie en Benchmarkconstructie
De auteurs stellen een uitgebreide, open-source benchmark suite voor, geïmplementeerd in Python. De methodologie omvat drie hoofdbestanddelen:

Verzameling en Uitbreiding van Instanties:
- De suite is gebaseerd op een gecureerde verzameling van 402 distincte FJSSP-instanties afkomstig uit tien gevestigde bronnen (bijvoorbeeld Brandimarte, Hurink, Kacem).
- Deze instanties worden systematisch uitgebreid om FJSSP-W-instanties te creëren. Het uitbreidingsproces wijst een set werknemers ( $W$ ) toe aan elke machine-bewerkingcombinatie.
- Logica voor Werknemer-toewijzing: Voor elk machine-bewerkingpaar wordt een willekeurig aantal in aanmerking komende werknemers gesampled. Verwerkingstijden voor deze nieuwe combinaties worden gegenereerd door te samplen uit een verdeling die is gecentreerd rond de oorspronkelijke machineverwerkingstijd (standaardbereik: 90% tot 110% van de basistijd).
- Karakterisering: De suite documenteert specifieke instantiekarakteristieken, waaronder het aantal banen ( $n$ ), machines ( $m$ ), werknemers ( $w$ ), bewerkingen ( $N$ ), flexibiliteit ( $\beta$ ) en variatie in duur ( $d_v$ ), wat filteren op basis van kenmerken mogelijk maakt.
Modellering van Onzekerheid via Discrete-Event Simulatie (DES):
- De omgeving ondersteunt de simulatie van drie soorten onzekerheid: variabiliteit in verwerkingstijden, machinestoringen en werknemersonbeschikbaarheid.
- Verwerkingstijden: Gemodelleerd met behulp van Beta-verdelingen om inconsistente werksnelheden te simuleren.
- Machinestoringen: Gemodelleerd met behulp van Exponentiële verdelingen voor het optreden (gemiddeld één storing per planning) en Weibull-verdelingen voor de duur (minimaal 10% van de doorlooptijd zonder ruis).
- Werknemersonbeschikbaarheid: Eveneens gemodelleerd met Exponentiële (lagere frequentie) en Weibull-verdelingen (langere duur, minimaal 50% van de doorlooptijd zonder ruis).
- Oplossingen worden weergegeven als Gerichte Acyclische Grafieken (DAG's) om traversering en simulatie van deze stochastische gebeurtenissen te faciliteren.
Evaluatiekader:
- De suite biedt API's voor het laden van instanties, het vertalen van coderingen (bijvoorbeeld tussen FJSSP en FJSSP-W) en het evalueren van prestaties.
- Metrieken: Het primaire doel is het minimaliseren van de doorlooptijd. Voor onzekerheidssimulaties wordt de robuste doorlooptijd ( $C_r$ ) berekend als het gemiddelde werkelijke doorlooptijd over meerdere simulatieruns.
- Statistische Analyse: Het kader omvat tools voor statistische rangschikking (Friedman- en Nemenyitesten) en visualisatie (bijvoorbeeld Nemenyidiagrammen) om de prestaties van oplossers strikt te vergelijken.

Belangrijkste Bijdragen

Gestandaardiseerde Benchmarkverzameling: Het creëren van een vast portfolio van 402 FJSSP-W-instanties, wat reproduceerbaarheid en vergelijkbaarheid tussen studies garandeert.
Open-Source Suite: Een Python-omgeving die meerdere optimalisatieparadigma's (MILP, CP, Evolutionaire Algoritmen) ondersteunt door het verstrekken van noodzakelijke modelrepresentaties en evaluatiefuncties.
Integratie van Onzekerheid: Een systematische methode om stochastiek in probleeminstanties in te brengen, waardoor de ontwikkeling en beoordeling van robuuste optimalisatiestrategieën mogelijk wordt.
Basisresultaten: Verstrekking van "best-known" resultaten afgeleid van state-of-the-art oplossers (Gurobi, IBM CPLEX/OR-Tools en Genetische Algoritmen) onder een gestandaardiseerde tijdslimiet (20 minuten) en hardwareconfiguratie.

Experimentele Resultaten
De auteurs demonstreerden de suite door vier oplossers te vergelijken op de 402 FJSSP-W-instanties:

Constraint Programmering (CP): Presteerde significant beter dan andere benaderingen, met een relatieve afwijking ( $\delta_{rel}$ ) van minder dan 0,25 op meer dan 80% van de instanties.
Genetisch Algoritme (GA): Presteerde goed, met significant betere resultaten dan MILP en Greedy-benaderingen, hoewel het achterbleef bij CP.
Mixed-Integer Lineaire Programmering (MILP): Had moeite met de schaal van het probleem; veel instanties konden niet binnen de tijdslimiet worden opgelost vanwege geheugenbeperkingen en het aantal variabelen.
Greedy Algoritme: Dient als basislijn en presteerde het slechtst.

In robuustheidssimulaties (met gebruik van de Fattahi20-instantie) visualiseerde het kader succesvol de degradatie van plannen onder onzekerheid, waarbij de robuuste doorlooptijd en de robuustheidsquotiënt ( $R$ ) werden berekend om de stabiliteit van het plan te evalueren.

Betekenis en Claims
Het artikel stelt dat dit werk een fundament legt voor gerichte algoritmeontwikkeling en consistente prestatiebeoordeling in onderzoek naar productieplanning. Door de fragmentatie in huidige benchmarkpraktijken aan te pakken, maakt de suite het mogelijk:

Eerlijke Vergelijking: Strikte, reproduceerbare evaluatie over verschillende oplossers en probleemsubdomeinen.
Algoritmeontwikkeling: Ondersteuning bij het ontwikkelen van operatoren voor specifieke probleemgroepen via instantiefiltratie.
Beoordeling van Robuustheid: De mogelijkheid om te evalueren hoe oplossers omgaan met real-world onzekerheden, verdergaand dan deterministische optimalisatie.

De auteurs benadrukken dat hoewel de suite primair is ontworpen voor Simulatiegebaseerde Optimalisatie (SBO) en Evolutionaire Algoritmen, het verstrekken van modelrepresentaties voor MILP en CP een vergelijking tussen paradigma's mogelijk maakt. Zij pleiten voor het gebruik van de vaste instantieset om wetenschappelijke reproduceerbaarheid te waarborgen en roepen op tot transparantie bij het rapporteren van experimentele parameters en hardware-specificaties om toekomstig onderzoek te faciliteren.