An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem

• We propose an improved IG algorithm for the no-wait flowshop scheduling problem.
• The proposed algorithm is incorporated with a Tabu-based reconstruction strategy.
• Simulation results confirm the advantages of utilizing the new reconstruction scheme.
• Our algorithm is more effective than other competitive algorithms in the literature.
• 43 new upper bound solutions for the problem have been made available.

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.

Figure optionsDownload as PowerPoint slide