Efficient algorithms for production scheduling

Beschreibung

Due to their high complexity, scheduling problems are hard to adapt to real-world problems. This thesis attempts to close the gap between the theory of scheduling and its applications. As a starting point, we consider the problems of buffer allocation and prefabrication with additional robustness and inventory constraints. Then, we propose models and derive provably tractable algorithms for the exact solving of both problems.
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.

Autor*in

Pascal Wortel

Themen in »Efficient algorithms for production scheduling«

Fraunhofer ITWM discrete mathematic combinatorics & graph theory algorithms & data structures robust optimization buffer allocation residence time minimization scheduling problems inventory constraints angewandte Mathematiker Berechnungsingenieur Angewandte Mathematiker Berechnungsingenieure

Stimmen zu »Efficient algorithms for production scheduling«

Details

Link teilen