000K  utf8
1100  $c2012
1500  eng
2050  urn:nbn:de:101:1-201203015352
3000  Jansen, Klaus
4000  A (3/2+ɛ) approximation algorithm for scheduling malleable and non-malleable parallel tasks  [Jansen, Klaus]
4209  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.
4950  https://nbn-resolving.org/urn:nbn:de:101:1-201203015352$xR$3Volltext$534
4961  https://macau.uni-kiel.de/receive/macau_mods_00001806
5051  004