An iterated greedy algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times

作者：Deng, Guanlong; Gu, Xingsheng^*

来源：International Journal of Systems Science, 2014, 45(3): 351-362.

DOI：10.1080/00207721.2012.723054

• scheduling
• heuristics
• single machine
• tardiness
• iterated greedy algorithm

This article presents an enhanced iterated greedy (EIG) algorithm that searches both insert and swap neighbourhoods for the single-machine total weighted tardiness problem with sequence-dependent setup times. Novel elimination rules and speed-ups are proposed for the swap move to make the employment of swap neighbourhood worthwhile due to its reduced computational expense. Moreover, a perturbation operator is newly designed as a substitute for the existing destruction and construction procedures to prevent the search from being attracted to local optima. To validate the proposed algorithm, computational experiments are conducted on a benchmark set from the literature. The results show that the EIG outperforms the existing state-of-the-art algorithms for the considered problem.

• 出版日期2014-3-1
• 单位华东理工大学