Preemptive Scheduling of a Single Machine to Minimize Maximum Cost Subject to Release Dates and Precedence Constraints

K. R. Baker, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan
Additional contact information
K. R. Baker: Dartmouth College, Hanover, New Hampshire
E. L. Lawler: University of California, Berkeley, California
J. K. Lenstra: Mathematisch Centrum, Amsterdam, The Netherlands
A. H. G. Rinnooy Kan: Erasmus University, Rotterdam, The Netherlands

Operations Research, 1983, vol. 31, issue 2, 381-386

Abstract: Suppose n jobs are to be processed on a single machine, subject to release dates and precedence constraints. The problem is to find a preemptive schedule which minimizes the maximum job completion cost. We present an O ( n 2 ) algorithm for this problem, generalizing previous results of E. L. Lawler.

Keywords: 432 computational complexity; 584 single machine scheduling (search for similar items in EconPapers)
Date: 1983
References: Add references at CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.31.2.381 (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:31:y:1983:i:2:p:381-386

Access Statistics for this article

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