Preemptive Scheduling with Release Times, Deadlines, and Due Times
Charles U. Martel · Journal of the ACM · 1982
Given n jobs, each of which has a release time, a deadhne, and a processing reqmrement, the problem of determining whether there exists a preemptwe schedule on m uniform machines which completes each .lobm the t~me mterval between its release t~me and its deadlme Js examined An O(m2n 4 + n ~) algonthm is presented which uses a generahzauon of network flow techmques to construct such a schedule whenever one extsts This algorithm is then used wRh search techniques to find a schedule which mmtm~zes maxtmum lateness.Categortes and SubJect Descriptors D 4 1 [