Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Efficient algorithms for production scheduling

: Wortel, Pascal
: Krumke, S.O.; Lübbecke, M.

Fulltext urn:nbn:de:0011-n-5901316 (909 KByte PDF)
MD5 Fingerprint: 8f612c4761eaf574765ecb6d9d2fb36d
Created on: 27.5.2020

Stuttgart: Fraunhofer Verlag, 2020, IX, 135 pp.
Zugl.: Kaiserslautern, TU, Diss., 2019
ISBN: 978-3-8396-1609-3
Dissertation, Electronic Publication
Fraunhofer ITWM ()
discrete mathematic; combinatorics & graph theory; algorithms & data structures; robust optimization; buffer allocation; residence time minimization; scheduling problems; inventory constraints; angewandte Mathematiker; Berechnungsingenieur

Scheduling problems play an important role in the area of production planning. However, due to e.g. uncertainties, real-world applications may induce additional constraints, and lead to intractable models. In the literature, approximated solutions are often computed. This thesis aims to derive exact yet tractable algorithms for different scheduling problems under robustness or inventory constraints.
First, we consider the notoriously NP-hard Buffer Allocation Problem (BAP) in flow lines. In its classical approach, it assumes that the processing times of jobs are known in advance. Realistically, this is not the case. Therefore, we present a model for the BAP with additional robustness constraints. We compute exact solutions and demonstrate the tractability of our method.
Next, we lay focus on inventory-constrained scheduling. In this setting, jobs are assumed to add or remove a given amount of material from a common stack. We identify a new class of such problems, where the objective function only depends on the consuming jobs. We provide complexity results and algorithms for variations of the problem with different objective functions and constraints.