Time-Dependent Path Scheduling (eBook)

Algorithmic Minimization of Walking Time at the Moving Assembly Line

Helmut A. Sedding (Autor)

eBook Download: PDF

2019 | 1st ed. 2020
XXIII, 169 Seiten
Springer Fachmedien Wiesbaden (Verlag)
978-3-658-28415-2 (ISBN)

Infos

Moving assembly lines are the stepping stone for mass production of automobiles. Here, every second counts, which necessitates planners to meticulously optimize them. A crucial factor is each worker's nonproductive walking time between the moving workpiece and line-side material containers for picking up required material. Minimizing the walking time is difficult because the workpiece moves steadily. Helmut A. Sedding devises algorithms to optimize the sequence of work operations, and the placement of material containers. Thereby, he introduces a novel category of time-dependent scheduling problems, and lays the basis for the algorithmic optimization of time-dependent paths at the moving assembly line.

About the Author:

Helmut A. Sedding passed his doctoral thesis with distinction at the Institute of Theoretical Computer Science at Ulm University, Germany. He researches on modeling, complexity analysis, and algorithm design for the solution of various optimization problems. His practical experience includes the development of automotive production planning software in use at major car manufacturers.

Helmut A. Sedding passed his doctoral thesis with distinction at the Institute of Theoretical Computer Science at Ulm University, Germany. He researches on modeling, complexity analysis, and algorithm design for the solution of various optimization problems. His practical experience includes the development of automotive production planning software, in use at major car manufacturers.

Inhalt

Acknowledgments 5
Abstract 6
Zusammenfassung 7
Contents 8
List of Definitions 12
List of Algorithms 13
List of Statements 14
List of Figures 16
List of Tables 17
Part I ntroduction 18
1 Introduction 19
1.1 Introduction 19
1.2 Organization 21
2 Modeling 23
2.1 Modeling 23
2.2 Related literature 24
2.3 Assumptions 28
2.3.1 Variable assumptions 28
2.3.2 Common assumptions 29
2.4 Walking strategies 32
Part II Operation sequencing 37
3 Operation sequencing 38
3.1 Introduction 38
3.2 Problem definition 39
3.3 Related literature 40
3.3.1 Assembly line balancing 40
3.3.2 Classic scheduling 42
3.3.3 Time-dependent scheduling 45
3.4 Polynomial cases 48
3.5 Lower bound 51
3.6 Dominance rule 54
3.7 Solution algorithms 55
3.7.1 Dynamic programming 55
3.7.2 Mixed integer program 56
3.7.3 Basic heuristics 57
3.7.4 Branch and bound algorithm 58
3.8 Numerical results 59
3.8.1 Instance generation 60
3.8.2 Exact algorithms 61
3.8.3 Heuristics 64
3.9 Conclusion 65
4 Operation sequencing with a single box position 66
4.1 Introduction 66
4.2 Related literature 68
4.3 Computational complexity 69
4.4 Dynamic programming algorithm 74
4.5 Fully polynomial time approximation scheme 77
4.6 Polynomial algorithm for a variable global start time 82
Part III Box placement 85
5 Box placement for one product variant 86
5.1 Introduction 86
5.2 Related literature 87
5.3 Problem definition 88
5.4 Polynomial cases 90
5.5 Computational complexity 95
5.6 Lower bound 100
5.7 Dominance rule 103
5.7.1 Exact dominance rule 103
5.7.2 Heuristic dominance rule 110
5.8 Solution algorithms 111
5.8.1 Mixed integer program 111
5.8.2 Basic heuristics 112
5.8.3 Branch and bound algorithm 113
5.8.4 Truncated branch and bound heuristic 114
5.9 Numerical results 114
5.9.1 Instance generation 115
5.9.2 Test setup 116
5.9.3 Exact algorithms 117
5.9.4 Heuristics 120
5.10 Conclusion 122
6 Box placement for multiple product variants 123
6.1 Introduction 123
6.2 Problem definition 125
6.3 Computational complexity 126
6.4 Mixed integer programs 127
6.4.1 Disjunctive sequencing 127
6.4.2 Space-indexing 128
6.5 Lower bound 130
6.5.1 Lagrangian relaxation of processing times 131
6.5.2 Subgradient search 132
6.5.3 Solving the Lagrangian relaxation 132
6.5.4 Determining box positions 134
6.5.5 Determining walk times 135
6.5.6 Greedily determining walk times 136
6.6 Solution algorithms 140
6.6.1 Basic heuristics 140
6.6.2 Branch and bound algorithm 141
6.6.3 Truncated branch and bound algorithm 142
6.7 Numerical results 142
6.7.1 Instance generation 143
6.7.2 Test setup 144
6.7.3 Exact algorithms 144
6.7.4 Heuristics 151
6.8 Conclusion 153
Part IV Conclusion 154
7 Conclusion 155
7.1 Conclusion 155
7.2 Future steps 156
8 Summary of major contributions 158
8.1 Sequencing assembly operations 158
8.2 Line side placement 159
Bibliography 161
Publications 177

Produkt-Details

• Erscheint lt. Verlag: 22.11.2019
• Zusatzinfo: XXIII, 169 p. 20 illus., 3 illus. in color.
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
• Themenwelt: Technik ► Bauwesen
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Planung / Organisation
• Schlagworte: Algorithm analysis and problem complexity • automobile production • Combinatorial Algorithms • complexity analysis • moving assembly line • nonmonotonic processing time • Production Planning • Time-Dependent Scheduling • time-dependent walking time • walking time minimization
• ISBN-10: 3-658-28415-3 / 3658284153
• ISBN-13: 978-3-658-28415-2 / 9783658284152