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

  • Neuartige Varianten und Anwendungen des Single-Item Lot-Sizing Problems

Spiekermann, Nils; Koster, Arie Marinus (Thesis advisor); Büsing, Christina Maria Katharina (Thesis advisor)

Aachen (2019)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2019


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 identified 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.


  • Discrete Optimization Teaching and Research Unit [113320]
  • Department of Mathematics [110000]
  • Chair of Mathematics II (for Engineers) [113210]