The Deadline Constrained Weighted Completion Time Problem: Analysis of a Heuristic

Marc E. Posner
Additional contact information
Marc E. Posner: The Ohio State University, Columbus, Ohio

Operations Research, 1988, vol. 36, issue 5, 742-746

Abstract: A greedy heuristic that schedules jobs on one machine is examined. The problem considered is to minimize the sum of weighted completion times subject to deadline constraints. Both theoretical and empirical evidence are presented to suggest that this method finds solutions that are near optimal. Optimality conditions are developed. Also, an analysis of the relative error is presented. Worst case bounds are found that are based on the problem parameters. In addition, we show that the relative error goes to zero as the problem size goes to infinity.

Keywords: production scheduling; single machine scheduling; programming; bounds for a greedy heuristic (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.36.5.742 (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:oropre:v:36:y:1988:i:5:p:742-746

Access Statistics for this article

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