Iterative Local Search Heuristic for the Single Machine Scheduling Problem with Sequence Dependent Setup Times and Due Dates

In this paper the NP-hard problem of scheduling jobs in a single machine with sequence dependent setup times is considered with the objective of minimizing the total tardiness with respect to the due dates. An iterative local search (ILS) heuristic is proposed which uses a GRASP (greedy randomized adaptive search procedure) algorithm to generate an initial solution. The ILS heuristic is compared with the GRASP algorithm proposed by Gupta and Smith (2006) and with the ant colony optimization (ACO) algorithm of Ching and Hsiao (2007). These algorithms obtained better solutions than other algorithms from the literature. Computational tests, on a set of test problems involving up to 85 jobs, show that our ILS heuristic is very efficient and competitive.