求解工件车间调度问题的一种高效近似算法

论文摘要

工件车间调度问题具有很高的理论价值和实际价值。人们的经验表明,它是最难的组合优化问题之一。当前学者们的研究重点是设计求解该问题的高效近似算法。当前文献中工件车间调度问题的问题描述很难理解。拟物方法可用来克服这个困难。拟物方法来源于物理世界。工件车间调度问题在用拟物方法进行描述后,变得很容易理解。双前沿贪心算法是一种新的基本算法。它依次指定所有工序的开工时刻。该算法指定双前沿工序在其最早合法开工时刻开工。联络图算法是文献中经常出现的一种基本算法。双前沿贪心算法生成调度的质量一致地高于等于联络图算法。双前沿贪心算法的计算时间比联络图算法略长。邻域搜索算法是以双前沿贪心算法为基础的。邻域结构的定义是基于关键路径的。精心设计的邻域结构是邻域搜索算法的一个关键所在。这种邻域搜索算法的创新之处在于当算法搜索到局部最优解时,并不是消极地停止搜索,而是在邻域中最好的三个邻点中均匀地随机选取一个邻点,接受这个邻点,积极地继续搜索。单机调度算法恰好改变一台机器上的工序的排列,保持其它机器上的工序的排列不变。单机调度算法可推广到双机调度算法。双机调度算法恰好改变两台机器上的工序的排列,保持其它机器上的工序的排列不变。邻域搜索算法容易陷入局部最优解。单机调度、双机调度和随机扰动这三种跳坑策略可用于跳出局部最优解,把搜索引向有希望的区域,从而提高搜索效率。以双前沿贪心算法为基础,结合了邻域搜索算法、单机调度算法和跳坑策略而形成的混合算法可用于求解工件车间调度问题。用这种混合算法计算了138个国际公认的标准问题实例。这些标准问题实例中规模最小的是工件数和机器数均为6的问题实例,规模最大的是工件数和机器数分别为100和20的问题实例。这种混合算法的计算结果可概括为以下三点。第一,所得混合算法生成解的质量比当前国际文献中最好的近似算法BV-best高。BV-best算法共计算了131个标准问题实例。其中27个实例混合算法生成解的质量比BV-best高,16个实例混合算法生成解的质量比BV-best低,88个实例混合算法生成解的质量和BV-best相等。第二,对一个名为TA15的标准问题实例,混合算法给出了一个makespan为1339的调度。这个调度优于当前文献中报导的最好的调度。在当前文献中,计算TA15所得到的最好的调度的makespan是1340。第三,这种混合算法是确定的,具有强烈的统一性,其中不包含任何随具体问题而变的待调参数。BV-best是不确定的。混合算法的研究是一个很有希望的领域。另外,置换流水车间调度问题和货郎担问题是和工件车间调度问题相关的两个问题。置换流水车间调度问题可用一种邻域搜索算法来求解。这种邻域搜索算法计算了一组共29个国际公认的标准问题实例。计算结果表明,邻域搜索算法的效率比当前国际文献中的一种改进的遗传算法高。改进的邻域搜索算法结合了构造型算法和邻域搜索算法。改进的邻域搜索算法的效率比邻域搜索算法高。货郎担问题可用一种邻域搜索算法来求解。这种邻域搜索算法基于一种新的贪心式基本算法。邻域搜索算法计算了一组共27个国际公认的标准问题实例。在短时间内,邻域搜索算法给出了其中24个实例的最优解,邻域搜索算法的效率高于当前国际文献中的一种著名的先进算法。

论文目录

• 摘要
• ABSTRACT
• 1 引言
• 1.1 本课题的来源及研究目的
• 1.2 选题的背景、依据及研究意义
• 1.3 问题描述
• 1.4 研究现状
• 1.5 本文的主要工作简介及结构安排
• 1.6 本章小结
• 2 基本理论和基本算法
• 2.1 工件前沿贪心算法
• 2.2 双前沿贪心算法
• 2.3 联络图算法
• 2.4 关键路径
• 2.5 本章小结
• 3 算法描述
• 3.1 邻域搜索
• 3.2 单机调度
• 3.3 双机调度
• 3.5 生成初始调度
• 3.6 算法描述
• 3.7 本章小结
• 4 实验测试
• 4.1 测试所用的问题实例
• 4.2 测试结果
• 4.3 本章小结
• 5 相关问题
• 5.1 置换流水车间调度问题
• 5.2 货郎担问题
• 5.3 本章小结
• 6 结论与展望
• 6.1 主要工作总结
• 6.2 主要研究成果及创新
• 6.3 研究展望
• 6.4 本章小结
• 致谢
• 参考文献
• 附录1 攻读博士学位期间发表的学术论文
• 附录2 TA15 的一个MAKESPAN 为1339 的调度