On the car sequencing problem [Elektronische Ressource] : analysis and solution methods / Uli Golle

Uli Kozok

Sujets

• Management

Informations

• Publié par: johannes_gutenberg-universitat_mainz
• Publié le: 01 janvier 2011
• Nombre de lectures: 14
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

On the Car Sequencing Problem:
Analysis and Solution Methods
Dissertation
zur Erlangung des Grades eines Doktors der
wirtschaftlichen Staatswissenschaften
(Dr. rer. pol.)
des Fachbereichs Rechts- und Wirtschaftswissenschaften
der Johannes Gutenberg-Universit¨at Mainz
vorgelegt von
Dipl.-Wirt.-Inf. Uli Golle
in Mainz
im Jahre 2011Tag der mu¨ndlichen Pru¨fung: 19.10.2011Fu¨r TamaraContents
List of Papers iv
List of Figures v
List of Tables vii
1 Introduction 1
1.1 Purpose of the thesis . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Structure of the thesis . . . . . . . . . . . . . . . . . . . . . . . 4
2 Analysis and design of sequencing rules for car sequencing 6
UliGolle,NilsBoysen,FranzRothlauf
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Assumptions and classification quality . . . . . . . . . . . . . . 8
2.3 Classification quality of the Bolat and Yano approach . . . . . . 9
2.4 MSR - A novel rule generation approach . . . . . . . . . . . . . 13
2.5 Multiple processing times . . . . . . . . . . . . . . . . . . . . . 16
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Car sequencing versus mixed-model sequencing:
A computational study 22
UliGolle,FranzRothlauf,NilsBoysen
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Mixed-model sequencing . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Car sequencing . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3.1 Sequencing rule generation approaches . . . . . . . . . . 29
3.3.2 Objective functions and model formulation . . . . . . . . 30
3.3.3 Weighting of violations . . . . . . . . . . . . . . . . . . . 36
3.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4.1 Instance generation . . . . . . . . . . . . . . . . . . . . . 37
3.4.2 Linear relationship between CS and MMS objectives . . 39
3.4.3 Solution quality of CS compared to MMS. . . . . . . . . 40
3.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
iContents
4 The car resequencing problem with pull-off tables 53
NilsBoysen,UliGolle,FranzRothlauf
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3 Transforming CRSP into a graph search problem . . . . . . . . 58
4.3.1 Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.3.2 Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.4 Search algorithms for the CRSP . . . . . . . . . . . . . . . . . . 62
4.4.1 Breadth-first search . . . . . . . . . . . . . . . . . . . . . 62
4.4.2 Beam search . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.4.3 Iterative beam search . . . . . . . . . . . . . . . . . . . . 67
4.4.4 A* search . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.5 Computational study . . . . . . . . . . . . . . . . . . . . . . . . 68
4.5.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . 68
4.5.2 Algorithmic performance . . . . . . . . . . . . . . . . . . 68
4.5.3 Resequencing flexibility . . . . . . . . . . . . . . . . . . . 72
4.6 Comparison with a real-world scheduling rule . . . . . . . . . . 74
4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5 Iterative beam search for car sequencing 81
UliGolle,FranzRothlauf,NilsBoysen
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.2 Model formulation and literature . . . . . . . . . . . . . . . . . 82
5.3 An iterative beam search approach . . . . . . . . . . . . . . . . 85
5.3.1 Search procedure . . . . . . . . . . . . . . . . . . . . . . 85
5.3.2 Graph representation of CS . . . . . . . . . . . . . . . . 86
5.3.3 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . . 87
5.3.4 Node selection . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4 Computational study . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . 92
5.4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.4.3 Optimality proof . . . . . . . . . . . . . . . . . . . . . . 94
5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6 Fitnesslandscapeanalysisanddesignofmetaheuristicsforcar
sequencing 100
Uli Golle
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.2 The car sequencing problem . . . . . . . . . . . . . . . . . . . . 102
6.3 Fitness landscape analysis of car sequencing . . . . . . . . . . . 105
6.3.1 Representation and neighborhood operators . . . . . . . 105
6.3.2 Autocorrelation . . . . . . . . . . . . . . . . . . . . . . . 106
iiContents
6.3.3 Fitness-distance-correlation . . . . . . . . . . . . . . . . 108
6.4 Metaheuristics for car sequencing . . . . . . . . . . . . . . . . . 111
6.4.1 Variable neighborhood search . . . . . . . . . . . . . . . 112
6.4.2 Memetic algorithm . . . . . . . . . . . . . . . . . . . . . 114
6.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.5.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . 117
6.5.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7 Summary and conclusions 126
7.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7.2 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Bibliography 131
iiiList of Papers
1 2 1• Uli Golle , Prof. Dr. Nils Boysen , Prof. Dr. Franz Rothlauf (2010).
Analysis and design of sequencing rules for car sequencing. European
Journal of Operational Research, 206 (3), pp. 579-585
1 1 2• Uli Golle , Prof. Dr. Franz Rothlauf , Prof. Dr. Nils Boysen (2011).
Car sequencing versus mixed-model sequencing: A computational study.
2 1 1• Prof. Dr. Nils Boysen , Uli Golle , Prof. Dr. Franz Rothlauf (2011).
The car resequencing problem with pull-off tables. BuR - Business Re-
search, 4 (2), pp. 1-17
1 1 2• Uli Golle , Prof. Dr. Franz Rothlauf , Prof. Dr. Nils Boysen (2011).
Iterative beam search for car sequencing. submitted to Annals of Opera-
tions Research
1• Uli Golle (2011). Fitness landscape analysis and design of metaheuris-
tics for car sequencing. submitted to IEEE Transactions on Evolutionary
Computation
1Johannes Gutenberg-Universita¨t Mainz, Lehrstuhl fu¨r Wirtschaftsinformatik und BWL,
Jakob-Welder-Weg 9, D-55128 Mainz, Germany
2Friedrich-Schiller-Universit¨at Jena, Lehrstuhl fu¨r Operations Management,
Carl-Zeiß-Straße 3, D-07743 Jena, Germany
ivList of Figures
2.1 Counterexample for CS-feasible← MMS-feasible . . . . . . . . . 11
2.2 Number of misclassified sequences where CS-feasible8MMS-
feasible (in %) . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Example for the MSR approach with sequences that assemble
three option models (+) and one basic model (-) . . . . . . . . 14
2.4 Average number of sequencing rules against sequence length T
for MSR and MSRstrict, which removes redundant rules. . . . 16
2.5 Counterexample for CS-feasible8MMS-feasible . . . . . . . . . 18
2.6 Number of misclassified sequences (in percent) for T = 10 . . . . 19
3.1 Movement diagram for example sequence . . . . . . . . . . . . . 28
3.2 Evaluation of example sequence with SW objective function . . 31
3.3 Evaluation of example sequence with FB objective function . . . 32
3.4 Evaluation of example sequence with BY objective function. . . 33
3.5 Example sequences subject to 1:4 . . . . . . . . . . . . . . . . . 34
3.6 Example sequences subject to 1:3, 2:6, 3:10 and 4:13. . . . . . . 35
3.7 Example option weights λ . . . . . . . . . . . . . . . . . . . . . 37o
3.8 Resulting Pearson’s correlation coefficients averaged over set 1
and set 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.9 Solution qualityw against avg. timeτ of MMS compared to CS
+variants with weighting factor λ = p −c based on instanceso o
with T = 100,S = 30,M = 30. . . . . . . . . . . . . . . . . . . 46
3.10 Solution qualityw against avg. timeτ of MMS compared to CS
+variants with weighting factor λ = p −c based on instanceso o
with T = 100,S = 30,M = 30. . . . . . . . . . . . . . . . . . . 47
4.1 Example on the use of a pull-off table of size one. . . . . . . . . 55
4.2 Example graph for BFS with UB = 1 . . . . . . . . . . . . . . . 64
4.3 Example for dominance rule . . . . . . . . . . . . . . . . . . . . 66
4.4 Performance of BS and IBS against P and T . . . . . . . . . . . 71
4.5 Performance of BS against beam width BW . . . . . . . . . . . 71
4.6 Resequencing flexibility . . . . . . . . . . . . . . . . . . . . . . 72
5.1 Example graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2 Example result of construction algorithm . . . . . . . . . . . . . 89
5.3 Example result of construction algorithm with already fixed slots 91
vList of Figures
6.1 Scatter plots for instance 10-93 andN based on 1000 localre
optima. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.2 Outline of VNS algorithm . . . . . . . . .