Time-Dependent Path Scheduling (eBook)

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