Preemptive Scheduling with Release Times, Deadlines, and Due Times

Abstract

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 .lob m 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.