基于启发式-遗传算法的混合流水车间成套订单问题

摘要

cqvip:针对并行机带工艺约束的混合流水车间环境下的成套订单问题,提出一种基于分批调度策略的启发式遗传算法。首先,以最大化加权成套订单数为目标建立数学模型,对工件分批采用内层遗传算法生成初始调度;再以外层启发式规则转化目标为最大加权成套订单数,设计一种订单评价指标用于突破交货时间瓶颈;最后,内外层算法循环优化,直到不存在瓶颈即得到满意解。实例验证结果显示,启发式遗传算法能在20代以内得到每组最优调度,种群规模大于50时得到最优解的概率达到70%。对比实验结果显示,当问题规模增加到40个工件时,遗传算法求解时间显著增加,在不同问题规模中临界比最小(SCR)规则优化后的加权成套订单数均较启发式遗传算法更少。启发式遗传算法能在实际工程中够将加权成套订单数提高到1.5倍以上,使加工时间平均缩短5.1%。结果表明,启发式遗传算法能够改善成套订单问题在混合流水车间环境下易陷入局部最优的问题,可在大规模复杂混合流水车间的订货型企业中实现计划与生产同步,具有实际意义。