Distributed Flow Shop Scheduling with Sequence-Dependent Setup Times Using an Improved Iterated Greedy Algorithm  

作　　者：Xue Han Yuyan Han Qingda Chen Junqing Li Hongyan Sang Yiping Liu Quanke Pan Yusuke Nojima 

机构地区：[1]the School of Computer Science,Liaocheng University,Liaocheng 252000,China [2]the State Key Laboratory of Synthetical Automation for Process Industries,Northeastern University,Shenyang 110819,China [3]the School of Information Science and Engineering,Shandong Normal University,Jinan 252000,China [4]the College of Computer Science and Electronic Engineering,Hunan University,Changsha 410082,China [5]the School of Mechatronic Engineering and Automation,Shanghai University,Shanghai 200072,China [6]the Department of Computer Science and Intelligent Systems,Osaka Prefecture University,Osaka 599-8531,Japan

出　　处：《Complex System Modeling and Simulation》2021年第3期198-217,共20页复杂系统建模与仿真（英文）

基　　金：This work was jointly supported by the National Natural Science Foundation of China(Nos.61803192,61973203,61966012,61773192,61603169,61773246,and 71533001);Thanks for the support of Shandong province colleges and universities youth innovation talent introduction and education program.

摘　　要：To meet the multi-cooperation production demand of enterprises,the distributed permutation flow shop scheduling problem(DPFSP)has become the frontier research in the field of manufacturing systems.In this paper,we investigate the DPFSP by minimizing a makespan criterion under the constraint of sequence-dependent setup times.To solve DPFSPs,significant developments of some metaheuristic algorithms are necessary.In this context,a simple and effective improved iterated greedy(NIG)algorithm is proposed to minimize makespan in DPFSPs.According to the features of DPFSPs,a two-stage local search based on single job swapping and job block swapping within the key factory is designed in the proposed algorithm.We compare the proposed algorithm with state-of-the-art algorithms,including the iterative greedy algorithm(2019),iterative greedy proposed by Ruiz and Pan(2019),discrete differential evolution algorithm(2018),discrete artificial bee colony(2018),and artificial chemical reaction optimization(2017).Simulation results show that NIG outperforms the compared algorithms.

关 键 词：distributed permutation flow shop iterated greedy local search swapping strategy 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]