Journal
APPLIED SOFT COMPUTING
Volume 30, Issue -, Pages 604-613Publisher
ELSEVIER
DOI: 10.1016/j.asoc.2015.02.006
Keywords
No-wait flow shop; Iterated greedy algorithm; Tabu search; Makespan
Categories
Funding
- National Natural Science Foundation of China [61273233, 61473141, 61104176]
- Research Foundation for the Doctoral Program of Higher Education [20120002110035, 20130002130010]
Ask authors/readers for more resources
This paper proposes a Tabu-mechanism improved iterated greedy (TMIIG) algorithm to solve the no-wait flowshop scheduling problem with a makespan criterion. The idea of seeking further improvement in the iterated greedy (IG) algorithm framework is based on the observation that the construction phase of the original IG algorithm may not achieve good performance in escaping from local minima when incorporating the insertion neighborhood search. To overcome this limitation, we have modified the IG algorithm by utilizing a Tabu-based reconstruction strategy to enhance its exploration ability. A powerful neighborhood search method that involves insert, swap, and double-insert moves is then applied to obtain better solutions from the reconstructed solution in the previous step. Empirical results on several benchmark problem instances and those generated randomly confirm the advantages of utilizing the new reconstruction scheme. In addition, our results also show that the proposed TMIIG algorithm is relatively more effective in minimizing the makespan than other existing well-performing heuristic algorithms. (C) 2015 Elsevier By. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available