🔢 mathematics

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

Diese Arbeit befasst sich mit dem ressourcenbeschränkten Projektplanungsproblem unter Berücksichtigung von Zeitnutzungstarifen und Maschinenzuständen, indem sie einen auf logikbasierter Benders-Zerlegung basierenden Ansatz vorschlägt, der monolithische Methoden bei der Minimierung der Durchlaufzeit und der Energiekosten signifikant übertrifft und gleichzeitig seine Verallgemeinerbarkeit auf andere komplexe Planungsprobleme demonstriert.

Ursprüngliche Autoren: Corentin Juvigny, Antonín Novák, Jan Mandík, Zdeněk Hanzálek

Veröffentlicht 2026-07-07

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Corentin Juvigny, Antonín Novák, Jan Mandík, Zdeněk Hanzálek

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 vor, Sie sind der Manager einer geschäftigen Fabrik. Sie haben eine Liste von Aufgaben zu erledigen, einige Maschinen, die jeweils nur eine Sache gleichzeitig tun können, und einen strengen Satz von Regeln darüber, welche Aufgaben vor anderen stattfinden müssen. Dies ist das klassische „Resource-Constrained Project Scheduling Problem“ (RCPSP). Es ist wie der Versuch, eine riesige Hochzeit zu organisieren, bei der der Caterer, die Band und die Location nur begrenzte Verfügbarkeiten haben und das Anschneiden der Torte nicht vor der Zeremonie stattfinden kann.

Aber jetzt fügen wir eine Wendung hinzu: Die Strompreise ändern sich im Laufe des Tages.

In einigen Stunden ist der Strom günstig (wie um 3 Uhr morgens); in anderen ist er teuer (wie um 17 Uhr). Zudem hat Ihre energiehungrigste Maschine (nennen wir sie den „Großen Ofen“) drei Stimmungen:

Backen (Proc): Er läuft und verbraucht Energie.
Leerlauf (Idle): Er ist warm, aber backt nicht. Er verbraucht ein wenig Energie, um einsatzbereit zu bleiben.
Aus (Off): Er ist kalt. Das Wiedereinschalten kostet Zeit und einen gewaltigen Energieschub.

Ihr Ziel ist es, jede Aufgabe so zu planen, dass Sie den Job so schnell wie möglich erledigen und so wenig Geld wie möglich für Strom ausgeben. Dies ist ein Balanceakt: Backen Sie den Ofen während der günstigen Stunden, auch wenn die gesamte Fabrik dann warten muss? Oder eilen Sie voran, um früh fertig zu werden, auch wenn dies in den Spitzenzeiten ein Vermögen an Stromkosten verursacht?

Das Problem: Ein Rätsel, das zu groß für ein einzelnes Gehirn ist

Die Autoren dieser Arbeit haben versucht, dieses Rätsel mit zwei traditionellen Methoden zu lösen:

Das „monolithische“ ILP: Der Versuch, eine einzige riesige mathematische Gleichung zu schreiben, die jeden einzelnen Task, jede Sekunde der Zeit und jeden Zustand der Maschine gleichzeitig berücksichtigt. Es ist, als würde man versuchen, ein 1.000-Teile-Puzzle zu lösen, während man blind ist und alle Teile in einer Hand hält.
Das „monolithische“ CP: Eine andere Art von Logik-Solver, der sehr gut im Zeitplanen ist, aber Schwierigkeiten bekommt, wenn man die komplexen „Strompreis“-Regeln obenauf setzt.

Beide Methoden funktionierten bei kleinen Rätseln ganz gut, aber als die Fabrik größer wurde (mehr Aufgaben), blieben sie stecken. Sie konnten nicht in einer angemessenen Zeit die beste Lösung finden.

Die Lösung: Der „Küchenchef“ und der „Beikoch“

Die Autoren schlugen einen neuen, klügeren Weg vor, der Logic-Based Benders Decomposition (LBBD) genannt wird. Stellen Sie sich das wie die Aufteilung des Jobs auf zwei Personen mit unterschiedlichen Fähigkeiten vor:

Der Küchenchef (Das Master-Problem): Diese Person ist ein Experte für Geld. Er betrachtet die Strompreis-Tabelle und entscheidet: „Okay, der Große Ofen sollte während dieser günstigen Stunden backen und während der teuren Stunden ruhen.“ Er kümmert sich nicht darum, welcher spezifische Kuchen gerade in den Ofen kommt; er legt einfach den Zeitplan für die „Stimmung“ des Ofens (An, Leerlauf, Aus) fest, um Geld zu sparen. Er nutzt einen schnellen mathematischen Solver (ILP) dazu.
Der Beikoch (Das Subproblem): Diese Person ist ein Experte für Logistik. Er nimmt den Zeitplan des Küchenchefs und fragt: „Können wir tatsächlich alle anderen Aufgaben (die Kuchen, die Dekorationen, die Gäste) um diesen Ofen-Zeitplan herum unterbringen, ohne gegen Regeln zu verstoßen?“ Er nutzt eine leistungsstarke Logik-Engine (Constraint Programming), um zu prüfen, ob der Plan funktioniert.

So kommunizieren sie miteinander:

Der Küchenchef erstellt einen Plan.
Der Beikoch versucht, diesen auszuführen.
Wenn es funktioniert: Großartig! Sie prüfen, ob sie es noch besser machen können.
Wenn es fehlschlägt: Sagt der Beikoch: „Hey, du kannst den Ofen nicht um 14 Uhr in den Modus 'Aus' versetzen, weil der Kuchenteig dann fertig sein muss!“
Der Küchenchef nimmt dieses Feedback, lernt daraus und erstellt einen neuen Plan, der diesen spezifischen Fehler vermeidet.

Sie wiederholen diesen Dialog, bis sie den perfekten Zeitplan gefunden haben.

Was sie herausfanden

Die Autoren testeten diesen „Team-Ansatz“ gegen den „Solo-Ansatz“ in Hunderten von verschiedenen Fabrikszenarien:

Wenn das Ziel rein die Geldersparnis ist (unter Ignorierung der Dauer des Jobs): War der Team-Ansatz (LBBD) ein massiver Gewinner. Er löste Probleme mit bis zu 480 Aufgaben perfekt, während die Solo-Methoden aufgaben oder ewig brauchten. Es war, als hätte man ein GPS, das genau wusste, wann man fahren muss, um Staus zu vermeiden, während der Solo-Fahrer nur raten konnte.
Wenn das Ziel eine Mischung aus Geschwindigkeit und Geld ist: War der Team-Ansatz meistens am besten, besonders für große, überfüllte Fabriken.
Die Ausnahme: Wenn die Fabrik sehr leer war (wenig Aufgaben) und die Geschwindigkeit das einzige Kriterium war, war die alte „Solo-Logik“ (Constraint Programming) manchmal schneller.

Der „Zaubertrick“ (Generalisierung)

Der spannendste Teil der Arbeit ist, dass dieses „Küchenchef / Beikoch“-Teamwork nicht nur für diese spezifische Fabrik gilt. Die Autoren zeigten, dass man dieselbe Teamwork-Strategie für andere Arten von Zeitplanungs-Problemen verwenden kann, wie zum Beispiel:

Flexible Job Shops: Wo eine Aufgabe auf jeder beliebigen von mehreren Maschinen erledigt werden kann.
Projekte mit „Blocking“: Wo eine Maschine blockiert ist, während sie auf ein Teil wartet.

In all diesen Fällen machte die Trennung der Entscheidung „Energie/Geld“ von der Entscheidung „Aufgabe/Zeit“ den Computer deutlich schneller und führte zu besseren Lösungen.

Zusammenfassung

Vereinfacht gesagt sagt diese Arbeit: Versuchen Sie nicht, das gesamte Energie-Zeitplan-Rätsel in einem einzigen riesigen Gehirn zu lösen. Teilen Sie es stattdessen auf. Lassen Sie einen Experten für die Stromrechnungen zuständig sein und einen anderen für die Aufgaben-Logistik. Lassen Sie sie miteinander kommunizieren, bis sie sich auf den besten Plan einigen. Diese Methode ist schneller, intelligenter und kann viel größere, komplexere reale Fabriken bewältigen als die alten Wege.

Technische Zusammenfassung: Ressourcenbeschränktes Projektplanungsproblem mit Zeitabhängigen Stromtarifen und Maschinenzuständen

1. Problemdefinition

Die Arbeit behandelt eine Variante des ressourcenbeschränkten Projektplanungsproblems (Resource-Constrained Project Scheduling Problem, RCPSP), die zeitabhängige Stromtarife (Time-of-Use, TOU) und Maschinenzustandsübergänge integriert. Das Problem umfasst die Planung einer Menge nicht-präemptiver Aufgaben unter Einhaltung von Vorrangbedingungen und begrenzten Ressourcenkapazitäten.

Zu den Hauptmerkmalen gehören:

Energieintensive Ressource: Eine spezifische Ressource ( $R_0$ ) besitzt eine unitäre Kapazität und ist energieintensiv. Sie kann sich in drei Zuständen befinden: proc (verarbeiten), idle (Leerlauf) oder off (aus).
Zustandsübergänge: Übergänge zwischen Zuständen verursachen spezifische Dauern und Energiekosten. Beispielsweise verbraucht das Einschalten oder Ausschalten einer Maschine erhebliche Mengen an Energie und Zeit. Die Maschine muss im Zustand off starten und enden.
Aufgabenklassifizierung: Aufgaben werden in energieintensive Aufgaben (die $R_0$ im Zustand proc erfordern) und nicht energieintensive Aufgaben (die $R_0$ nicht nutzen) unterteilt.
Zielsetzung: Das Ziel ist die Minimierung einer konvexen Kombination aus den Gesamtenergiekosten (Total Energy Cost, TEC) und der Makespan ( $C_{max}$ ). Der TEC wird basierend auf TOU-Tarifen berechnet, die zeitlich variieren können und sogar negative Werte annehmen können. Die Zielfunktion wird unter Verwendung von Untergrenzen normalisiert, die aus unabhängigen Optimierungen der TEC- und $C_{max}$ -Komponenten abgeleitet wurden.

2. Methodik

Die Autoren schlagen drei verschiedene Modellierungsansätze vor und vergleichen diese:

A. Monolithische Modelle
Es werden zwei kompakte Modelle formuliert, um das Problem als Ganzes zu lösen:

Monolithisches ILP: Ein ganzzahliges lineares Programmierungsmodell (Integer Linear Programming) unter Verwendung zeitindexierter Variablen. Es beinhaltet vorab berechnete optimale Übergangskosten (via SPACES-Algorithmus) zwischen Verarbeitungsintervallen, um die Maschinenzustände zu handhaben.
Monolithisches CP: Ein Constraint-Programming-Modell (CP), das optionale Intervallvariablen nutzt. Dieser Ansatz repräsentiert die Aufgabenverarbeitung und optimale Zustandsübergänge als Intervallvariablen, was es dem Solver ermöglicht, die Anzahl und Platzierung der Übergänge dynamisch zu bestimmen.

B. Logic-Based Benders Decomposition (LBBD)
Der Hauptbeitrag ist ein hybrider LBBD-Ansatz, der das Problem in zwei gekoppelte Teilprobleme zerlegt:

Masterproblem (ILP): Löst die Optimierung der Maschinenzustände und Energiekosten. Es bestimmt die Startzeiten der energieintensiven Aufgaben und die Sequenz der Zustandsübergänge. Es verwendet einen modifizierten SPACES-Graphen zur Berechnung der Übergangskosten.
Teilproblem (CP): Eine Durchführbarkeitsprüfung für die RCPSP-Komponente. Gegeben die fixierten Startzeiten der energieintensiven Aufgaben aus dem Masterproblem, versucht es, alle verbleibenden nicht energieintensiven Aufgaben unter Einhaltung der Ressourcenkapazitäten und Vorrangbedingungen zu planen.
Schnitte (Cutting Planes):
- Durchführbarkeitsschnitte (Feasibility Cuts): Werden generiert, wenn das Teilproblem unzulässig ist, um das Masterproblem daran zu hindern, dieselbe konfliktäre Menge an Startzeiten für energieintensive Aufgaben auszuwählen.
- Optimalitätsschnitte (Optimality Cuts): Werden generiert, wenn das Teilproblem zulässig ist, aber eine Makespan liefert, die von der Schätzung des Masters abweicht. Diese Schnitte nutzen den kritischen Pfad des Ressourcenfluss-Graphen, um eine Untergrenze für die Makespan im Masterproblem durchzusetzen.

3. Kernbeiträge

Problemformulierung: Die Einführung einer neuen RCPSP-Variante, die die Dynamik der Maschinenzustände (proc, idle, off) mit TOU-Tarifen koppelt und damit bisherige Einzelmaschinenstudien auf einen Kontext der Multi-Ressourcen-Projektplanung erweitert.
Neuartiger LBBD-Rahmen: Die Entwicklung einer Dekompositionsstrategie, die das Energiemanagement (Master) von der kombinatorischen Planung (Teilproblem) trennt. Die Autoren leiten spezifische Benders-Schnitte ab, die auf die Interaktion zwischen Maschinenzuständen und RCPSP-Beschränkungen zugeschnitten sind.
Verallgemeinerung: Demonstration, dass die LBBD-Architektur für andere Planungsprobleme anwendbar ist, insbesondere:
- RCPSP mit Blockierungszeiten und einem gewichteten Gesamtzustandsziel (Total Weighted Tardiness).
- Flexible Job Shop Scheduling (FJSP).

4. Experimentelle Ergebnisse

Die Experimente wurden an Instanzen durchgeführt, die aus dem PSPLIB-Datensatz stammen, kategorisiert nach der Dichte der energieintensiven Aufgaben (Sparse, Standard, Dense) und variierenden Gewichtungsparametern ( $\alpha$ ) zwischen Energiekosten und Makespan.

Leistung vs. monolithische Modelle:
- Beide monolithischen Ansätze (ILP und CP) werden in den meisten Szenarien vom LBBD übertroffen, insbesondere bei größeren Instanzen (bis zu 480 Aufgaben) und wenn das Kriterium der Makespan weniger dominant ist ( $\alpha \to 1$ ).
- Der LBBD-Ansatz löst Instanzen signifikant schneller optimal als das monolithische CP, welches mit großen Suchräumen kämpft.
- Das monolithische ILP schneidet ordentlich ab, ist aber im Allgemeinen langsamer als LBBD.
Einfluss der Parameter:
- $\alpha = 1$ (Nur Energie): LBBD performt außergewöhnlich gut, da das Teilproblem zu einer reinen Durchführbarkeitsprüfung reduziert wird, die CP-Solver effizient handhaben können.
- $\alpha < 1$ (Gemischte Ziele): LBBD bleibt in Standard- und Dense-Instanzen überlegen. In Sparse-Instanzen mit niedrigem $\alpha$ (hohe Makespan-Gewichtung) übertrifft das monolithische CP jedoch manchmal das LBBD, da die Zeitlimits der Teilprobleme im LBBD die Exploration des Suchraums behindern können.
Verallgemeinerungsergebnisse:
- Bei RCPSP mit Blockierungszeiten fand LBBD für nahezu 90 % der Instanzen optimale Lösungen innerhalb von 30 Minuten, verglichen mit weniger als 5 % für das monolithische CP.
- Im Flexible Job Shop Problem fand LBBD häufiger zulässige Lösungen (107/120 Mal) als das monolithische ILP (83/120 Mal) unter Zeitbeschränkungen.

5. Bedeutung und Behauptungen

Das Paper behauptet, dass der vorgeschlagene LBBD-Ansatz einen bedeutenden Fortschritt für energiebewusste Planungsprobleme mit komplexen Maschinenzuständen darstellt. Seine primäre Bedeutung liegt in der Fähigkeit, die kontinuierliche Optimierung der Energiekosten von den diskreten kombinatorischen Planungsbeschränkungen zu entkoppeln, wodurch jeder Teil durch den am besten geeigneten Solver (ILP für Energie, CP für Planung) gelöst werden kann.

Die Autoren betonen, dass diese Dekomposition nicht nur effektiv für das spezifische RCPSP-TOU-Problem ist, sondern ein verallgemeinerbares Framework für jedes Planungsproblem darstellt, bei dem energieintensive Aktivitäten von der restlichen Ressourcenallokationslogik getrennt werden können. Die Arbeit hebt hervor, dass monolithische Modelle zwar intuitiv sind, aber oft mit der Problemgröße und Komplexität skalieren scheitern, während der LBBD-Ansatz über verschiedene Instanzdichten und Zielgewichtungen hinweg robust bleibt.

Das Paper schließt mit dem Hinweis, dass zukünftige Arbeiten mehrere energieintensive Ressourcen, komplexere Zustandsübergänge und die Integration von Energiespeichern oder lokaler Erzeugung sowie die Auswirkungen der Unsicherheit bei Energietarifen untersuchen könnten.