An Effective Iterated Greedy Algorithm for a Robust Distributed Permutation Flowshop Problem With Carryover Sequence-Dependent Setup Time

被引:32
作者
Jing, Xue-Lei [1 ,2 ]
Pan, Quan-Ke [1 ]
Gao, Liang [3 ]
Wang, Ling [4 ]
机构
[1] Shanghai Univ, Sch Mech Engn & Automat, Shanghai 200444, Peoples R China
[2] Liaocheng Univ, Liaocheng 252059, Shandong, Peoples R China
[3] Huazhong Univ Sci & Technol, State Key Lab Digital Mfg Equipment & Technol, Wuhan 430074, Peoples R China
[4] Tsinghua Univ, Dept Automat, Beijing 100084, Peoples R China
来源
IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS | 2022年 / 52卷 / 09期
基金
美国国家科学基金会;
关键词
Production; Job shop scheduling; Uncertainty; Single machine scheduling; Automation; Search methods; Optimization; Carryover sequence-dependent setup time (CST); iterated greedy (IG) algorithm; scheduling; uncertain processing times (UPT); SCHEDULING PROBLEM; SEARCH ALGORITHM; PROCESSING TIME; MACHINE; SHOP; MAKESPAN; OPTIMIZATION; UNCERTAINTY; HEURISTICS;
D O I
10.1109/TSMC.2021.3131849
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
A new scheduling problem, the distributed permutation flowshop scheduling problem with uncertain processing times and carryover sequence-dependent setup time (DPUC), is addressed. The DPUC is an important application problem in modern electronics manufacturing. A robust model is established for the DPUC with makespan criterion. A counter-intuitive paradox is found, that is, adding a new job to one of the production lines can reduce the completion time of the production line. Two acceleration methods are provided to save computational efforts. An iterated greedy algorithm called IG_FS is proposed to solve the DPUC. A heuristic based on the well-known NEH is proposed to generate the initial solution for the IG_FS. In the destruction phase of the IG_FS, dynamic sizes based on both adaptability and randomness are provided to improve the exploration capability. During the local search phase of the IG_FS, a hybrid local search method consisting of shift and swap operators is presented to exploit more diverse search areas. Extensive experiments show that the proposed IG_FS performs significantly better than the six competing algorithms adapted from the closely related scheduling literature.
引用
收藏
页码:5783 / 5794
页数:12
相关论文
共 55 条