Normal view MARC view

A Survey of algorithms for the single machine total weighted tardiness scheduling problem

Author: Van Wassenhove, Luk N. ; Abdul-Razaq, T. S. ; Potts, Christopher N.INSEAD Area: Technology and Operations ManagementIn: Discrete Applied Mathematics, vol. 26, 1990 Language: EnglishDescription: p. 235-253.Type of document: INSEAD ArticleNote: Please ask the Library for this articleAbstract: This paper surveys algorithms for the problem of scheduling jobs on a single machine to minimize total weighted tardiness. Special attention is given to two dynamic programming and four branch and bound algorithms. The dynamic programming algorithms both use the same recursion defined on sets of jobs, but they generate the sets in lexicographic order and cardinality order respectively. Two of the branch and bound algorithms use the quickly computed but possibly rather weak lower bounds obtained from linear and exponential functions of completion times problems. These algorithms rely heavily on dominance rules to restrict the search. The other two branch and bound algorithms use lower bounds obtained from the Lagrangean relaxation of machine capacity constraints and from dynamic programming state-space relaxation. They invest a substantial amount of computation time at each node of the search tree in an attempt to generate tight lower bounds and thereby generate only small search trees. A computational comparison of all these algorithms on problems with up to 50 jobs is given.
Tags: No tags from this library for this title. Add tag(s)
Log in to add tags.
Item type Current location Call number Status Date due
INSEAD Article Doriot Library
Available

Please ask the Library for this article

This paper surveys algorithms for the problem of scheduling jobs on a single machine to minimize total weighted tardiness. Special attention is given to two dynamic programming and four branch and bound algorithms. The dynamic programming algorithms both use the same recursion defined on sets of jobs, but they generate the sets in lexicographic order and cardinality order respectively. Two of the branch and bound algorithms use the quickly computed but possibly rather weak lower bounds obtained from linear and exponential functions of completion times problems. These algorithms rely heavily on dominance rules to restrict the search. The other two branch and bound algorithms use lower bounds obtained from the Lagrangean relaxation of machine capacity constraints and from dynamic programming state-space relaxation. They invest a substantial amount of computation time at each node of the search tree in an attempt to generate tight lower bounds and thereby generate only small search trees. A computational comparison of all these algorithms on problems with up to 50 jobs is given.

Digitized

There are no comments for this item.

Log in to your account to post a comment.
Koha 3.18 - INSEAD Library Catalogue
Library Home | Contact Us | What's Koha?