Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops

Yookun Cho and Sartaj Sahni
Additional contact information
Yookun Cho: University of Minnesota, Minneapolis, Minnesota
Sartaj Sahni: University of Minnesota, Minneapolis, Minnesota

Operations Research, 1981, vol. 29, issue 3, 511-522

Abstract: We study the problem of obtaining feasible preemptive schedules for independent jobs. It is assumed that each job has associated with it a release and due time. No job can begin before its release time. All jobs must be completed by their respective due times. It is shown that determining the existence of feasible preemptive schedules for two processor flow and job shops is NP -hard in the strong sense even when all jobs have the same due time. A linear programming formulation for the open shop problem is obtained. Also, a fast polynomial time algorithm is obtained for a restricted class of open shop problems.

Date: 1981
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.29.3.511 (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:29:y:1981:i:3:p:511-522

Access Statistics for this article

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