Effective Iterated Greedy Algorithm for Flow-Shop Scheduling Problems with Time lags

作     者：Ning ZHAO Song YE Kaidian LI Siyu CHEN 

作者机构：school of mechanical engineeringuniversity of science and technology beijingBeijing 100083China 

出 版 物：《Chinese Journal of Mechanical Engineering》 (中国机械工程学报（英文版）)

年 卷 期：2017年第30卷第3期

页      面：652-662页

核心收录：

学科分类：08[工学] 0817[工学-化学工程与技术] 0807[工学-动力工程及工程热物理] 0802[工学-机械工程] 0811[工学-控制科学与工程] 0801[工学-力学（可授工学、理学学位）] 

基　　金：Supported by National Natural Science Foundation of China(Grant No.71301008) Beijing Municipal Natural Science Foundation of China(Grant No.9144030) 

主　　题：Permutation Non-permutation Flow shopTime lags . Makespan Iterated greedy algorithm 

摘      要：Flow shop scheduling problem with time lags is a practical scheduling problem and attracts many studies. Permutation problem（PFSP with time lags） is concentrated but non-permutation problem（non-PFSP with time lags） seems to be neglected. With the aim to minimize the makespan and satisfy time lag constraints, efficient algo- rithms corresponding to PFSP and non-PFSP problems are proposed, which consist of iterated greedy algorithm for permutation（IGTLP） and iterated greedy algorithm for non-permutation （IGTLNP）. The proposed algorithms are verified using well-known simple and complex instances of permutation and non-permutation problems with various time lag ranges. The permutation results indicate that the proposed IGTLP can reach near optimal solution within nearly 11% computational time of traditional GA approach. The non-permutation results indicate that the proposed IG can reach nearly same solution within less than 1% com- putational time compared with traditional GA approach. The proposed research combines PFSP and non-PFSP together with minimal and maximal time lag consideration, which provides an interesting viewpoint for industrial implementation.