Scheduling Independent Multiprocessor Tasks

Abstract

We study the problem of scheduling a set of n independent multiprocessor tasks with prespecified processor allocations on a fixed number of processors. We propose a linear time algorithm that finds a schedule of minimum makespan in the preemptive model, and a linear time approximation algorithm that finds a schedule of makespan within a factor of (1+\eps) of optimal in the non-preemptive model. We extend our results by obtaining a polynomial time approximation scheme for the parallel processors variant of the multiprocessor task model.