信阅平台

内容介绍

本书专门讨论了作业车间调度问题，提出了改进的转换瓶颈算法、一个混合式邻域搜索算法、扩展HLS的算法、基础的拟物拟人算法、带禁忌规则的拟物拟人算法等一系列求解该问题的高效算法。 本书适合计算机专业本科高年级学生、研究生阅读，可供计算性与算法复杂性的研究人员阅读。

展开

精彩书摘

（1）不能保证算法一定得到最优解； （2）性能不稳定。启发式算法对同一个问题的不同实例的计算会产生不同的效果。有些实例所得的解的优度很高，而另一些则相反。在工程应用中，启发式算法的这种不稳定性使得计算结果不可信； （3）启发式算法的优劣依赖于具体问题以及设计者的经验、技术等，这一点很难总结成规律，同时使不同算法之间难于比较。 虽说启发式方法有诸多优点，但是它本身固有的一个很严重的缺陷--无法保证得到最优解，使得对启发式算法的评价显得尤为重要。一个好的启发式算法可以使其解尽可能地接近最优解，同时保持很好的稳定性。评价启发式算法的性能有很多不同的方法，主要是对算法的复杂性和它的计算效能进行分析。下面就简要地介绍几种常用的方法。 1.最坏情形分析 最坏情形分析考虑计算复杂性和所得解的效果两个方面。最坏情形计算复杂性分析关注算法基本运算总次数同实例的计算机二进制输入长度之间的关系，从最坏实例--规模相同基本计算步数最多的实例的角度来研究、分析算法的计算时间复杂性。 2.概率分析 由于最坏情形分析是以最坏的实例来评价一个算法或者它所得到的解，这样难免因为一个实例导致对某个算法或它所求得解的优劣的评价完全颠倒。人们认识到应该从总体上而非极端的实例上来评价算法，概率分析方法正是着眼于此。这个方法是从理论上考虑的，针对一个算法，我们可以从它的计算时间复杂性和计算所得解的效果两个方面进行概率分析。无论作哪一个方面的分析，都假设实例的数据服从某一种概率分布。在这些数据的一个已知概率分布的假设条件下，研究算法或其解的某种平均效果。 概率方法在评价算法方面的一个成功、典型的应用是对线性规划单纯形法的评价。概率发现方法是一种理论分析方法，它需要对问题本身有很深入的理解，并且掌握概率模型的建立和概率理论。 最坏情形分析和概率分析方法有一个共同的特点：用理论的方法分析算法所得到的解同最优解之间的误差界，要求分析者具有坚实的数学基础，而且分析过程很繁复。 3.大规模计算分析 前两种方法都是理论分析方法，要求有多的数学工具和繁复的推演，而且分析过程很复杂。 ……

展开

前言 第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 本章小结 参考文献

展开