改进遗传算法求解带不相关并行机的HFSP

王静云，王 雷，李佳路

（安徽工程大学机械工程学院，安徽，芜湖 241000）

0 引言

车间调度是典型的NP-hard 问题，混合流水车间调度问题（Hybrid flow shop scheduling problem,HFSP）是车间调度中常见的调度类型，是传统的流水线生产与并行机调度的综合。目前，混合流水车间调度广泛存在于化工、冶金、纺织、机械、装配、运输等行业中[1]。

近年来，越来越多的智能优化算法应用于HFSP。张源等在传统的差分算法上结合了反向学习策略生成初始种群，添加自适应差分因子，并在个体选择时引入Metropolis 准则[2]；Zhou 等人运用带分布估计的混合差分进化算法，求解了一种可重入混合流水车间调度问题[3]；Mageed 和Ibrahim 研究了无等待的两阶段问题，采用PSO 算法优化了总延迟时间[4]；Meng 等人针对不相关并行机的节能混合流水车间调度问题，提出了改进的遗传算法，通过对比模拟退火算法和迁徙鸟类优化算法，证明了其改进的遗传算法的有效性[5]；罗函明等针对布谷鸟算法常规解码方法难以获得最优解的缺点，提出一种改进的解码方法，通过对比原始规则解码、随机规则解码、改进规则解码所得结果，验证其有效性[6]；Mousavi 等人提出了一种基于遗传算法的近似求解方法，求解了最大完成时间和总拖延时间最小化的双目标问题[7]；杜利珍等提出了基于权重的编码方式的果蝇优化算法，来求解混合流水车间调度问题，并通过与经典算法进行对比验证了其算法的有效性[8]；宋存利采用正序解码和逆序解码，提出贪婪交叉算子变异算子，增加了种群的多样性，提高了遗传算法在求解HFSP 时的局部搜索能力[9]；……