🔢 mathematics

Resource-constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States: A Logic-based Benders Decomposition Approach

Dit artikel behandelt het Resource-Constrained Project Scheduling Problem met Time-of-Use energietarieven en machinetoestanden door een Logic-Based Benders Decomposition aan te bevelen die monolithische methoden aanzienlijk overtreft in het minimaliseren van de doorlooptijd en energiekosten, terwijl het zijn generaliseerbaarheid naar andere complexe planningsproblemen aantoont.

Oorspronkelijke auteurs: Corentin Juvigny, Antonín Novák, Jan Mandík, Zdeněk Hanzálek

Gepubliceerd 2026-07-07

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Corentin Juvigny, Antonín Novák, Jan Mandík, Zdeněk Hanzálek

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 voor dat je de manager bent van een drukke fabriek. Je hebt een lijst met taken die voltooid moeten worden, enkele machines die tegelijkertijd slechts één ding kunnen doen, en een strikte set regels over welke taken vóór andere moeten plaatsvinden. Dit is het klassieke "Resource-Constrained Project Scheduling Problem" (RCPSP). Het is alsof je een enorme bruiloft probeert te organiseren waarbij de cateraar, de band en de locatie allemaal een beperkte beschikbaarheid hebben, en het aansnijden van de taart niet kan gebeuren vóór de ceremonie.

Maar nu voeg je een draai toe: de elektriciteitsprijzen veranderen gedurende de dag.

Op sommige uren is stroom goedkoop (zoals om 3 uur 's nachts); op andere uren is het duur (zoals om 17:00 uur). Bovendien heeft je meest energieverslindende machine (laten we het de "Grote Oven" noemen) drie stemmingen:

Koken (Proc): De oven is aan het werk en verbruikt energie.
Idel: De oven is warm, maar bakt niets. Hij gebruikt een beetje energie om klaar te blijven staan.
Uit: De oven is koud. Het weer aanzetten kost tijd en een enorme uitbarsting van energie.

Je doel is om elke taak zo in te plannen dat je de klus zo snel mogelijk voltooit en zo min mogelijk geld uitgeeft aan elektriciteit. Dit is een evenwichtsoefening: Laat je de oven draaien tijdens de goedkope uren, zelfs als de hele fabriek dan moet wachten? Of haast je je om vroeg klaar te zijn, ook al kost dat een fortuin aan stroom tijdens de piekuren?

Het Probleem: Een Puzzel Te Groot voor Eén Brein

De auteurs van dit artikel probeerden dit puzzelstukje op te lossen met twee traditionele methoden:

De "Monolithische" ILP: Proberen één gigantische wiskundige vergelijking te schrijven die rekening houdt met elke enkele taak, elke seconde van de tijd en elke machine-toestand tegelijkertijd. Het is alsof je een legpuzzel van 1.000 stukjes probeert op te lossen terwijl je geblinddoekt bent en alle stukjes in één hand houdt.
De "Monolithische" CP: Een andere logische solver die erg goed is in plannen, maar moeite krijgt wanneer je de complexe "elektriciteitsprijs"-regels toevoegt.

Beide methoden werkten redelijk voor kleine puzzels, maar wanneer de fabriek groter werd (meer taken), liepen ze vast. Ze konden niet de beste oplossing vinden binnen een redelijke tijd.

De Oplossing: De "Chef-kok" en de "Lijnkok"

De auteurs stelden een nieuwe, slimmere manier voor genaamd Logic-Based Benders Decomposition (LBBD). Zie dit als het verdelen van de taak tussen twee mensen met verschillende vaardigheden:

De Chef-kok (Het Hoofdprobleem): Deze persoon is een expert in geld. Hij kijkt naar de elektriciteitsprijstabel en beslist: "Oké, de Grote Oven moet koken tijdens deze goedkope uren en rusten tijdens deze dure uurs." Hij maakt zich geen zorgen over welke specifieke taart er in de oven gaat; hij bepaelt alleen het schema voor de "stemming" van de oven (Aan, Idel, Uit) om geld te besparen. Hij gebruikt een snelle wiskundige solver (ILP) om dit te doen.
De Lijnkok (Het Subprobleem): Deze persoon is een expert in logistiek. Hij neemt het oven-schema van de Chef-kok en vraat: "Kunnen we alle andere taken (de taarten, de decoraties, de gasten) rondom dit oven-schema plannen zonder de regels te breken?" Hij gebruikt een krachtige logische engine (Constraint Programming) om te controleren of het plan werkt.

Hoe ze met elkaar communiceren:

De Chef-kok maakt een plan.
De Lijnkok probeert het uit te voeren.
Als het werkt: Geweldig! Ze kijken of ze het nog beter kunnen doen.
Als het mislukt: De Lijnkok zegt: "Hé, je kunt de oven niet in de 'Uit'-modus zetten om 14:00 uur, want de taartbeslag moet dan klaar zijn!"
De Chef-kok neemt deze feedback mee, leert ervan en maakt een nieuw plan dat die specifieke fout vermijdt.

Ze herhalen dit gesprek totdat ze het perfecte schema hebben gevonden.

Wat Ze Vonden

De auteurs testten deze "Team-aanpak" tegen de "Solo-aanpak" in honderden verschillende fabrieksscenario's:

Wanneer het doel puur het besparen van geld is (het negeren van hoe lang de klus duurt): De Team-aanpak (LBBD) was een enorme winnaar. Het loste problemen met wel 480 taken perfect op, terwijl de solo-methoden opgaven of er eeuwen over deden. Het was alsof je een GPS had die precies wist wanneer je moest rijden om files te vermijden, terwijl de solo-chauffeur gewoon gokte.
Wanneer het doel een mix is van snelheid en geld: De Team-aanpak was meestal nog steeds de beste, vooral voor grote, drukke fabrieken.
De Uitzondering: Als de fabriek erg leeg was (weinig taken) en snelheid de enige prioriteit was, was de oude "Solo-logica" (Constraint Programming) soms sneller.

De "Tovertruc" (Generalisatie)

Het meest opwindende deel van het artikel is dat deze "Chef-kok / Lijnkok"-teamwork niet alleen voor deze specifieke fabriek is. De auteurs lieten zien dat je deze zelfde teamwork-strategie kunt gebruiken voor andere planningsproblemen, zoals:

Flexibele Job Shops: Waarbij een taak op elke van de verschillende machines kan worden uitgevoerd.
Projecten met "Blocking": Waarbij een machine vastzit in afwachting van een onderdeel dat moet arriveren.

In al deze gevallen maakte het splitsen van de "Energie/Geld"-beslissing van de "Taak/Tijd"-beslissing de computer veel sneller in staat om het probleem op te lossen en betere oplossingen te vinden.

Samenvatting

In eenvoudige bewoordingen zegt dit artikel: Probeer niet de hele energie-planningspuzzel in één gigantisch brein op te lossen. Verdeel het in plaats daarvan. Laat een expert de elektriciteitsrekeningen afhandelen en een andere expert de logistiek van de taken. Laat ze met elkaar praten totdat ze het eens zijn over het beste plan. Deze methode is sneller, slimmer en kan veel grotere, complexere real-world fabrieken aan dan de oude manieren.

Technische Samenvatting: Resource-Constrained Project Scheduling met Time-of-Use Energietarieven en Machinetoestanden

1. Probleemdefinitie

Het artikel behandelt een variant van het Resource-Constrained Project Scheduling Problem (RCPSP) die Time-of-Use (TOU) energietarieven en machine-toestandsovergangen integreert. Het probleem betreft het plannen van een set niet-preemptieve taken onderhevig aan precedentiebeperkingen en beperkte capaciteiten van middelen.

Belangrijke kenmerken zijn:

Energie-intensief middel: Eén specifiek middel ( $R_0$ ) heeft een unitaire capaciteit en is energie-intensief. Het kan zich in drie toestanden bevinden: proc (verwerken), idle (stationair) of off (uit).
Toestandsovergangen: Overgangen tussen toestanden brengen specifieke duur en energiekosten met zich mee. Bijvoorbeeld, het inschakelen of uitschakelen van een machine verbruikt aanzienlijke energie en tijd. De machine moet in de off-toestand beginnen en eindigen.
Taakclassificatie: Taken worden verdeeld in energie-intensieve taken (die $R_0$ in de proc-toestand vereisen) en niet-energie-intensieve taken (die $R_0$ niet gebruiken).
Doelstelling: Het doel is om een convexe combinatie te minimaliseren van de Totale Energiekosten (TEC) en de Makespan ( $C_{max}$ ). De TEC wordt berekend op basis van TOU-tarieven, die in de tijd kunnen variëren en zelfs negatieve waarden kunnen aannemen. De doelfunctie wordt genormaliseerd met behulp van ondergrenzen afgeleid van onafhankelijke optimalisaties van de respectievelijke TEC- en $C_{max}$ -componenten.

2. Methodologie

De auteurs stellen drie verschillende modelleringsbenaderingen voor en vergelijken deze:

A. Monolithische Modellen
Twee compacte modellen worden geformuleerd om het probleem als geheel op te lossen:

Monolithische ILP: Een Integer Linear Programming model dat gebruikmaakt van tijd-geïndexeerde variabelen. Het incorporeert vooraf berekende optimale overgangskosten (via het SPACES-algoritme) tussen verwerkingsintervallen om machinetoestanden te beheren.
Monolithische CP: Een Constraint Programming model dat gebruikmaakt van optionele intervalvariabelen. Deze benadering stelt taakverwerking en optimale toestandsovergangen voor als intervalvariabelen, waardoor de solver dynamisch het aantal en de plaatsing van transities kan bepalen.

B. Logic-Based Benders Decomposition (LBBD)
De primaire bijdrage is een hybride LBBD-benadering die het probleem ontleedt in twee gekoppelde subproblemen:

Master Problem (ILP): Lost de optimalisatie van machinetoestanden en energiekosten op. Het bepaalt de starttijden van energie-intensieve taken en de sequentie van toestandsovergangen. Het maakt gebruik van een aangepaste SPACES-graaf om overgangskosten te berekenen.
Subproblem (CP): Een haalbaarheidscontrole voor het RCPSP-component. Gegeven de vaste starttijden van energie-intensieve taken vanuit de Master, probeert het alle overige niet-energie-intensieve taken te plannen terwijl de capaciteit van middelen en precedentiebeperkingen worden gerespecteerd.
Snijvlakken (Cutting Planes):
- Haalbaarheids-cuts (Feasibility Cuts): Genereren wanneer het subprobleem onhaalbaar is, om te voorkomen dat de Master dezelfde conflicterende set starttijden voor energie-intensieve taken selecteert.
- Optimaliteits-cuts (Optimality Cuts): Genereren wanneer het subprobleem haalbaar is maar een andere makespan oplevert dan de schatting van de Master. Deze cuts gebruiken het kritieke pad van de resource-flow graaf om een ondergrens op de makespan in de Master op te leggen.

3. Belangrijkste Bijdragen

Probleemformulering: De introductie van een nieuwe RCPSP-variant die machine-toestandsdynamiek (proc, idle, off) koppelt aan TOU-tarieven, waarmee eerdere studies naar enkelvoudige machines worden uitgebreid naar een projectplanning met meerdere middelen.
Nieuw LBBD-framework: De ontwikkeling van een decompositiestrategie die energiebeheer (Master) scheidt van combinatorische planning (Subproblem). De auteurs leiden specifieke Benders-cuts af die op maat zijn gemaakt voor de interactie tussen machinetoestanden en RCPSP-beperkingen.
Generalisatie: Demonstratie dat de LBBD-architectuur toepasbaar is op andere planningsproblemen, specifiek:
- RCPSP met blokkertijden en een doelstelling van totale gewogen tardiness.
- Flexible Job Shop Scheduling (FJSP).

4. Experimentele Resultaten

Experimenten werden uitgevoerd op instanties afgeleid van de PSPLIB-dataset, gecategoriseerd op basis van de dichtheid van energie-intensieve taken (Sparse, Standard, Dense) en variërende wegingsparameters ( $\alpha$ ) tussen energiekosten en makespan.

Prestaties versus Monolithische Modellen:
- Zowel de monolithische ILP- als de CP-benaderingen worden door de LBBD overtroffen in de meeste scenario's, met name voor grotere instanties (tot 480 taken) en wanneer de makespan-criterium minder dominant is ( $\alpha \to 1$ ).
- De LBBD-benadering lost instanties tot optimaliteit aanzienlijk sneller op dan de monolithische CP, die moeite heeft met grote zoekruimtes.
- De monolithische ILP presteert redelijk goed, maar is over het algemeen trager dan LBBD.
Impact van Parameters:
- $\alpha = 1$ (Alleen energie): De LBBD presteert uitzonderlijk goed, aangezien het subprobleem reduceert tot een zuivere haalbaarheidscontrole, die CP-solvers efficiënt afhandelen.
- $\alpha < 1$ (Gemengde doelstellingen): LBBD blijft superieur in Standard en Dense instanties. Echter, in Sparse instanties met een lage $\alpha$ (hoge makespan-weging), presteert de monolithische CP soms beter dan LBBD omdat de tijdslimieten van het subprobleem in LBBD de exploratie van de zoekruimte kunnen hinderen.
Generalisatie-resultaten:
- In de RCPSP met blokkertijden vond LBBD optimale oplossingen voor bijna 90% van de instanties binnen 30 minuten, vergeleken met minder dan 5% voor de monolithische CP.
- In het Flexible Job Shop-probleem vond LBBD vaker haalbare oplossingen (107/120 keer) dan de monolithische ILP (83/120 keer) onder tijdsrestricties.

5. Betekenis en Claims

Het artikel claimt dat de voorgestelde LBBD-benadering een significante vooruitgang vormt voor energiebewuste planningsproblemen met complexe machinetoestanden. De primaire betekenis ligt in het vermogen om de continue optimalisatie van energiekosten te ontkoppelen van de discrete combinatorische planningsbeperkingen, waardoor elk deel kan worden opgelost door de meest geschikte solver (ILP voor energie, CP voor planning).

De auteurs stellen dat deze decompositie niet alleen effectief is voor het specifieke RCPSP-TOU probleem, maar een generaliseerbaar framework is voor elk planningsprobleem waarbij energie-intensieve activiteiten gescheiden kunnen worden van de rest van de middelenallocatielogica. Het werk benadrukt dat hoewel monolithische modellen intuïtief zijn, ze vaak niet schalen met de omvang en complexiteit van het probleem, terwijl de LBBD-benadering robuust blijft over variërende instantiedichtheden en doelstelling-wegingen.

Het artikel concludeert door te merken dat toekomstig werk de mogelijkheden kan verkennen van meerdere energie-intensieve middelen, complexere toestandsovergangen en de integratie van energieopslag of on-site generatie, evenals de impact van onzekerheid in energietarieven.