求解工件加工调度问题的一种混合邻域搜索算法

论文摘要

工件加工调度问题是最困难的组合优化问题之一。工件加工调度是利用有限的机器资源满足加工任务的各种要求,确定工件在相关加工机器上的加工顺序和时间,以保证所选择的性能指标最优。邻域搜索是一种很重要的求解工件加工调度问题的启发式算法。论文重点研究了邻域搜索算法,介绍了邻域搜索在工件加工调度问题中的应用。通过面向具体问题的启发式策略,针对现有的邻域搜索算法的缺点,研究如何改进邻域搜索的有关技术,提出了基于邻域搜索的,结合单机调度和拟物拟人思想的快速的启发式算法。为了说清楚所提算法的思想,提出了一些定义和定理,并严格证明了定理。提出了一种新的启发式调度规则以生成初始解,作为邻域搜索和回溯算法的出发点。利用拟物拟人的思想,构造出新的邻域。分析了移动瓶颈过程的子算法Schrage算法的优缺点,提出了一种改进的单机调度算法。针对邻域搜索在计算的过程中经常会陷入局部极小值陷阱的缺点,以文中提出的新邻域结构为基础,结合单机调度策略得到一个基于混合式邻域结构的搜索算法HNLS。混合邻域结构与单一邻域结构相比,有助于计算跳出局部极小值的陷阱,走向前景更好的区域,搜索到更好的解。在HNLS算法中不仅把单机调度作为一种跳出局部极小值陷阱的策略,还结合拟人拟物思想,提出了“模拟调整”、“同工件工序调整”及“最小工件后移”多种策略以保证计算走向新的前景更好的区域。使用了不同规模和难度的68个国际标准算例做为HNLS算法的测试实验集,这些算例是近十年以来经常被国际文献提到的,其中包括OR-Library中所有的3个FT算例、5个ABZ算例、40个LA算例、10个ORB算例及TA1-TA10算例。试验结果表明,对于实验集中所有的18个10工件10机器算例,其中包括著名的难例FT10,HNLS算法全部算出了最优解。对于实验集中所有的40个LA算例,HNLS算法算出了其中37个算例的最优解。HNLS算法的优度优于一些经典算法,比如模拟退火、遗传算法、禁忌搜索、移动瓶颈过程。HNLS还和目前国际上的两种先进算法TSSB以及Balas的算法进行了比较。Balas提出的算法根据设置参数和使用方法的不同有GLS、SB-GLS1、SB-GLS2、SB-RGLS1和SB-RGLS2等版本,BV-best是Balas不同版本的算法对所求问题最好的解。对于HNLS和TSSB算法共同报告了计算结果的63个算例,HNLS对其中19个算例解的质量优于TSSB对它们解的质量,只有一个算例TSSB对它解的质量优于HNLS对它解的质量。对于HNLS和Balas的算法共同报告了计算结果的63个算例, HNLS对其中6个算例解的质量优于BV-best的质量,7个算例BV-best的质量优于HNLS对它们解的质量。对于所测试的算例,HNLS算法中的参数是统一不变的。实验结果表明,HNLS对这些算例解的优度好于Balas的任何一个确定参数的算法对它们解的优度。论文还提出了一种求解工件加工调度问题的回溯算法。测试了实验集中的22个算例,回溯算法找到了其中17个算例的最优解。算法也测试和分析了不同回溯参数及嵌套重数对算法效率的影响。算例测试说明回溯算法是一种十分快速但是优度稍逊的求解工件加工调度问题的近似算法。

论文目录

• 摘要
• ABSTRACT
• 1 引言
• 1.1 本文的来源及研究目的
• 1.2 选题的背景、依据及研究意义
• 1.3 本文的主要工作及结构安排
• 1.4 小结
• 2 工件加工调度问题
• 2.1 组合优化与启发式算法
• 2.2 工件加工调度问题的提法
• 2.3 研究现状与存在问题
• 2.4 一些本文算法相关的定义、定理和证明
• 2.5 小结
• 3 改进的单机调度算法
• 3.1 移动瓶颈过程
• 3.2 单机调度
• 3.3 求解单机调度问题的SCHRAGE 算法
• 3.4 改进的单机调度算法
• 3.5 本章小结
• 4 混和邻域结构搜索算法
• 4.1 局部搜索算法
• 4.2 邻域搜索算法的统一流程和设计
• 4.3 混和邻域结构搜索算法
• 4.4 算法的计算结果以及与其他算法的比较
• 4.5 本章小结
• 5 回溯算法
• 5.1 回溯算法
• 5.2 试验结果与分析比较
• 5.3 小结
• 6 全文总结及展望
• 6.1 主要工作及创新之处
• 6.2 未来的研究方向
• 致谢
• 参考文献
• 附录1 攻读博士学位期间发表的论文目录