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

Hybrid heuristic algorithm for multi-stage hybrid flow shop scheduling with unrelated parallel machines and finite buffers

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

A multi-stage hybrid flow shop problem(MHFSP) is studied with unrelated parallel machines at each stage,where job processing time depends on the assigned machine and the buffer capacity between adjacent production stages is limited. Because it is very difficult to solve this NP-hard problem directly, the original problem is transformed to the MHFSP with blocking and unrelated parallel machines(BMHFSP-UPM). An integer programming model is formulated,and a hybrid heuristic algorithm(HH-GA&TS) is then proposed to handle it based on the genetic algorithm(GA) and tabu search(TS). In this algorithm, a two-dimensional matrix coding scheme based on multi-stage parallel production is designed. A self-adaptive strategy of parameters is then developed according to the formulation of the initial solutions using a two-dimensional matrix cell group. Two single-point inverted crossover procedures using job location and gene location are designed, and a single-point mutation procedure using machine number is introduced, so that the GA is applied to update solutions. Finally, the three moving rules of neighborhood solutions are designed: Sequence exchange of machine number(MNE), exchange of job location(JNE), operation mutation of jobs(JNM). Thus the re-optimization process of TS using MNE-JNE-JNM is completed. Simulation experiments are performed on 720 different sized instances with up to 120 jobs. The results show that the hybrid algorithm can find a better quality schedule compared with the GA,the TS and the NEH-IGA.