流水调度问题的启发式求解

论文摘要

以总完工时间为目标的Flow shop调度问题是一个重要的制造加工系统，广泛应用于工业环境中。流水调度是很多实际流水线生产调度问题的简化模型，也是一类典型的NP完全问题，已被证明在多项式时间内得不到最优值。该问题是生产管理中的核心问题，好的求解方法可以促进企业提高生产率。因此，该研究无论从理论还是实际都有重要意义。近年来，对于流水调度问题的求解主要有启发式算法和元启发式算法，但各有其不足之处：元启发式方法的运行时间长，可获得较好的解，但其解不稳定；启发式方法可在较短的时间内得到鲁棒性较强的解，但是极少获得较优的解。为了更好地解决流水调度问题，提出两个相应的启发式算法，从优解性和实时性两个方面与现有的算法进行比较，大量试验结果表明该方法能有效求解所考虑的流水调度问题。针对以总完工时间为优化目标的流水作业调度问题，提出基于局部插入和全局插入方法的双插入启发式算法RP和RT。RP和RT算法与目前求解流水调度问题最好的启发算法有RZ、WY、FL在1700个实例上进行比较。试验表明，RP和RT算法具有最好的性能，在最好调度的获取能力、所得调度的平均质量及所得调度的稳定性方面，RP和RT算法均是最优的。RP和RT能够更有效地解决以总完工时间最小为目标的Flow Shop调度问题。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.2 国内外研究现状与分析
• 1.3 研究方法
• 1.4 评价启发式算法的性能指标
• 1.5 本文结构
• 第2章 流水作业调度问题
• 2.1 流水作业调度问题的概述
• 2.2 流水作业调度问题的目标
• 2.3 流水作业调度问题的类型
• 2.4 流水作业调度问题的计算复杂性
• 2.5 同顺序流水作业问题的一般描述
• 2.6 本章小结
• 第3章 流水作业调度的求解方法
• 3.1 调度问题求解
• 3.2 流水调度的元启发式方法
• 3.2.1 遗传算法
• 3.2.2 模拟退火法
• 3.2.3 禁忌搜索法
• 3.2.4 神经网络算法
• 3.2.5 蚁群算法
• 3.3 流水调度的启发式方法
• 3.3.1 Johnson算法
• 3.3.2 Palmer发式算法
• 3.3.3 Gupta发式算法
• 3.3.4 CDS启发式算法
• 3.3.5 关键工件法
• 3.3.6 NEH 启发式算法
• 3.3.7 Rajendran 算法
• 3.3.8 Insertion Method 算法
• 3.3.9 RZ算法
• 3.3.10 WY算法
• 3.3.11 FL算法
• 3.4 流水调度启发式方法总结
• 3.5 本章小结
• 第4章 复合禁忌搜索算法求解流水调度问题
• 4.1 混合算法的结构
• 4.1.1 串行结构
• 4.1.2 镶嵌结构
• 4.1.3 并行结构
• 4.2 问题描述
• 4.3 禁忌搜索算法
• 4.4 初始解生成算法选择
• 4.5 RP启发式算法
• 4.5.1 初始解生成算法
• 4.5.2 禁忌搜索算法的参数设置
• 4.5.3 算法描述
• 4.5.4 实例说明
• 4.5.5 模拟实验
• 4.6 RP算法时间复杂性分析
• 4.7 本章小结
• 第5章 复合启发式算法RT
• 5.1 RT启发式算法
• 5.1.1 初始解生成算法
• 5.1.2 禁忌搜索算法的参数设置
• 5.1.3 RT 算法描述
• 5.1.4 实例说明
• 5.1.5 模拟实验
• 5.2 时间复杂性分析
• 5.3 启发式算法RP与RT比较
• 5.4 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢