第1章 绪论 1
1.1 组合最优化问题 1
1.2 实际难解性和NP完全问题 2
1.3 启发式方法 4
1.3.1 基本策略 5
1.3.2 性能评价 7
1.3.3 算法类型 9
1.3.4 拟物拟人算法 13
1.4 作业车间调度问题及其算法概论 15
1.5 本书研究内容及工作安排 17
1.6 本章小结 19
第2章 改进的转换瓶颈算法 20
2.1 问题的描述及其形式化 20
2.1.1 问题的描述 20
2.1.2 问题的形式化 21
2.2 转换瓶颈算法 22
2.2.1 问题的一种直观表示和一个定理 22
2.2.2 转换瓶颈算法 26
2.3 定理2.2的证明 28
2.3.1 一个关于单机调度的引理 29
2.3.2 定理2.2的证明 32
2.4 改进的转换瓶颈算法ISB 35
2.4.1 带扰动的Schrage算法 36
2.4.2 关于扰动系数δ 38
2.5 部分回溯算法 38
2.6 对典型实例的计算结果 40
2.7 本章小结 43
第3章 一个混合式邻域搜索算法 44
3.1 Tabu搜索与作业车间调度问题 44
3.1.1 Tabu搜索 44
3.1.2 作业车间调度问题中的Tabu搜索 45
3.2 邻域搜索算法HLS 47
3.2.1 邻域结构 48
3.2.2 初始解和禁忌表 49
3.2.3 一个基于拟人策略的吸引准则 50
3.2.4 集中和分散策略 51
3.2.5 新的邻域搜索算法 53
3.3 对实例的计算结果 55
3.4 本章小结 57
第4章 扩展HLS的算法 58
4.1 常用的邻域结构 58
4.2 新邻域结构的基础 60
4.2.1 两种新的移动 60
4.2.2 关于新移动的两个定理 61
4.3 新的混合算法TSISB 63
4.3.1 新邻域的定义 64
4.3.2 新的禁忌表 64
4.4 含随机策略的邻域搜索算法SHLS 65
4.5 对实例的计算结果 67
4.6 关于最长路径长度的计算 72
4.7 本章小结 73
第5章 各种启发式算法的比较 74
5.1 基于邻域搜索算法之比较 74
5.2 与典型启发式算法的比较和分析 77
5.3 本章小结 84
第6章 基础的拟物拟人算法 85
6.1 作业车间调度问题的物理模型 85
6.1.1 作业车间调度问题的弹性物理模型 86
6.1.2 弹性力和位移量 89
6.2 拟物算法的基础 91
6.3 初始算法 95
6.4 拟物拟人算法 97
6.4.1 反向挤压策略 97
6.4.2 分组计算策略 99
6.4.3 随机策略 101
6.5 实验结果 102
6.6 本章小结 106
第7章 带禁忌规则的拟物拟人算法 107
7.1 禁忌搜索算法概述 107
7.2 带禁忌规则的拟物拟人算法 109
7.2.1 初始解和邻域结构 110
7.2.2 禁忌表 110
7.2.3 搜索和跳坑策略 111
7.3 算法的实验结果 113
7.4 本章小结 117
第8章 总结及展望 118
8.1 主要工作总结及创新 118
8.2 未来的研究方向 121
8.3 本章小结 122
参考文献 123