变量块内部迭代算法求解零空闲流水车间问题

Variable-block internal iteration algorithm for solving no-idle permutation flowshop scheduling problem

零空闲流水车间问题(NIFSP)是流水车间问题中带有约束条件的典型NP-hard问题,在大多数现实场景下,零空闲约束是对机器的基本要求。而目前关于NIFSP问题提出的算法对于较大规模算例、综合性能及参数调整的灵活性较差。为此,以最小化最大完工时间为目标,提出了一种可变内部迭代算法VIIA。在VIIA的初始化阶段,使用改进的FRB5产生初始解,提高了FRB5的效率,在保证算法性能的同时极大地缩短了CPU消耗时间。在破坏重建阶段,通过增加对移除工件块数量的内部迭代,从而灵活调整参数值。VIIA增大了邻域搜索,以适应不同规模的算例。为了验证VIIA算法的性能,将该算法与在流水车间调度问题中表现优秀的几种算法进行了比较。实验结果证明了VIIA在NIFSP问题求解上性能的优越性,并且在最优解的搜索上,性能明显优于对比算法。

The no-idle flowshop problem(NIFSP)is a typical NP-hard problem with constraints in the flowshop problem.In most real-world scenarios,the no-idle constraint is the basic requirement for the machine.However,the current proposed algorithms on the NIFSP problem have poor flexibility in comprehensive performance and parameter adjustment,for large-scale instances.To this end,this paper proposed an variable block internal iteration algorithm named VIIA with the goal of minimizing the maximum makespan.In the initialization phase of VIIA,it used the improved FRB5 produced the initial solutions,which improved the efficiency of FRB5,and greatly reduced the CPU consumption time while ensuring the algorithm performance.In the destruction reconstruction phase,it increased the internal iteration of the number of removed variable blocks,thus flexibly adjusted the parameter values.VIIA increased the neighborhood search to adapted to different size of instances.In order to verify the performance of VIIA,the algorithm was compared with several algorithms that perform well in the flowshop scheduling problem.The experimental results demonstrate the superiority of VIIA in solving the NIFSP problem,and the performance of VIIA is obviously better than that of the comparison algorithms in the search of the optimal solution.