Algoristics for Single-Machine Sequencing with Precedence Constraints

Thomas E. Morton and Bala Ganga Dharan
Additional contact information
Thomas E. Morton: Carnegie-Mellon University
Bala Ganga Dharan: Carnegie-Mellon University

Management Science, 1978, vol. 24, issue 10, 1011-1020

Abstract: Although Horn, Sidney and Lawler have considered the problem of minimizing weighted mean flow time for n jobs with precedence constraints on one machine, practical exact algorithms for the general case remain elusive. Two relatively sophisticated heuristics are presented which are computationally attractive. Each is optimal on large subclasses of problems; computational study demonstrates each to be extremely close to optimal in general. Such heuristics are dubbed "algoristics." The first-come first-served heuristic serves as a benchmark. Finally, a simple "myopic" heuristic produces about 80% of the savings of the algoristics; it possesses the advantages of a dispatching rule. A standard branch and bound procedure has also been computed for a large subset of problems for comparison purposes. Planning horizon results are also derived.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.24.10.1011 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:24:y:1978:i:10:p:1011-1020

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().