A Comparison of Four Methods for Minimizing Total Tardiness on a Single Processor with Sequence Dependent Setup Times

Document Type

Article

Publication Date

6-2000

Publication Title

Omega

Publisher

Elsevier

Volume

28

Issue

3

First page number:

313

Last page number:

326

Abstract

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.

Keywords

Branch-and-bound; Branch and bound algorithms; Genetic algorithms; Genetic search; Scheduling; Sequence dependent setup times; Simulated annealing; Simulated annealing (Mathematics); Tardiness

Disciplines

Business

Language

English

Permissions

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.

UNLV article access

Search your library

Share

COinS