A Greedy Heuristic for Single Machine Sequencing with Precedence Constraints

Howard J. Weiss
Additional contact information
Howard J. Weiss: Temple University

Management Science, 1981, vol. 27, issue 10, 1209-1216

Abstract: We present a greedy heuristic for the n job/1 machine scheduling problem with precedence constraints. This method is useful whenever the manager's optimization criteria is the sum of weighted or unweighted completion times, the sum of weighted or unweighted flow times, (with or without release dates), the sum of weighted or unweighted working times, the sum of weighted or unweighted lateness, average completion time, average flow time, average waiting time or average lateness. The greedy heuristic found the optimal solution for 58 of 68 test problems for which a branch and bound method was used to find the optimal solution. The heuristic is, of course, much easier to implement (and executes in less time). The greedy heuristic fared well in comparison with a simple myopic heuristic presented by Morton and Dharan (Morton. T. E., B. G. Dharan. 1978. Algoristics for single machine sequencing with precedence constraints. Management Sci. 24 (10) 1011--1020.).

Keywords: production/scheduling; heuristic: greedy; programming: integer algorithms; branch and bound (search for similar items in EconPapers)
Date: 1981
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.27.10.1209 (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:27:y:1981:i:10:p:1209-1216

Access Statistics for this article

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