Preemptive Scheduling of a Multiprocessor System with Memories To Minimize L(MAX)

摘要

We develop an O(K(sq)n + nlogn) algorithm to obtain a preemptive schedule that minimizes L sub max when n jobs with given memory requirements are to be scheduled on m processors (n > or = m) of given memory sizes. k is the number of distinct due dates. The value of the minimum L sub max can itself be found in O(kn + nlogn) time. (Author)