On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals
Barbara Simons, Michael Sipser
Operations Research · 1984 · Volume 32 · Issue 1
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
Enable JavaScript for citation tools and additional paper interactions.