Solution of a bilevel optimistic scheduling problem on parallel machines

Dit artikel presenteert een NP-moeilijkheidsbewijs en een hybride exacte oplossing (MIP en branch-and-bound met kolomgeneratie) voor een optimistische bilevel-planningsprobleem op uniforme parallelle machines, waarbij de leider de gewogen aantal vertraagde taken minimaliseert en de volger de totale voltooiingstijd, met succesvolle tests tot 80 taken.

De kern

Hier is een uitleg van het onderzoek in gewoon Nederlands, met behulp van alledaagse vergelijkingen om de complexe wiskunde begrijpelijk te maken.

De Kern: Een Hiërarchie van Beslissingen

Stel je een grote fabriek voor die producten moet maken. In deze fabriek werken twee soorten managers die met elkaar moeten samenwerken, maar niet op gelijke voet.

1. De Baas (De Leider): Dit is de fabrieksdirecteur. Hij moet beslissen welke bestellingen hij überhaupt gaat aannemen. Zijn doel is simpel: hij wil zo min mogelijk klachten van klanten hebben (producten die te laat zijn). Hij wil dus alleen die bestellingen kiezen die hij zeker op tijd kan leveren.
2. De Uitvoerder (De Volger): Dit is de ploegleider op de vloer. Als de Baas een lijst met bestellingen heeft gekozen, moet de Uitvoerder beslissen hoe hij die bestellingen op de machines gaat draaien. De Uitvoerder heeft zijn eigen doel: hij wil dat de machines zo efficiënt mogelijk werken en dat alle producten zo snel mogelijk klaar zijn (minimale wachttijd).

Het spannende deel: De Uitvoerder is slim. Als er meerdere manieren zijn om alles even snel af te werken, kiest hij altijd de manier die het beste is voor de Baas. Dit noemen ze in de vakwereld een "optimistische" situatie. De Baas weet dit en probeert zijn beslissingen zo te nemen dat hij, rekening houdend met de slimme keuzes van de Uitvoerder, het beste resultaat krijgt.

Het Probleem: Twee Snelheden

De machines in deze fabriek werken niet allemaal even snel.

• Sommige machines zijn snel (zoals een sportauto).
• Andere machines zijn langzaam (zoals een oude vrachtwagen), misschien omdat ze onderhoud nodig hebben of ouder zijn.

De Uitvoerder moet de bestellingen verdelen over deze snelle en trage machines. Als hij een bestelling op een trage machine doet, duurt het langer. Als hij het op een snelle machine doet, gaat het snel. Maar hij moet ook opletten dat hij niet te veel bestellingen op de trage machines gooit, want dan lopen ze vertraging op.

Waarom is dit zo moeilijk?

Het klinkt simpel, maar het is een enorme puzzel. Waarom?

• De Combinatie: De Baas moet uit honderden bestellingen een selectie maken. Er zijn zoveel mogelijke combinaties dat het voor een computer onmogelijk is om ze allemaal één voor één te proberen. Het is alsof je probeert alle mogelijke wegen in een enorm doolhof te lopen om de kortste te vinden, terwijl de doolhof zelf ook nog eens verandert.
• De Wiskundige Val: De onderzoekers hebben bewezen dat dit probleem "NP-hard" is. In het Nederlands betekent dit: het is een probleem dat zo complex is dat er waarschijnlijk geen snelle formule bestaat om het voor elke situatie op te lossen. Hoe groter de fabriek (meer machines, meer bestellingen), hoe explosief de moeilijkheid toeneemt.

De Oplossing: Slimme Trucs

De auteurs van het artikel hebben geen magische formule gevonden die alles in één seconde oplost, maar ze hebben wel slimme methoden bedacht om het probleem toch op te lossen voor redelijk grote fabrieken.

1. De "Blokken"-Strategie:
   Ze hebben ontdekt dat de Uitvoerder (de ploegleider) altijd een bepaald patroon volgt om de machines zo snel mogelijk te laten werken. Het is alsof je een stapel borden moet ordenen: je zet ze altijd in een specifieke volgorde neer om ruimte te besparen. De onderzoekers gebruiken dit patroon (noem het "blokken") om het probleem te vereenvoudigen. In plaats van te kijken naar elke individuele machine, kijken ze naar groepen (blokken) die samenwerken.

2. De "Branch-and-Bound" Methode (Zoeken met een Net):
   Stel je voor dat je een schat zoekt in een groot bos. Je zou elk stukje bos kunnen doorzoeken, maar dat duurt eeuwen.

   • Branch (Verzorgen): Je maakt een kaart en splitst het bos op in kleinere stukken.
   • Bound (Begrenzen): Je gebruikt een kompas (een wiskundige berekening) om te zien welke stukken bos nooit de schat kunnen bevatten. Als je ziet dat een stuk bos te ver weg is, gooi je die tak van de kaart direct weg. Je hoeft daar niet te zoeken.
     De onderzoekers gebruiken een geavanceerde versie van dit kompas (genaamd Column Generation) om snel te zien welke combinaties van bestellingen hopeloos zijn en die direct af te vallen.

3. Het Geheugen (Memorization):
   Omdat de computer vaak dezelfde stukjes van het doolhof tegenkomt, laten ze de computer een "geheugen" gebruiken. Als de computer al eens heeft gezien dat een bepaalde situatie slecht is, onthoudt hij dat en doet hij die weg niet nog een keer. Dit bespaart enorm veel tijd.

Wat hebben ze ontdekt?

• Het is echt moeilijk: Zelfs met de slimste computers en de beste algoritmen kunnen ze momenteel alleen fabrieken met ongeveer 80 bestellingen en 4 machines perfect oplossen. Als je meer machines of bestellingen toevoegt, wordt het probleem te groot voor de huidige technologie.
• De Baas vs. De Volger: Het is verrassend dat het moeilijkste moment voor de Baas (de selectie van bestellingen) niet altijd het moeilijkste moment is voor het hele systeem. Soms helpt het juist als er meer bestellingen zijn, omdat de Uitvoerder dan meer vrijheid heeft om slimme keuzes te maken binnen zijn blokken.
• Toekomst: Voor heel grote fabrieken (zoals in de "Industrie 4.0" van de toekomst) zullen ze waarschijnlijk moeten vertrouwen op slimme schattingen (heuristieken) of kunstmatige intelligentie, omdat exacte oplossingen te lang duren.

Samenvattend

Dit artikel gaat over het vinden van de perfecte balans tussen een directeur die bestellingen kiest en een ploegleider die ze uitvoert op machines met verschillende snelheden. Het is een enorme logistieke puzzel die wiskundig gezien extreem moeilijk is. De onderzoekers hebben bewezen dat er geen snelle "one-size-fits-all" oplossing is, maar ze hebben wel een zeer slimme manier bedacht om de zoektocht te versnellen door slim te "snijden" in de mogelijke opties en door slimme patronen te gebruiken. Voor nu is het een succes voor middelgrote fabrieken, maar voor de gigantische fabrieken van de toekomst is er nog veel werk te doen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Solution of a bilevel optimistic scheduling problem on parallel machines" in het Nederlands.

Titel: Oplossing van een bilevel optimistisch planningsprobleem op parallelle machines

1. Probleembeschrijving

Het artikel behandelt een complex planningsprobleem in de context van bilevel optimalisatie met een optimistische instelling. Het scenario omvat:

• Systeem: Een set van uniforme parallelle machines ($m$ stuks) die werken op twee verschillende snelheden: een hoge snelheid ($V_1$) en een lage snelheid ($V_0$).
• Actoren:
  • Leider (Leader): Beslist welke $n$ taken uit een grotere set van $N$ taken worden geselecteerd en toegewezen aan de volger. Het doel van de leider is het minimaliseren van het gewogen aantal vertraagde taken ($\sum w_j U_j^L$).
  • Volger (Follower): Ontvangt de geselecteerde taken en plant deze op de machines om het totaal van de voltooiingstijden ($\sum C_j^F$) te minimaliseren.
• Optimistische Aanneming: Als de volger meerdere optimale oplossingen heeft voor zijn eigen doel (minimale totale voltooiingstijd), kiest hij degene die het beste is voor de leider (d.w.z. het minst aantal vertraagde taken).
• Toepassing: Dit model is relevant voor Industrie 4.0, waar autonome cyber-fysische systemen (CPS) hiërarchisch samenwerken. De leider (het systeem) kan bijvoorbeeld machines met onderhoudsrisico's op een lage snelheid zetten, terwijl gezonde machines op volle snelheid draaien.

2. Methodologie en Algoritmen

De auteurs ontwikkelen een combinatie van theoretische analyses en exacte oplossingsmethoden:

A. Complexiteitsanalyse:

• Het probleem wordt bewezen sterk NP-hard te zijn door een reductie van het Numerical 3-Dimensional Matching (NUM-3DM) probleem.
• Voor de volger alleen (geen leiderskeuze) is het probleem in het algemeen NP-hard (sterk voor het geval met willekeurige snelheden en taken, zwak voor het geval met identieke taken).
• Er wordt aangetoond dat het probleem niet tot de tweede laag van de polynoomhiërarchie ($\Sigma_2^P$) behoort, maar NP-hard is in de sterke zin.

B. Structuur van de Oplossing (Block Structure):

• Voor het probleem van de volger ($Q|V_i|\sum C_j$) geldt een specifieke structuur: de optimale planning bestaat uit blokken. Taken binnen een blok kunnen onderling worden verwisseld zonder de totale voltooiingstijd te beïnvloeden.
• De volger sorteert taken volgens de Shortest Processing Time (SPT) regel op de eerst beschikbare machine, maar door de twee snelheden ontstaat een patroon van herhalende blokken.

C. Exacte Oplossingsmethoden:

1. Mixed Integer Programming (MIP):
   • Een compacte MIP-formulering met een polynoomaantal variabelen en constraints.
   • Deze formulering maakt het mogelijk om het probleem als een enkel niveau probleem op te lossen, hoewel de schaalbaarheid beperkt blijft.
2. Branch-and-Bound (BaB) met Column Generation:
   • Dit is de hoofdmethode voor het oplossen van grotere instanties.
   • Branching: Gebaseerd op de blokkenstructuur. De boom wordt opgebouwd door beslissingen te nemen over welke taken in welke blokken worden geplaatst.
   • Memorization (Branch-and-Memorize): Een techniek om de zoekboom te verkleinen door gedeeltelijke oplossingen te onthouden en te controleren op dominantie (Theorema 2.7). Als een nieuwe knoop gedomineerd wordt door een eerder bezochte knoop, wordt de tak afgesneden.
   • Lower Bound (Ondergrens): Berekend via Column Generation. Het hoofdstuk (Master Problem) selecteert machine-planningen (kolommen) om een ondergrens te vinden voor het gewogen aantal vertraagde taken. Het prijsvraag (Pricing Problem) wordt opgelost met dynamische programmering om kolommen met negatieve gereduceerde kosten te vinden.
3. Dynamische Programmering (DP):
   • Een exacte DP-algoritme met een matig exponentiële tijdcomplexiteit ($O(2^m \cdot (\sum p_j)^m \cdot N \cdot n^2 \log n)$). Dit is voornamelijk van theoretisch belang en werkt goed voor een vast aantal machines.

3. Belangrijkste Bijdragen

• Complexiteitsbewijs: Het eerste bewijs dat dit specifieke bilevel planningsprobleem op uniforme machines met twee snelheden sterk NP-hard is.
• Nieuwe Formuleringsstrategie: Een MIP-model dat de blokkenstructuur van de volger integreert, waardoor het probleem effectiever kan worden gemodelleerd dan met standaard bilevel-programmering.
• Hybride Exacte Algoritme: Een geavanceerde Branch-and-Bound implementatie die Column Generation combineert met Memorization en dominantie-regels. Dit is een zeldzame combinatie die specifiek is ontworpen voor deze klasse van bilevel problemen.
• Analyse van de "Hardheid": De auteurs tonen aan dat het moeilijkste scenario voor de leider (selectie van $n=N/2$ taken) niet noodzakelijk het moeilijkste is voor het bilevel-probleem, vanwege de flexibiliteit die de blokkenstructuur van de volger biedt.

4. Experimentele Resultaten

De auteurs hebben hun algoritmen getest op willekeurig gegenereerde instanties (tot 80 taken en 4 machines) en vergeleken met de CPLEX solver op de MIP-formulering:

• Prestaties: De Branch-and-Bound (BaB) methode presteert over het algemeen beter dan de pure MIP-aanpak, vooral wat betreft de rekentijd en het aantal opgeloste instanties.
• Schaalbaarheid:
  • Instanties met tot 40 taken en 2 of 4 machines worden efficiënt opgelost door beide methoden.
  • Voor 80 taken en 4 machines wordt het probleem zeer uitdagend; alleen BaB kan een subset van deze instanties binnen een redelijke tijd (300 sec) oplossen, terwijl MIP vaak faalt.
  • De BaB-methode explodeert in complexiteit bij een toenemend aantal machines (door de exponentiële groei van de branching-factor), maar blijft superieur voor 2 en 4 machines.
• Memorization: Het gebruik van memorization (het opslaan van bezochte knopen) bleek cruciaal voor de efficiëntie van de diepte-eerst zoekstrategie.

5. Betekenis en Conclusie

Dit onderzoek vult een belangrijke lacune in de literatuur over bilevel planningsproblemen op. Hoewel het planningsprobleem van de volger alleen in polynoomtijd oplosbaar is, maakt de interactie met de leider (selectie van taken) het probleem extreem moeilijk.

• Praktische relevantie: De methoden bieden inzicht in hoe autonome systemen in de toekomstige industrie taken kunnen plannen onder onzekerheid en beperkte resources.
• Beperkingen: Zelfs met geavanceerde exacte algoritmen blijven grote instanties (>80 taken) onoplosbaar binnen redelijke tijd.
• Toekomstig werk: De auteurs suggereren de ontwikkeling van heuristieken (bijvoorbeeld Beam Search gebaseerd op de BaB) of het gebruik van Machine Learning om de beslissingen van de volger te benaderen, om grootschalige industriële problemen aan te pakken.

Samenvattend biedt dit artikel een robuust theoretisch kader en een state-of-the-art exacte oplossing voor een complex bilevel probleem, met de conclusie dat het een van de meest uitdagende problemen in het huidige planningsonderzoek blijft.