On maximizing the throughput of multiprocessor tasks

✍ Scribed by Aleksei V. Fishkin; Guochuan Zhang

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 289 KB
• Volume: 302
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00850-2

✦ Synopsis

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 ÿrst-ÿt increasing algorithm and the latest-ÿt increasing algorithm, and prove that their worst-case ratios are 2 and 2 -1=m, respectively (m ¿ 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 √ m+1. We straighten this result by showing that the problem cannot be approximated within a factor of m 1=2-for any ¿ 0, unless NP = ZPP.