An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion

作者：Pan Quan Ke^*; Wang Ling; Zhao Bao Hua

来源：International Journal of Advanced Manufacturing Technology, 2008, 38(7-8): 778-786.

DOI：10.1007/s00170-007-1120-y

• no-wait flow shop
• makespan
• iterated greedy algorithm
• speed-up method
• insert neighborhood
• local search

An improved iterated greedy algorithm (IIGA) is proposed in this paper to solve the no-wait flow shop scheduling problem with the objective to minimize the makespan. In the proposed IIGA, firstly, a speed-up method for the insert neighborhood is developed to evaluate the whole insert neighborhood of a single solution with (n-1)(2)supercript stop neighbors in time O(n(2)), where n is the number of jobs; secondly, an improved Nawaz-Enscore-Ham (NEH) heuristic is presented for constructing solutions in the initial stage and searching process; thirdly, a simple local search algorithm based on the speed-up method is incorporated into the iterated greedy algorithm to perform exploitation. The computational results based on some well-known benchmarks show that the proposed IIGA can obtain results better than those from some existing approaches in the literature.

• 出版日期2008-9
• 单位中国科学技术大学; 清华大学; 聊城大学