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

• 作 者: Ning ZHAO Song YE Kaidian LI Siyu CHEN
• 机 构: School of Mechanical Engineering, University of Science and Technology Beijing,
• 出 处: Chinese Journal of Mechanical Engineering
• 发表日期: 2017年03期
• 关键词: Permutation Non-permutation Flow shop Time lags Makespan Iterated greedy algorit

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 algorithms 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% computational 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.

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 algorithms 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% computational time compared with traditional GA approach. proposed research combines PFSP and non-PFSP together with minimal and maximal time lag consideration, which provides an interesting viewpoint for industrial implementation.