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

1 December 1985

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research

Vol. 33 (6) , 1360-1380
https://doi.org/10.1287/opre.33.6.1360

Abstract

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.

Keywords

SCHEDULE
PROCESSOR
JOBS
MEMORY
SUP
PREEMPTIVE
UNIFORM
JTH
DEADLINE
CONSTRAINTS

This publication has 0 references indexed in Scilit: