求解作业车间调度问题的高效算法研究
出版时间：2010年版
内容简介
本书专门讨论了作业车间调度问题，提出了改进的转换瓶颈算法、一个混合式邻域搜索算法、扩展HLS的算法、基础的拟物拟人算法、带禁忌规则的拟物拟人算法等一系列求解该问题的高效算法。本书适合计算机专业本科高年级学生、研究生阅读，可供计算性与算法复杂性的研究人员阅读。
目录
前言
第1章 绪论
1.1 组合最优化问题
1.2 实际难解性和NP完全问题
1.3 启发式方法
1.3.1 基本策略
1.3.2 性能评价
1.3.3 算法类型
1.3.4 拟物拟人算法
1.4 作业车间调度问题及其算法概论
1.5 本书研究内容及工作安排
1.6 本章 小结
第2章 改进的转换瓶颈算法
2.1 问题的描述及其形式化
2.1.1 问题的描述
2.1.2 问题的形式化
2.2 转换瓶颈算法
2.2.1 问题的一种直观表示和一个定理
2.2.2 转换瓶颈算法
2.3 定理2.2的证明
2.3.1 一个关于单机调度的引理
2.3.2 定理2.2的证明
2.4 改进的转换瓶颈算法ISB
2.4.1 带扰动的Schrage算法
2.4.2 关于扰动系数
2.5 部分回溯算法
2.6 对典型实例的计算结果
2.7 本章 小结
第3章 一个混合式邻域搜索算法
3.1 Tabu搜索与作业车间调度问题
3.1.1 Tabu搜索
3.1.2 作业车间调度问题中的Tabu搜索
3.2 邻域搜索算法HLS
3.2.1 邻域结构
3.2.2 初始解和禁忌表
3.2.3 一个基于拟人策略的吸引准则
3.2.4 集中和分散策略
3.2.5 新的邻域搜索算法
3.3 对实例的计算结果
3.4 本章 小结
第4章 扩展HLS的算法
4.1 常用的邻域结构
4.2 新邻域结构的基础
4.2.1 两种新的移动
4.2.2 关于新移动的两个定理
4.3 新的混合算法TSISB
4.3.1 新邻域的定义
4.3.2 新的禁忌表
4.4 含随机策略的邻域搜索算法SHLS
4.5 对实例的计算结果
4.6 关于最长路径长度的计算
4.7 本章 小结
第5章 各种启发式算法的比较
5.1 基于邻域搜索算法之比较
5.2 与典型启发式算法的比较和分析
5.3 本章 小结
第6章 基础的拟物拟人算法
6.1 作业车间调度问题的物理模型
6.1.1 作业车间调度问题的弹性物理模型
6.1.2 弹性力和位移量
6.2 拟物算法的基础
6.3 初始算法
6.4 拟物拟人算法
6.4.1 反向挤压策略
6.4.2 分组计算策略
6.4.3 随机策略
6.5 实验结果
6.6 本章 小结
第7章 带禁忌规则的拟物拟人算法
7.1 禁忌搜索算法概述
7.2 带禁忌规则的拟物拟人算法
7.2.1 初始解和邻域结构
7.2.2 禁忌表
7.2.3 搜索和跳坑策略
7.3 算法的实验结果
7.4 本章 小结
第8章 总结及展望
8.1 主要工作总结及创新
8.2 未来的研究方向
8.3 本章 小结
参考文献
