Datum
2024Autor
Linß, AndreasSchlagwort
510 Mathematik ReihenfolgeproblemBranch-and-Bound-MethodeOptimierungsproblemNP-hartes ProblemGanzzahlige OptimierungMetadata
Zur Langanzeige
Dissertation
Job-shop scheduling with flexible energy prices and time windows: A branch-and-price-and-cut approach
Zusammenfassung
Energy-aware scheduling is crucial in the current economy and green production initiatives. However, with the rise of renewable energy sources, power production is subject to uncertain weather conditions. Hence, within a network, some balancing group managers must maintain a balance between production and demand, which requires precise energy orders for specific times. Therefore, those managers must prioritize accurate energy orders to manage this complex problem.
The primary aim of this thesis is to manage one customer's energy order for a series of energy-dependent tasks efficiently. It is crucial to recognize that energy costs are subject to fluctuations and that the customer's primary concern is to minimize costs, assuming all orders are completed. To embed the customers' interests into a mathematical model, we consider the job-shop scheduling problem with time windows, precedence constraints and machine states, where the challenge is to organize the energy required to process a set of jobs. We aim to create a feasible processing start for each task while ensuring that the machines consume the least amount of energy. To that end, we use an integer programming formulation that couples the scheduling of tasks with the assignment of the corresponding machine states. The objective function is the price of the consumed energy. It turns out that the considered scheduling problem is NP-hard in general. Nevertheless, we present some relevant cases that are solvable in polynomial time. Scheduling problems are notoriously difficult due to the intertwining of time-based events and job processing start times. To address this, we use a time-indexed formulation using many variables. Additionally, proving the optimality of primal solutions becomes increasingly time-consuming as the problem size grows. To handle a huge number of variables, we use presolving rules specifically designed for the problem and involve combinatorial conditions to reduce the number of variables quickly.
The primary aim of this thesis is to manage one customer's energy order for a series of energy-dependent tasks efficiently. It is crucial to recognize that energy costs are subject to fluctuations and that the customer's primary concern is to minimize costs, assuming all orders are completed. To embed the customers' interests into a mathematical model, we consider the job-shop scheduling problem with time windows, precedence constraints and machine states, where the challenge is to organize the energy required to process a set of jobs. We aim to create a feasible processing start for each task while ensuring that the machines consume the least amount of energy. To that end, we use an integer programming formulation that couples the scheduling of tasks with the assignment of the corresponding machine states. The objective function is the price of the consumed energy. It turns out that the considered scheduling problem is NP-hard in general. Nevertheless, we present some relevant cases that are solvable in polynomial time. Scheduling problems are notoriously difficult due to the intertwining of time-based events and job processing start times. To address this, we use a time-indexed formulation using many variables. Additionally, proving the optimality of primal solutions becomes increasingly time-consuming as the problem size grows. To handle a huge number of variables, we use presolving rules specifically designed for the problem and involve combinatorial conditions to reduce the number of variables quickly.
In der energiebewussten Planung von Aufgaben ist die Berücksichtigung von Energiepreisen wirtschaftlich interessant und der Einfluss von erneuerbarer Energie kann nicht vernachlässigt werden. In dieser Dissertation wird das Job-Shop-Scheduling-Problem mit variablen Energiepreisen und Zeitfenstern thematisiert, welches das Planen von Prozessen und die Berücksichtigung von Energiepreisen miteinander verknüpft.
Beim Job-Shop-Scheduling-Problem mit variablen Energiepreisen und Zeitfenstern werden die Startzeitpunkte verschiedener Aufgaben ausgerechnet. Die Aufgaben sind Jobs und Maschinen zugeordnet und müssen in einer vorgegebenen Reihenfolge innerhalb eines Zeitfensters bearbeitet werden. Das Ziel ist die Berechnung eines Schedules, der alle Aufgaben vollständig bearbeitet und gleichzeitig die zugehörigen Energiekosten minimiert. Zur Berechnung der Energiekosten eines Schedules werden die Zustände Offline, Hochfahren, Setup, Arbeiten, Standby und Herunterfahren verwendet. Dabei hat jede Maschine in jedem Zustand einen festen Energiebedarf. In Kombination mit periodenabhängigen Energiepreisen kann unter Berücksichtigung von erlaubten Maschinenzustandswechseln jedem Schedule ein Maschinenzustandsprofil und damit auch ein Zielfunktionswert zugeordnet werden.
Es wird gezeigt, dass das Job-Shop-Scheduling-Problem mit variablen Energiepreisen und Zeitfenstern ein NP-schweres Optimierungsproblem ist. Jedoch stellen sich spezielle Varianten des Job-Shop-Scheduling-Problems als polynomiell lösbar heraus.
In dieser Arbeit wird ein Branch-and-Cut-and-Price-Algorithmus für das Job-Shop-Scheduling-Problem vorgestellt. Dazu wird dieses Problem mit einer zeitindizierten Formulierung als ein ganzzahliges lineares Programm modelliert. Die zeitindizierten Variablen für die Aufgaben beschreiben implizit den Maschinenstatus Setup und Arbeiten. Zusätzlich werden zeitindizierte Variablen für den Maschinenstatus Standby verwendet. Zur Beschreibung der übrigen Maschinenzustände werden Variablen konstruiert, welche beschreiben, dass die Maschine innerhalb eines Intervalls herunterfährt, offline bleibt und wieder hochfährt. Diese Variablen werden Breaks genannt. Es wird gezeigt, dass diese Art der Modellierung stärker als eine zeitindizierte Modellierung der Maschinenzustände ist.
Beim Job-Shop-Scheduling-Problem mit variablen Energiepreisen und Zeitfenstern werden die Startzeitpunkte verschiedener Aufgaben ausgerechnet. Die Aufgaben sind Jobs und Maschinen zugeordnet und müssen in einer vorgegebenen Reihenfolge innerhalb eines Zeitfensters bearbeitet werden. Das Ziel ist die Berechnung eines Schedules, der alle Aufgaben vollständig bearbeitet und gleichzeitig die zugehörigen Energiekosten minimiert. Zur Berechnung der Energiekosten eines Schedules werden die Zustände Offline, Hochfahren, Setup, Arbeiten, Standby und Herunterfahren verwendet. Dabei hat jede Maschine in jedem Zustand einen festen Energiebedarf. In Kombination mit periodenabhängigen Energiepreisen kann unter Berücksichtigung von erlaubten Maschinenzustandswechseln jedem Schedule ein Maschinenzustandsprofil und damit auch ein Zielfunktionswert zugeordnet werden.
Es wird gezeigt, dass das Job-Shop-Scheduling-Problem mit variablen Energiepreisen und Zeitfenstern ein NP-schweres Optimierungsproblem ist. Jedoch stellen sich spezielle Varianten des Job-Shop-Scheduling-Problems als polynomiell lösbar heraus.
In dieser Arbeit wird ein Branch-and-Cut-and-Price-Algorithmus für das Job-Shop-Scheduling-Problem vorgestellt. Dazu wird dieses Problem mit einer zeitindizierten Formulierung als ein ganzzahliges lineares Programm modelliert. Die zeitindizierten Variablen für die Aufgaben beschreiben implizit den Maschinenstatus Setup und Arbeiten. Zusätzlich werden zeitindizierte Variablen für den Maschinenstatus Standby verwendet. Zur Beschreibung der übrigen Maschinenzustände werden Variablen konstruiert, welche beschreiben, dass die Maschine innerhalb eines Intervalls herunterfährt, offline bleibt und wieder hochfährt. Diese Variablen werden Breaks genannt. Es wird gezeigt, dass diese Art der Modellierung stärker als eine zeitindizierte Modellierung der Maschinenzustände ist.
Zitieren
@phdthesis{doi:10.17170/kobra-2024061210342,
author={Linß, Andreas},
title={Job-shop scheduling with flexible energy prices and time windows: A branch-and-price-and-cut approach},
school={Kassel, Universität Kassel, Fachbereich Mathematik und Naturwissenschaften, Institut für Mathematik},
year={2024}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2024$n2024 1500 1/eng 2050 ##0##http://hdl.handle.net/123456789/15859 3000 Linß, Andreas 4000 Job-shop scheduling with flexible energy prices and time windows: A branch-and-price-and-cut approach / Linß, Andreas 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/http://hdl.handle.net/123456789/15859=x R 4204 \$dDissertation 4170 5550 {{Reihenfolgeproblem}} 5550 {{Branch-and-Bound-Methode}} 5550 {{Optimierungsproblem}} 5550 {{NP-hartes Problem}} 5550 {{Ganzzahlige Optimierung}} 7136 ##0##http://hdl.handle.net/123456789/15859
2024-06-19T09:55:42Z 2024-06-19T09:55:42Z 2024 doi:10.17170/kobra-2024061210342 http://hdl.handle.net/123456789/15859 eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ branch and bound job-shop scheduling computational integer programming 510 Job-shop scheduling with flexible energy prices and time windows: A branch-and-price-and-cut approach Dissertation Energy-aware scheduling is crucial in the current economy and green production initiatives. However, with the rise of renewable energy sources, power production is subject to uncertain weather conditions. Hence, within a network, some balancing group managers must maintain a balance between production and demand, which requires precise energy orders for specific times. Therefore, those managers must prioritize accurate energy orders to manage this complex problem. The primary aim of this thesis is to manage one customer's energy order for a series of energy-dependent tasks efficiently. It is crucial to recognize that energy costs are subject to fluctuations and that the customer's primary concern is to minimize costs, assuming all orders are completed. To embed the customers' interests into a mathematical model, we consider the job-shop scheduling problem with time windows, precedence constraints and machine states, where the challenge is to organize the energy required to process a set of jobs. We aim to create a feasible processing start for each task while ensuring that the machines consume the least amount of energy. To that end, we use an integer programming formulation that couples the scheduling of tasks with the assignment of the corresponding machine states. The objective function is the price of the consumed energy. It turns out that the considered scheduling problem is NP-hard in general. Nevertheless, we present some relevant cases that are solvable in polynomial time. Scheduling problems are notoriously difficult due to the intertwining of time-based events and job processing start times. To address this, we use a time-indexed formulation using many variables. Additionally, proving the optimality of primal solutions becomes increasingly time-consuming as the problem size grows. To handle a huge number of variables, we use presolving rules specifically designed for the problem and involve combinatorial conditions to reduce the number of variables quickly. In der energiebewussten Planung von Aufgaben ist die Berücksichtigung von Energiepreisen wirtschaftlich interessant und der Einfluss von erneuerbarer Energie kann nicht vernachlässigt werden. In dieser Dissertation wird das Job-Shop-Scheduling-Problem mit variablen Energiepreisen und Zeitfenstern thematisiert, welches das Planen von Prozessen und die Berücksichtigung von Energiepreisen miteinander verknüpft. Beim Job-Shop-Scheduling-Problem mit variablen Energiepreisen und Zeitfenstern werden die Startzeitpunkte verschiedener Aufgaben ausgerechnet. Die Aufgaben sind Jobs und Maschinen zugeordnet und müssen in einer vorgegebenen Reihenfolge innerhalb eines Zeitfensters bearbeitet werden. Das Ziel ist die Berechnung eines Schedules, der alle Aufgaben vollständig bearbeitet und gleichzeitig die zugehörigen Energiekosten minimiert. Zur Berechnung der Energiekosten eines Schedules werden die Zustände Offline, Hochfahren, Setup, Arbeiten, Standby und Herunterfahren verwendet. Dabei hat jede Maschine in jedem Zustand einen festen Energiebedarf. In Kombination mit periodenabhängigen Energiepreisen kann unter Berücksichtigung von erlaubten Maschinenzustandswechseln jedem Schedule ein Maschinenzustandsprofil und damit auch ein Zielfunktionswert zugeordnet werden. Es wird gezeigt, dass das Job-Shop-Scheduling-Problem mit variablen Energiepreisen und Zeitfenstern ein NP-schweres Optimierungsproblem ist. Jedoch stellen sich spezielle Varianten des Job-Shop-Scheduling-Problems als polynomiell lösbar heraus. In dieser Arbeit wird ein Branch-and-Cut-and-Price-Algorithmus für das Job-Shop-Scheduling-Problem vorgestellt. Dazu wird dieses Problem mit einer zeitindizierten Formulierung als ein ganzzahliges lineares Programm modelliert. Die zeitindizierten Variablen für die Aufgaben beschreiben implizit den Maschinenstatus Setup und Arbeiten. Zusätzlich werden zeitindizierte Variablen für den Maschinenstatus Standby verwendet. Zur Beschreibung der übrigen Maschinenzustände werden Variablen konstruiert, welche beschreiben, dass die Maschine innerhalb eines Intervalls herunterfährt, offline bleibt und wieder hochfährt. Diese Variablen werden Breaks genannt. Es wird gezeigt, dass diese Art der Modellierung stärker als eine zeitindizierte Modellierung der Maschinenzustände ist. open access Linß, Andreas 2024-04-11 5 ungezählte Seiten, 208 Seiten Kassel, Universität Kassel, Fachbereich Mathematik und Naturwissenschaften, Institut für Mathematik Bley, Andreas (Prof. Dr.) Pfetsch, Marc (Prof. Dr.) Reihenfolgeproblem Branch-and-Bound-Methode Optimierungsproblem NP-hartes Problem Ganzzahlige Optimierung publishedVersion false true
Die folgenden Lizenzbestimmungen sind mit dieser Ressource verbunden:
:Urheberrechtlich geschützt