基于混合遗传算法的考虑运输时间的柔性作业车间调度问题研究

• 作 者: 余慧慧
• 出 处: 福州大学
• 发表日期: 2017年01期
• 关键词: 柔性作业车间调度 运输时间 多目标优化 遗传算法 模拟退火

制造业是国民经济的重要支柱。“工业4.0”及多元化需求的背景下,企业只有制定更加合理的调度方案,才能及时地响应市场。传统车间调度问题忽略了除加工时间以外的其他时间,但实际生产中工件在机器间的运输时间却是客观存在的。柔性车间中运输时间会随着机器的柔性选择而动态变化,若忽略此时间,车间调度的优化性能会有很大影响。基于此,本文将运输时间影响因子增加到柔性车间调度模型中,研究考虑运输时间的柔性作业车间调度问题。首先,深入分析考虑运输时间的柔性作业车间调度问题,在传统调度模型的基础上加入了新的假设和约束,建立了以最大完工时间最小、瓶颈机器负荷最小和机器总负荷最小为目标的新型带运输时间的柔性作业车间调度模型。其次,针对新的模型提出基于记忆指导的混合遗传模拟退火算法进行求解。不同于传统的串行混合结构,本文利用模拟退火算法实现对动态记忆库的局部优化,并将优化后的记忆库种群作为遗传算法的方向指导,融合了两种算法的全局和局部搜索能力。在遗传算法中做了如下改进:初始化规则上,设计了考虑运输时间的最短工作时间法改善初始种群的质量;交叉算子上,前期以较大的概率引入记忆库优质种群以提高算法的搜索速度;变异算子上,根据适值变化动态调整变异概率,防止算法在后期过早停止进化。在模拟退火算法中基于有效基因块设计了新的邻域结构,确保局部搜索的有效性。针对多个优化目标,本文采用改进Pareto排序和小生境技术的拥挤距离进行二级适值分配,保证算法收敛至均匀分布的Pareto曲面。最后,采用加入两类运输时间的26组基准算例进行测试,以解的质量和解的分布度作为本文算法和传统遗传算法的评价标准。每组算例分别连续运行10次,共得到520组实验结果。实验表明,与传统遗传算法相比,本文提出的混合算法总能得到质量更优、分布更均匀的Pareto非支配解。并且随着问题规模和运输时间的增加,优化程度越明显,进一步验证了本文算法在求解考虑运输时间的柔性作业车间调度问题上的可行性和有效性。