Novel variants and applications of the single-item lot-sizing problem

Spiekermann, Nils; Koster, Arie Marinus; Büsing, Christina Maria Katharina

doi:10.18154/RWTH-2019-03433

Novel variants and applications of the single-item lot-sizing problem = Neuartige Varianten und Anwendungen des Single-Item Lot-Sizing Problems

Spiekermann, Nils^RWTH*

2019

Verantwortlichkeitsangabevorgelegt von Nils Spiekermann, M.Sc.

ImpressumAachen 2019

Umfang1 Online-Ressource (vi, 116 Seiten) : Illustrationen, Diagramme

Dissertation, RWTH Aachen University, 2019

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Koster, Arie Marinus (Thesis advisor)^RWTH* ; Büsing, Christina Maria Katharina (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2019-03-22

Online
DOI: 10.18154/RWTH-2019-03433
URL: https://publications.rwth-aachen.de/record/759249/files/759249.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
computational complexity (frei) ; lot-sizing (frei) ; mixed integer linear programming (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
In dieser Arbeit studieren wir neuartige Varianten des Single-Item Lot-Sizing Problems im Kontext von Energieerzeugung, mit einem Fokus auf Koproduktion von Hitze und Strom, in Verbindung mit Wärmespeichern. Diese Varianten resultieren aus der Einbindung von Speichergrenzen, Speicherverlusten und/oder Produktionsgrenzen in die Problemformulierung. Die korrespondierenden Modelle werden hierbei zumeist in der Form ganzzahliger linearer Programme aufgestellt. Zuerst untersuchen wir die Probleme im Hinblick auf ihre theoretische Komplexität. Wir betrachten insbesondere nicht nur lineare Zielfunktionen, sondern auch nichtnegative und nicht-fallende konkave Funktionen. Zudem studieren wir Kostenfunktionen mit der Wagner-Whitin Eigenschaft, welche spekulative Motive ausschließt. Hierbei werden alle Probleme, außer diejenigen, welche die Kombination von stationären Produktionsgrenzen und stationären Verfallsraten kombinieren, entweder als polynomiell lösbar oder NP-vollständig identiﬁziert, wobei Ergebnisse aus der Literatur mit einbezogen werden. Weiterhin untersuchen wir die Struktur des zugrundeliegenden Polytops für die Variante, welche nur Speicherverluste einbindet. Wir modiﬁzieren eine bekannte vollständige Formulierung sowie eine erweiterte Formulierung für das normale Single-Item Lot-Sizing Problem, sodass die Verluste abgedeckt werden. Zuletzt behandeln wir Optimierungsansätze für ein Realbeispiel basierend auf einem Blockheizkraftwerk in Verbindung mit einem Wärmespeicher. Hierbei liegt der Fokus auf dem Umgang mit Unsicherheiten in den Wärmedaten, basierend auf einer gegebenen Vorhersage, primär in einer robusten Art und Weise. Weiterhin wird ein Maß für die realisierte Qualität von Lösungen, beziehungsweise deren Anwendung auf die tatsächliche Realisierung der Daten, entwickelt. Schlussendlich vergleichen wir statische und adaptive Ansätze in einer ausführlichen Rechenstudie, wobei auch stochastische Zielfunktionen und Regularisierungsmethoden eingebunden werden, um instabiles Verhalten zu unterbinden.

In this thesis, we study novel variants of the single-item lot-sizing problem, in the context of energy supply, with a focus on heat and power co-production in combination with heat storage units. These variants result from the inclusion of storage bounds, storage deterioration and/or production bounds in the problem formulation. The corresponding models are primarily regarded in the form of mixed integer linear programs. First, the problems are analyzed with respect to computational complexity. We particularly consider not only linear objective functions, but also study the problems for non-negative and non-decreasing concave ones. Additionally, we study cost functions with the Wagner-Whitin property, that is the absence of speculative motive. Here, all considered problems except those that combine stationary production bounds and stationary deterioration rates are identiﬁed as either polynomially solvable or NP-complete, when including known results from the literature. Moreover, the structure of the underlying convex polytope is studied in the case of only storage deterioration. We modify known ideal and extended formulations for the standard single-item lot-sizing problem to include the deterioration. Lastly, we explore optimization approaches for a real life problem based on a combined heat and power plant in combination with a heat storage tank. Here, the focus lies on ways to handle uncertainty in the heat demand data, based on a given forecast, primarily in a robust manner. Furthermore, a measure for the realized quality of solutions, i.e., their application to the actual realization of the data, is designed. Finally, we compare static and adaptive approaches in an extensive computational study, also incorporating stochastic objective functions and a regularization method, to prevent unstable behavior.

OpenAccess:
PDF
(additional files)