A (3/2+\epsilon) approximation algorithm for scheduling malleable and non-malleable parallel tasks

zum Volltext (333 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • Februar 2012
Seitenbereich25 S.

In this paper we study a scheduling problem with malleable and non-malleable parallel tasks on $m$ processors. A non-malleable parallel task is one that runs in parallel on a specific given number of processors. The goal is to find a non-preemptive schedule on the $m$ processors which minimizes the makespan, or the latest task completion time. The previous best result is the list scheduling algorithm with an absolute approximation ratio of $2$. On the other hand, there does not exist an approximation algorithm for scheduling non-malleable parallel tasks with ratio smaller than $1.5$, unless $P=NP$. In this paper we show that a schedule with length $(1.5 +\epsilon) OPT$ can be computed for the scheduling problem in time $O(n \log n) + f(1/\epsilon)$. Furthermore we present an $(1.5 + \epsilon)$ approximation algorithm for scheduling malleable parallel tasks. Finally, we show how to extend our algorithms to the variant with additional release dates.
Statische URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000047
 
URN:NBNurn:nbn:de:101:1-201203015352
IDNummer des Berichts :
  • TR_1203