Contents 
Preface
Chapter 1 A hybrid tabu search algorithm for FJSP 1 
1.1 Introduction 1 
1.2 Problem description and formulation 4 
1.3 Related algorithm and theory 6 
1.3.1 Tabu search algorithm 6 
1.3.2 Critical path theory 7 
1.4 The hybrid algorithm framework 8 
1.4.1 Coding 8 
1.4.2 Initialization of solutions 9 
1.4.3 Public critical blocks 11 
1.4.4 Nei□□□orhood for machine assignment component 12 
1.4.5 Nei□□□orhood for operation scheduling component 14 
1.4.6 The hybrid algorithm framework 16 
1.5 Experimental results 17 
1.5.1 Experimental setup 18 
1.5.2 Test instances of the Kacem instances 19 
1.5.3 Test instances of the BRdata 21 
1.6 Conclusion 24 
References 25 
Chapter 2 A hybrid tabu search for multi-objective FJSP 28 
2.1 Introduction 28 
2.2 Problem formulation 30 
2.3 Framework of the hybrid algorithm 32 
2.4 Assignment algorithm: tabu search algorithm 35 
2.4.1 Tabu search algorithm 35 
2.4.2 Encoding 35 
2.4.3 Parameter settings 36 
2.4.4 Local search 38
2.5 Scheduling algorithm: variable nei□□□orhood search 39 
2.5.1 Left-shift based decoding 39 
2.5.2 Public critical block 41 
2.5.3 Variable nei□□□orhood search 42 
2.6 Experimental results 44 
2.6.1 Results of Kacem instances 44 
2.6.2 Results of BRdata 51 
2.7 Conclusion 57 
References 57 
Chapter 3 A hybrid VNS algorithm for multi-objective FJSP 60 
3.1 Introduction 60 
3.2 Problem formulation 62 
3.3 Framework of the hybrid algorithm 64 
3.4 Machine assignment algorithm: the genetic algorithm 65 
3.4.1 Genetic algorithm 65 
3.4.2 Encoding 66 
3.4.3 Initialization of machine assignment component 67 
3.4.4 Crossover operation 67 
3.4.5 Mutation operation 68 
3.5 Operation sequencing algorithm: variable nei□□□orhood search algorithm 68 
3.5.1 Initialization of the operation sequencing component 68 
3.5.2 Public critical block theory 69 
3.5.3 Effective nei□□□orhood structure 72 
3.6 Experimental results 73 
3.6.1 Setting parameters 74 
3.6.2 Results of the Kacem instances 74 
3.7 Conclusion 80 
References 81 
Chapter 4 Pareto-based ABC for multi-objective FJSP 83 
4.1 Introduction 83 
4.2 Problem formulation 84 
4.3 Artificial bee colony algorithm 86 
4.3.1 The basic concept of ABC algorithm 86
4.3.2 Initialization of the parameters 87 
4.3.3 Initialization of the population 87 
4.3.4 Local search operator 87 
4.3.5 Global search operator 87 
4.3.6 Random search operator 88 
4.4 The hybrid algorithm P-DABC 88 
4.4.1 Food source representation 88 
4.4.2 Local search approaches 88 
4.4.3 Employed bee phase 89 
4.4.4 Crossover operator 89 
4.4.5 Onlooker bee phase 90 
4.4.6 Scout bee phase 90 
4.4.7 Multi-objective optimizer 91 
4.5 Experimental results 94 
4.5.1 Setting parameters 94 
4.5.2 Results comparisons 94 
4.6 Conclusion 99 
References 100 
Chapter 5 An effective shu2ed frog-leaping algorithm for multi-objective FJSP 103 
5.1 Introduction 103 
5.2 Literature review 105 
5.3 Problem formulation 106 
5.4 Shuffled flog-leaping algorithm 106 
5.5 The hybrid algorithm HSFLA 108 
5.5.1 Solution representation 109 
5.5.2 Population initialization 110 
5.5.3 Multi-objective SFLA 112 
5.5.4 The framework of HSFLA 118 
5.6 Experimental results 119 
5.6.1 Setting parameters 119 
5.6.2 Results comparisons 120
5.6.3 The three Kacem instances 120 
5.6.4 The three Kacem instances with release dates 123 
5.6.5 The BRdata instances 124 
5.7 Conclusion 133 
References 133 
Chapter 6 A hybrid Pareto-based local search algorithm for multi-objective FJSP 137 
6.1 Introduction 137 
6.2 Problem description 139 
6.3 Related theory 140 
6.3.1 Variable nei□□□ourhood search 140 
6.3.2 Critical path theory 140 
6.4 The hybrid algorithm 142 
6.4.1 Coding 142 
6.4.2 Population initialization 142 
6.4.3 Nei□□□oring approaches 145 
6.4.4 VNS based self-adaptive strategy 147 
6.4.5 Pareto archive set 149 
6.4.6 The framework of PLS 152 
6.5 Experimental results 153 
6.5.1 Setting parameters 153 
6.5.2 Results comparisons 153 
6.6 Conclusion 159 
References 160