A Penalty Groups-Assisted Iterated Greedy Integrating Idle Time Insertion:Solving the Hybrid Flow Shop Group Scheduling with Delivery Time Windows  

作　　者：Qianhui Ji Yuyan Han Yuting Wang Biao Zhang Kaizhou Gao 

机构地区：[1]the School of Computer Science,Liaocheng University,Liaocheng 252059,China [2]Institute of Systems Engineering,Macao University of Science and Technology,Macao 999078,China

出　　处：《Complex System Modeling and Simulation》2024年第2期137-165,共29页复杂系统建模与仿真（英文）

基　　金：This work was supported by the Natural Science Foundation of Shandong province(No.ZR2023MF022);National Natural Science Foundation of China(Nos.61973203,61803192,62106073,and 61966012);Guangyue Young Scholar Innovation Team of Liaocheng University(No.LCUGYTD2022-03).

摘　　要：The hybrid flow shop group scheduling problem(HFGSP)with the delivery time windows has been widely studied owing to its better flexibility and suitability for the current just-in-time production mode.However,there are several unresolved challenges in problem modeling and algorithmic design tailored for HFGSP.In our study,we place emphasis on the constraint of timeliness.Therefore,this paper first constructs a mixed integer linear programming model of HFGSP with sequence-dependent setup time and delivery time windows to minimize the total weighted earliness and tardiness(TWET).Then a penalty groups-assisted iterated greedy integrating idle time insertion(PG IG ITI)is proposed to solve the above problem.In the PG IG ITI,a double decoding strategy is proposed based on the earliest available machine rule and the idle time insertion rule to calculate the TWET value.Subsequently,to reduce the amount of computation,a skip-based destruction and reconstruction strategy is designed,and a penalty groups-assisted local search is proposed to further improve the quality of the solution by disturbing the penalized groups,i.e.,early and tardy groups.Finally,through comprehensive statistical experiments on 270 test instances,the results prove that the proposed algorithm is effective compared to four state-of-the-art algorithms.

关 键 词：hybrid flow shop group scheduling iterated greedy algorithm delivery time windows sequence-dependent setup time 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]