第1章 调度问题与计算复杂性 1
1.1调度问题及其描述 1
1.1.1调度问题 1
1.1.2工件加工数据和特性的描述 2
1.1.3机器加工环境的描述 3
1.1.4加工性能指标的描述 4
1.1.5性能指标的正规性、等价性和活动调度 6
1.1.6调度问题的表示 7
1.1.7Job Shop和Flow Shop调度问题 9
1.2调度算法分类与邻域搜索算法 10
1.2.1调度算法分类 10
1.2.2邻域搜索算法 12
1.3计算复杂性与NP完全问题 18
1.3.1计算复杂性基本概念 18
1.3.2P,NP,NP-C,NP-hard 19
第2章 遗传算法理论与实现技术 22
2.1遗传算法的基本流程 22
2.2模式定理和隐含并行性 24
2.3遗传算法的马尔可夫链描述及其收敛性 26
2.3.1预备知识 26
2.3.2标准遗传算法的马尔可夫链描述 27
2.3.3标准遗传算法的收敛性 28
2.3.4标准遗传算法的收敛速度估计 29
2.4一般可测状态空间上遗传算法的收敛性 31
2.4.1问题描述 31
2.4.2算法及其马尔可夫链描述 31
2.4.3收敛性分析和收敛速度估计 32
2.4.4有限离散状态空间上GA的收敛性和收敛速度 34
2.5遗传算法参数与操作的设计 36
2.5.1编码 36
2.5.2适配值函数 37
2.5.3算法参数 37
2.5.4遗传操作 39
2.5.5算法终止条件 42
2.6遗传算法的改进 42
2.7免疫遗传算法 45
2.7.1引言 45
2.7.2免疫遗传算法及其收敛性 46
2.7.3免疫算子的机理与构造 48
2.7.4 TSP的免疫遗传算法 51
2.8并行遗传算法 52
2.8.1同步主仆式 52
2.8.2异步并发式 53
2.8.3网络式 53
2.8.4 GAMAS模型 54
第3章 Job Shop调度及其遗传算法 56
3.1引言 56
3.2典型Job Shop调度问题 59
3.3 Job Shop调度的遗传算法编码设计 68
3.3.1基于操作的编码 69
3.3.2基于工件的编码 70
3.3.3基于先后表的编码 71
3.3.4基于工件对关系的编码 71
3.3.5基于优先规则的编码 73
3.3.6基于析取图的编码 74
3.3.7基于完成时间的编码 75
3.3.8基于机器的编码 75
3.3.9随机键编码 76
3.4 Job Shop调度的遗传算法操作和框架设计 76
3.4.1 JSP的GA交叉与变异操作设计 77
3.4.2 JSP的GA框架设计 80
3.5 Job Shop调度的混合遗传算法 81
3.5.1编码与解码 81
3.5.2混合遗传算法 83
3.5.3仿真结果与比较 85
3.6一类模糊Job Shop调度的遗传算法 90
3.6.1问题描述和模糊操作 90
3.6.2遗传算法设计 92
3.6.3仿真结果 94
3.7 Job Shop调度的遗传算法简要综述 96
3.7.1 JSP的GA编码研究 96
3.7.2 JSP和GA的特征分析 96
3.7.3 Benchmark问题和算法改进与比较研究 97
3.7.4混合遗传算法的研究 98
3.7.5 JSP的推广和动态调度 99
3.7.6调度器开发和实际应用 100
3.7.7展望 100
第4章 Flow Shop调度及其遗传算法 102
4.1引言 102
4.1.1问题描述 102
4.1.2启发式方法 103
4.2典型Flow Shop调度问题 105
4.3置换Flow Shop调度的遗传算法 114
4.3.1初始化对SGA的影响 115
4.3.2交叉操作对SGA的影响 116
4.3.3变异操作对SGA的影响 117
4.3.4改进遗传算法 118
4.3.5数值仿真与分析 120
4.4多目标Flow Shop调度的遗传算法 122
4.4.1引言 122
4.4.2多目标遗传算法 124
4.4.3多目标Flow Shop调度的优化 126
4.5一类批量可变Flow Shop调度的遗传算法 129
4.5.1问题描述 129
4.5.2改进遗传算法 130
4.5.3仿真结果和分析 131
4.6模糊F1ow Shop调度及其遗传算法 132
4.6.1模糊交货期下Flow Shop调度的遗传算法 132
4.6.2模糊交货期下的其他指标 136
4.6.3模糊加工时间下Flow Shop调度的遗传算法 137
4.7混合Flow Shop调度的遗传算法 138
4.7.1问题描述 138
4.7.2基于矩阵编码的遗传算法设计 140
4.7.3基于置换编码的遗传算法设计 141
4.7.4基于复合码的遗传算法设计 144
第5章 并行机调度及其遗传算法 146
5.1最小化最大完成时间的遗传算法 146
5.1.1问题描述 146
5.1.2遗传算法设计 146
5.1.3计算实例 147
5.2最小化最大加权推迟时间的遗传算法 148
5.2.1问题描述 148
5.2.2遗传算法设计 148
5.2.3计算实例 150
5.3最小化公共交货期下E/T指标的遗传算法 151
5.3.1问题描述 151
5.3.2遗传算法设计 152
5.3.3计算实例 153
5.4一类带工艺约束的并行机调度的遗传算法 154
5.4.1问题描述 154
5.4.2遗传算法设计 155
5.4.3计算实例 156
附录 158
附录1典型Job Shop调度问题 158
附录2典型Flow Shop调度问题 193
参考文献 219