FLOW_SHOP调度问题研究(调度：原理、算法及系统).pdf

调度：原理、算法及系统 课程论文 FLOW SHOP 调度问题研究 1 Flow Shop 调度问题描述 Flow Shop 调度问题是很多实际流水线生产调度问题的简化模型，也是一个 典型的NP hard 问题，因此其研究具有重要的理论意义和工程价值，他也是目前 研究最广泛的一类典型调度问题。Flow Shop 调度问题研究m 台机器上n 个工件 的流水加工过程，每个工件在各机器上的加工顺序相同，同时约定每个工件在每 台机器上只加工一次，每台机器一次在某一时刻只能够加工一个工件，各工件在 各机器上的加工时间和准备时间已知，要求得到某调度方案使得某项指标最优。 进一步，若约定每台机器加工的各工件顺序相同，则称其为置换Flow Shop 问题。 2 Flow Shop 调度问题研究 尽管相对Job Shop 调度而言，Flow Shop 的工艺约束比较简单，但是它仍然是一 个非常复杂和困难的组合优化问题 其NP-hard 特性和强大的工程背景使其一直成为理论界 和工程领域研究的热点 问题 2.1 FLOW SHOP 调度问题的启发式算法[1] 针对以总完工时间最小为目标的Flow Shop调度问题，基于全局插入和任务 交换两种方法，提出一个启发式算法RP。RP算法的种子序列采用分组加权规则产 生，并在调度改进阶段依据种子序列应用全局插入和任务交换方法对当前调度进 行改进，以提高算法的有哪些信誉好的足球投注网站能力。模拟实验表明，在调度结果的平均质量、最好 调度的获取能力和算法稳定性方面，RP算法优于目前最好的启发式算法RZ、WY、 Ⅸ和FL。 针对总完工时间最小为目标的Flow Shop 调度问题，本文提出一个启发式算 法RP，RP 种子序列按分组加权规则产生，在调度序列构造阶段依据种子序列采 用RZ—I ／con(PWE)结构对当前序列进行改进，以提高算法有哪些信誉好的足球投注网站能力。实验结果 表明 RP 具有很好的性能，对于不同规模的大多数问题，RP 均能取得最好调度； 其所得调度的平均质量及算法稳定性也明显优于其他 4 个启发式算法。虽然 RP 所需CPU 时间比WY 和FL 要多，但多项式时间复杂性使其能够满足制造加工系统 中实时性的需求。在时间和质量要求较高的环境中，RP 算法能够更有效地解决 以总完工时间最短为目标的Flow Shop 调度问题。 2.2 Flow ．shop 调度问题的自适应模拟退火算法[2] 为求得一个强NP-难问题—Flow Shop调度问题的最优解或近优解，提出一种 自适应模拟退火算法，本算法采用一种基于区段特性的特殊邻域结构、简便的目 标函数计算方法和自适应退火策略，通过Flow Shop调度问题的基准测试问题的 实验，数值结果证实了该方法的有效性。 自适应模拟退火算法采用了简化的邻域结构、快速简便的目标函数计算方法 和自适应退火策略，加速了算法的运行速度，同时寻优性能明显提高，数值计算 结果证实了本算法的性能明显强于目前著名的Taillard的禁忌有哪些信誉好的足球投注网站算法和Osman 的模拟退火算法． 2.3 多目标Flow Shop 调度问题的改进TA 求解算法[3] 应用TA算法的关键在于如何合理设置一系列递减的门槛值T,传统TA算法中 邻域有哪些信誉好的足球投注网站结果对于门槛值设置没有反馈作用,这种开环控制方式,使得求解过程 盲目性较大,无法合适权衡有哪些信誉好的足球投注网站的分散性与收敛性,很难找到既能使算法收敛,又 2 能使其摆脱局部最优的T值序列.一般来讲T值对于问题的类型和规模是敏感的, 只有通过大量试验,经验地确定算法的参数.离散最优化问题,尤其多目标优化问 题,往往存在多个局部最优,为避免陷入局部最优,算法参数设定和有哪些信誉好的足球投注网站的控制方 式尤为关键. 速度和质量是算法设计中的两个矛盾指标,门槛值设定控制是TA综合上述二 者的关键性算法构件.加大T值下降速率无疑会提高算法速度,但很可能陷入局部 最优.考虑在有哪些信誉好的足球投注网站过程陷入局部最优时,适时提高门槛值,可以摆脱局部最优.因 此,改进TA算法设计的基本思想为:在有哪些信誉好的足球投注网站过程中,以较大的T值下降率实现算法 的快速性,同时允许对T值进行必要的小范围局部增加,保证寻求到合适的T值序 列,避免陷入局部最优;引入有哪些信誉好的足球投注网站进展对于算法构件的反馈机制,考虑T值设定控 制、邻域有哪些信誉好的足球投注网站强度 （次数）和算法终止条件相配合，由算法过程自动触发。 计算比较结果表明：对于上述各规模问题，ATA算法求解质量均