Efficient algorithms for production scheduling
Seiten
2020
Fraunhofer Verlag
978-3-8396-1609-3 (ISBN)
Fraunhofer Verlag
978-3-8396-1609-3 (ISBN)
- Titel ist leider vergriffen;
keine Neuauflage - Artikel merken
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.
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.
| Erscheinungsdatum | 21.05.2020 |
|---|---|
| Zusatzinfo | num., mostly col. illus. and tab. |
| Verlagsort | Stuttgart |
| Sprache | englisch |
| Maße | 148 x 210 mm |
| Themenwelt | Mathematik / Informatik ► Informatik |
| Mathematik / Informatik ► Mathematik ► Angewandte Mathematik | |
| Schlagworte | Algorithms & Data Structures • Angewandte Mathematiker • B • Berechnungsingenieur • Berechnungsingenieure • Buffer Allocation • combinatorics & graph theory • discrete mathematic • Fraunhofer ITWM • Inventory constraints • residence time minimization • robust optimization • Scheduling problems |
| ISBN-10 | 3-8396-1609-3 / 3839616093 |
| ISBN-13 | 978-3-8396-1609-3 / 9783839616093 |
| Zustand | Neuware |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
für Ingenieure und Naturwissenschaftler
Buch | Softcover (2024)
Springer Vieweg (Verlag)
CHF 48,95
Buch | Softcover (2025)
Springer Vieweg (Verlag)
CHF 62,95
Buch | Softcover (2025)
Springer Fachmedien Wiesbaden (Verlag)
CHF 69,95
