Preemptive Scheduling to Minimize Maximum Completion Time on Uniform Processors with Memory Constraints

We consider the problem of preemptively scheduling n jobs on m processors. The ith job has a processing requirement p_i and a memory requirement q_i. The ith processor has a speed s_i and a memory capacity c_i. The ith job can be run on the jth processor whenever c_j ≥ q_i. When all jobs have a deadline D_i we develop an O(n log m) time algorithm that finds a feasible schedule or determines that no such schedule exists. We then use this algorithm to find the minimum time by which all jobs can be completed in O(nm log²m) time.