论文部分内容阅读
流水作业调度问题是一类具有广泛应用的组合优化问题。总完工时间、总误工时间、最大完工时间和总加权误工时间是几个重要的性能指标。论文对最小化总完工时间的流水作业调度问题(F|prmu|∑Cj)、最小化总误工时间的流水作业调度问题(F|prmu|∑Tj)、准备时间顺序依赖的最小化最大完工时间流水作业调度问题(F|Sijg|Cmax)和准备时间顺序依赖的最小化总加权误工时间流水作业调度问题(F|Sijg|∑WjTj)进行研究。
针对F|prmu|∑Cj提出混合遗传算法(HGA)、混合分布估计算法(PHEDA)、量子激发的迭代贪婪算法(QIG)和基于相似度的蚁群算法(SACO)等4个高效智能算法。HGA使用加权简单基因挖掘结构采集种群信息并构造人工染色体,设计一个新的杂交算子,使人工染色体直接参与杂交过程,不但可挖掘父母双亲的局部优良基因,而且可挖掘隐含于种群的全局优良基因,并将优良基因直接遗传至子代。仿真实验表明,CJC帮助HGA获得较高的性能。PHEDA将基因挖掘方法和分布估计策略有机结合,提出高效子代个体的构造算子,将优良基因遗传至子代,并有效地保持种群的多样性。实验结果显示,PHEDA优于目前求解该问题的其他算法,且获得前90个Taillard标准实例中72个实例的目前最优解,其中42个为首次发现。基于量子比特与任务结合的混合编码模式,QIG使用一个新的旋转门动态调整量子比特,实现扰动强度的自适应调整。仿真实验说明,QIG优于目前求解该问题的其他算法。SACO并行构造多个候选解,基于定义的相似度,从候选解中选择最有可能被局部搜索方法改进的解进行局部搜索。实验结果表明,基于相似度的选择方法帮助SACO获得较高性能。
针对F|prmu|∑Tj提出基于相似度的迭代局部搜索算法(SILS)。为避免早熟,SILS使用一个混合邻域结构的扰动算子对当前最优解扰动多次,构造出多个候选解;使用SACO中基于相似度的选择方法,从候选解中挑选一个最有可能被局部搜索方法改进的解进行局部搜索。实验结果表明,混合邻域结构的扰动算子使SILS有效避免早熟,SILS优于求解问题的目前最好算法。
针对F|Sijg|Cmax和F|Sijg|∑WjTj提出自适应遗传算法(AGA),给每个任务增加一个继承因子,表示该任务在杂交算子中直接遗传至子代相同位置的概率;动态调整继承因子以挖掘优良基因和劣质基因;提出新的杂交算子,以较大概率遗传优良基因,同时以较大概率破坏劣质基因;构造3个不同邻域结构的局部搜索方法L1-L3,并提出3个混合算法AGA1-AGA3。仿真实验表明,这些混合算法都优于求解该问题的目前最好算法,准备时间对局部搜索方法的性能影响很大,混合邻域结构的局部搜索方法适用于具有较小准备时间的问题,而交换邻域结构的局部搜索方法适合于具有较大准备时间的问题。