On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals

Barbara Simons and Michael Sipser
Additional contact information
Barbara Simons: IBM Research, San Jose, California
Michael Sipser: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1984, vol. 32, issue 1, 80-88

Abstract: We consider the problem of scheduling n unit-time jobs with multiple release time/deadline intervals, which are intervals of time in which the job can be scheduled. A feasible schedule is one in which each job is run in its entirety within one of its release time/deadline intervals. We show that the general problem is NP-complete, but that for a special case one can determine in polynomial time if a feasible schedule exists. If there is a feasible schedule for the special case, then it is possible to obtain both a schedule that minimizes the maximum completion time and also one that minimizes the sum of the completion times of all jobs. If, on the other hand, there is no feasible schedule, then one can determine the minimum number of jobs that must be removed to make the problem instance feasible.

Keywords: 432 polynomial time algorithm and NP completeness; 486 scheduling with release times; 584 scheduling unit-time jobs on identical machines (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.32.1.80 (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:32:y:1984:i:1:p:80-88

Access Statistics for this article

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