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