A comparison of four methods for minimizing total tardiness on a single processor with sequence dependent setup times

Much of the research on operations scheduling problems has either ignored s etup times or assumed that setup times on each machine are independent of t he job sequence. This paper considers the problem of scheduling a single ma chine for minimizing total tardiness in a sequence dependent setup environm ent. The comparative performance of branch-and-bound, genetic search, simul ated annealing and random-start pairwise interchange was evaluated in this problem setting. The experimental results suggest that simulated annealing and random-start pairwise interchange are viable solution techniques that c an yield good solutions to a large combinatorial problem when considering t he tardiness objective with sequence dependent setup times. However, branch -and-bound may be the preferred solution technique in solving smaller probl ems, and it is the only solution technique tested that will confirm an opti mum solution has been reached. The methods considered in this research offe r promise to deal with a class of scheduling problems, which have been cons idered difficult by both researchers and practitioners. (C) 2000 Elsevier S cience Ltd. All rights reserved.