A Comparison of Four Methods for Minimizing Total Tardiness on a Single Processor with Sequence Dependent Setup Times
First page number:
Last page number:
Much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. This paper considers the problem of scheduling a single machine for minimizing total tardiness in a sequence dependent setup environment. The comparative performance of branch-and-bound, genetic search, simulated 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 can yield good solutions to a large combinatorial problem when considering the tardiness objective with sequence dependent setup times. However, branch-and-bound may be the preferred solution technique in solving smaller problems, and it is the only solution technique tested that will confirm an optimum solution has been reached. The methods considered in this research offer promise to deal with a class of scheduling problems, which have been considered difficult by both researchers and practitioners.
Branch-and-bound; Branch and bound algorithms; Genetic algorithms; Genetic search; Scheduling; Sequence dependent setup times; Simulated annealing; Simulated annealing (Mathematics); Tardiness
Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.
Rubin, P. A.,
Ragatz, G. L.
A Comparison of Four Methods for Minimizing Total Tardiness on a Single Processor with Sequence Dependent Setup Times.