Efficient iterated greedy algorithm to minimize makespan for the no-wait flowshop with sequence dependent setup times

摘要

In this paper, an efficient iterated greedy algorithm is proposed for the SDST (Sequence Dependent Setup Time) no-wait flowshop with makespan minimization, which is known to be NP-hard. By introducing effective operators, the Iterated Greedy algorithm is adapted to the considered problem. To improve the quality of solutions, Local Search is incorporated into the modified Iterated Greedy algorithm. The proposed algorithm is compared with BIH, GAPH1-GAPH4, and IG_Ruiz on Taillard's instances of ssd10, ssd50, ssd100, and ssdl25. Experimental results demonstrate that the proposal outperforms BIH and GAPH1-GAPH4. As well, the proposal is more effective than IG_Ruiz under the same computation-time criterion.