求解作业车间调度问题的高效算法研究
2010-2
中国科学技术大学出版社
尹爱华
130
无
从有资源分配的时代开始，人类就开始接触到调度问题。从人们在战争中对军队的调度到从事农耕、娱乐、运输、制作中对人力和物资的分配与调度，人类很早就感受到了在有限资源条件下完成指定的任务需要调度。然而，一个很有意思的现象是，虽然调度问题在军事、生活等方面的活动中普遍存在，但是严格地研究这个问题却是在数千年之后。提出调度问题的数学模型的出现是很晚的，1954年，S.M.Johnson提出了求解流水车间两台机器下调度问题最优解的法则，这是第一个求解调度问题的数学模型，Ramser于1959年首次提出交通调度问题。这既不同于欧拉研究哥尼斯堡七桥问题从而导致图论的创立，又不同于17世纪人们从研究投骰子赌博现象而提出的概率论。笔者很早就注意到了这一现象，并做了一些调查研究，但是到目前为止都没有找到解释这个现象的文献。基于人们目前对各种调度问题的研究成果，笔者猜想人们数千年以来都是采用增加资源和人为强制介入的办法（某种强权干预资源分配）来解决现实中的调度问题，从而误导人们认为“该问题不是数学问题”。当然，也可能因为这个问题过于复杂，不显得“有趣”。 1999年起，笔者开始攻读博士学位，师从国际知名的NP难问题研究专家黄文奇教授。我因此有机会更加深入地了解了调度问题，并选择了作业车间调度问题作为我博士论文的研究内容。众所周知，NP难问题是理论计算机科学领域的重要研究对象，作业车间调度问题不仅是NP难的，还被认为是最难的组合最优化问题之一。人们已经知道，为解决工业生产、物流、经济管理和网络通信等诸多方面的问题，可以借助于求解作业车间调度问题的结果。所以，高效、快速地求解作业车间调度问题，既有重要的理论意义，又有重大的应用价值。 人们为了求解作业车间调度问题提出了许多方法。在黄文奇教授的悉心指导下，我认真总结了前人的研究结论，提出了一套求解该问题的方法并完成我的博士论文。特别要指出的是，用我的方法找到了一个大规模实例（50个作业，20台机器，1000个工序）到目前为止的最好解。博士毕业后，我进一步钻研求解这个问题的高效率算法的设计，提出了拟物拟人方法。拟物拟人方法同原有的方法都不同，虽然这方面的研究刚刚起步，但是可以预见到它有很好的发展前景，本书将这个研究的相关结果收录进来了。 ……
本书专门讨论了作业车间调度问题，提出了改进的转换瓶颈算法、一个混合式邻域搜索算法、扩展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 本章 小结参考文献
（1）不能保证算法一定得到最优解； （2）性能不稳定。启发式算法对同一个问题的不同实例的计算会产生不同的效果。有些实例所得的解的优度很高，而另一些则相反。在工程应用中，启发式算法的这种不稳定性使得计算结果不可信； （3）启发式算法的优劣依赖于具体问题以及设计者的经验、技术等，这一点很难总结成规律，同时使不同算法之间难于比较。 虽说启发式方法有诸多优点，但是它本身固有的一个很严重的缺陷--无法保证得到最优解，使得对启发式算法的评价显得尤为重要。一个好的启发式算法可以使其解尽可能地接近最优解，同时保持很好的稳定性。评价启发式算法的性能有很多不同的方法，主要是对算法的复杂性和它的计算效能进行分析。下面就简要地介绍几种常用的方法。 1.最坏情形分析 最坏情形分析考虑计算复杂性和所得解的效果两个方面。最坏情形计算复杂性分析关注算法基本运算总次数同实例的计算机二进制输入长度之间的关系，从最坏实例--规模相同基本计算步数最多的实例的角度来研究、分析算法的计算时间复杂性。 2.概率分析 由于最坏情形分析是以最坏的实例来评价一个算法或者它所得到的解，这样难免因为一个实例导致对某个算法或它所求得解的优劣的评价完全颠倒。人们认识到应该从总体上而非极端的实例上来评价算法，概率分析方法正是着眼于此。这个方法是从理论上考虑的，针对一个算法，我们可以从它的计算时间复杂性和计算所得解的效果两个方面进行概率分析。无论作哪一个方面的分析，都假设实例的数据服从某一种概率分布。在这些数据的一个已知概率分布的假设条件下，研究算法或其解的某种平均效果。 概率方法在评价算法方面的一个成功、典型的应用是对线性规划单纯形法的评价。概率发现方法是一种理论分析方法，它需要对问题本身有很深入的理解，并且掌握概率模型的建立和概率理论。 最坏情形分析和概率分析方法有一个共同的特点：用理论的方法分析算法所得到的解同最优解之间的误差界，要求分析者具有坚实的数学基础，而且分析过程很繁复。 3.大规模计算分析 前两种方法都是理论分析方法，要求有多的数学工具和繁复的推演，而且分析过程很复杂。 ……
无
对JobShop调度进行了深入研究，值得学习
**了，就一个博士论文的东西，老后悔了。