Control and Decision
1001-0920
10.13195/j.kzyjc.2021.0426
article
混合迭代贪婪算法求解准时生产分布式流水线调度问题
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) 规则及三种工厂分配规则, 同时结合问题性质提出两种工件插入各工厂内部时问题目标值的下界估计方法. 首先, 通过实验确定使用分配规则1将工件向各工厂进行分配, 同时将结合下界估计方法的NEH作为改进启发式算法以生成较高质量初始解. 其次, 为了增加解的多样性, 提出一种关键工厂的移除策略和适用于问题的模拟退火机制. 然后, 设计基于四种有效邻域操作的两阶段变邻域下降搜索策略, 用于在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 algorithm 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. First, 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 is based on four A 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 HIG. Finally, simulation experiments and algorithm comparison verify the effectiveness of hig in solving this problem.
分布式流水线调度; 总延迟时间; 混合迭代贪婪算法; 下界; 分配规则
distributed permutation flowshop scheduling; total tardiness; hybrid iterated greedy; low bound; assignment rule
钱斌,刘荻飞,胡蓉,张梓琪
qianbin,liudifei,hurong,zhangziqi
1.昆明理工大学信息工程与自动化学院;2.昆明理工大学机电工程学院
Faculty of Information Engineering and Automation, Kunming University of Science and Technology
kzyjc/article/abstract/2021-0426