| dc.date.accessioned | 2024-06-19T09:55:42Z | |
| dc.date.available | 2024-06-19T09:55:42Z | |
| dc.date.issued | 2024 | |
| dc.identifier | doi:10.17170/kobra-2024061210342 | |
| dc.identifier.uri | http://hdl.handle.net/123456789/15859 | |
| dc.language.iso | eng | |
| dc.rights | Urheberrechtlich geschützt | |
| dc.rights.uri | https://rightsstatements.org/page/InC/1.0/ | |
| dc.subject | branch and bound | eng |
| dc.subject | job-shop scheduling | eng |
| dc.subject | computational integer programming | eng |
| dc.subject.ddc | 510 | |
| dc.title | Job-shop scheduling with flexible energy prices and time windows: A branch-and-price-and-cut approach | eng |
| dc.type | Dissertation | |
| dcterms.abstract | 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. | eng |
| dcterms.abstract | 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. | ger |
| dcterms.accessRights | open access | |
| dcterms.creator | Linß, Andreas | |
| dcterms.dateAccepted | 2024-04-11 | |
| dcterms.extent | 5 ungezählte Seiten, 208 Seiten | |
| dc.contributor.corporatename | Kassel, Universität Kassel, Fachbereich Mathematik und Naturwissenschaften, Institut für Mathematik | |
| dc.contributor.referee | Bley, Andreas (Prof. Dr.) | |
| dc.contributor.referee | Pfetsch, Marc (Prof. Dr.) | |
| dc.subject.swd | Reihenfolgeproblem | ger |
| dc.subject.swd | Branch-and-Bound-Methode | ger |
| dc.subject.swd | Optimierungsproblem | ger |
| dc.subject.swd | NP-hartes Problem | ger |
| dc.subject.swd | Ganzzahlige Optimierung | ger |
| dc.type.version | publishedVersion | |
| kup.iskup | false | |
| ubks.epflicht | true | |
