带不相关并行机和有限缓冲MHFS调度的混合启发式算法

来源期刊：控制与决策2021年第3期

论文作者：轩华 郑倩倩 李冰

文章页码：565 - 576

关键词：多阶段混合流水车间;有限缓冲;不相关并行机;最小化最大完工时间;混合启发式算法;

摘    要：研究每阶段含不相关并行机的多阶段混合流水车间问题（MHFSP）,工件的加工时间取决于所分配的机器,相邻阶段之间缓冲区能力有限.鉴于直接求解该NP-hard问题较为困难,将其转化为带阻塞和不相关并行机的MHFSP （BMHFSP-UPM）,建立整数规划模型,基于遗传算法（GA）和禁忌搜索（TS）提出一种混合启发式算法（HHGA&TS）进行求解.在该算法中,设计基于多阶段并行加工的二维矩阵编码方案,继而基于二维矩阵元胞组的初始解群体表述设计参数自适应策略;引入基于工件位-基因位的单点倒置交叉以及基于机器号的单点变异过程,利用GA求解机制完成解更新过程;设计机器号次序交换（MNE）、工件位置交换（JNE）、工件工序变异（JNM）三种邻域解移动规则,从而完成基于MNE-JNE-JNM的TS二次优化.仿真实验测试了多达120个工件的720组不同规模实例,结果表明,相较于GA、TS及NEH-IGA,所提出的混合启发式算法在解的质量方面表现更佳.