On maximizing the throughput of multiprocessor tasks
We consider the problem of scheduling n independent multiprocessor tasks with due dates and unit processing times, where the objective is to compute a schedule maximizing the throughput. We derive the complexity results and present several approximation algorithms. For the parallel variant of the problem, we introduce the first-fit increasing algorithm and the latest-fit increasing algorithm, and prove that their worst-case ratios are 2 and 2 - 1/m, respectively (m greater than or equal to 2 is the number of processors). Then we propose a revised algorithm with a worst-case ratio bounded by 3/2 - 1/(2m) (m is odd) and 3/2 - 1/(2m - 2) (m is even). For the dedicated variant, we present a simple greedy algorithm. We show that its worst-case ratio is bounded by rootm + 1. We straighten this result by showing that the problem cannot be approximated within a factor of m(1/2-c) for any epsilon > 0, unless NP = ZPP. (C) 2002 Elsevier Science B.V. All rights reserved.
multiprocessor task complexity approximation algorithm