Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic

The single-machine tardiness problem with sequence dependent setup times is a core topic for scheduling studies. Tardiness is actually a difficult criterion to deal with, even in a relatively simple manufacturing system, such as a single-machine is strongly NP-hard. Motivated by the computational complexity of this problem, a simple iterated greedy (IG) heuristic is proposed to solve it. To validate and verify the proposed IG heuristic, computational experiments were conducted on three benchmark problem sets that included weighted and un-weighted tardiness problems. The experiment results clearly indicate that the proposed IG heuristic is highly effective as compared to the state-of-the-art meta-heuristics on the same benchmark instances. In terms of both solution quality and computational expense, this study successfully develops an effective and efficient approach for single-machine total tardiness problems with sequence dependent setup times. (C) 2008 Elsevier Ltd. All rights reserved.