混合迭代贪婪算法求解准时生产分布式流水线调度问题

Hybrid iterated greedy algorithm for just in time distributed permutation flowshop scheduling problem

针对以最小化总延迟时间为优化目标的分布式置换流水线问题(distributed permutation flowshop scheduling problem,DPFSP),建立问题排序模型,并提出混合迭代贪婪算法(hybrid iterated greedy,HIG)进行求解.基于问题特点提出最小工期差值(smallest due date difference value,SDV)规则及3种工厂分配规则,同时结合问题性质提出两种工件插入各工厂内部时问题目标值的下界估计方法.首先,通过实验确定使用分配规则1将工件向各工厂进行分配,同时结合下界估计方法的NEH作为改进启发式算法以生成较高质量初始解;其次,为了增加解的多样性,提出一种关键工厂的移除策略和适用于问题的模拟退火机制;然后,设计基于4种有效邻域操作的两阶段变邻域下降搜索策略,用于在HIG每代中对问题解空间的不同区域进行较深入和细致的搜索;最后,通过仿真实验和算法比较验证了采用HIG求解所提出问题的有效性.

In this paper,for the distributed permutation flowshop scheduling problem,which is optimized to minimize the total tardiness,a problem sorting model is established,and a hybrid iterated greedy(HIG)algorithm is proposed to solve the problem.Based on the characteristics of the problem,this paper proposes the minimum due date difference value(SDV)rule and three kinds of factory assignment rules.At the same time,combining with the nature of the problem,this paper proposes two methods to estimate the lower bound of the target value of the problem when the job is assigned to each factor.At the same time,combining with the nature of the problem,two methods for estimating the lower bound of the target value of the problem are proposed.Firstly,through experimental analysis,it is determined that the SDV is used as a encoding rule,and the NEH combined with the lower bound estimation method is used as an improved heuristic algorithm to generate a higher quality initial solution.Secondly,in order to increase the diversity of solutions,a key factory removal strategy and simulated annealing mechanism are proposed.Then,the design based on four two-stage variable neighborhood descent search strategy for effective neighborhood operation is used to search different regions of the problem solution space in depth and detail in each generation of the HIG.Finally,simulation experiments and algorithm comparison verify the effectiveness of HIG in solving this problem.