柔性作业车间调度问题(FlexibleJobShopSchedulingProblem,FJSSP)是作业车间调度中的一种特例，因其增加了机床选择的柔性，使得FJSSSP相比作业车间调度更为复杂，属于强NP-难问题，近年来成为靠前外研究的热点问题。本书研究单目标、多目标、多约束FJSSP问题，首先建立其混合整数规划模型；其次，融合新型的离散智能优化算法，如人工蜂群优化算法、忌搜索算法、和声搜索、粒子群优化等，综合考虑FJSSP问题特征、目标特点和约束条件，利用启发式信息指导智能算法的搜索方向，融合面向具体问题的局部算法来强化集中能力，利用问题解之间的本质联系来提高个体的评价速度和算法的搜索效率，提出了解决多约束、多目标柔性作业车间调度问题的高性能混合优化算法。

   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 Neighborhood for machine assignment component 12

1.4.5 Neighborhood 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 neighborhood search 39

2.5.1 Left-shift based decoding 39

2.5.2 Public critical block 41

2.5.3 Variable neighborhood 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 neighborhood 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 neighborhood 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 Artifi 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 neighbourhood 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 Neighboring 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