多种群混合进化算法求解带工序跳跃的分布式异构批量流混合流水车间调度问题

摘要

针对以最小化最大完工时间、总流经时间、机器等待时间以及总加权提前时间和延迟时间为优化目标的带工序跳跃的分布式异构批量流混合流水车间调度问题，提出了一种多种群混合进化算法(Multi-Population Hybrid Evolutionary Algorithm,MPHEA)。首先，给出每个优化目标的计算方式，并制定合适的编码方案。其次，设计了总种群与4个子种群之间的并行协同进化策略。在对总种群执行混合交叉算子和变异操作后，依据快速非支配排序和拥挤距离更新种群，从而确保总种群的多样性和优质解的保留。同时，从总种群中提取出部分解，形成了4个子种群，每个子种群专注于优化一个特定目标。总种群与子种群并行进化的方式使得子种群在各自方向上进化时能够避免过分偏重于某一个目标，从而实现多个目标的均衡优化。考虑到工序跳跃的操作对调度问题的影响，采用了相应的工序跳跃启发式规则。最后，通过仿真实验验证了MPHEA解决该调度问题的有效性和优越性。

关键词

工序跳跃 / 分布式车间调度 / 批量流 / 异构工厂 / 高维多目标优化

基金资助

国家自然科学基金(61973120,62076095)