Scheduling Malleable Tasks with Precedence Constraints

zum Volltext (274 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • März 2009
Seitenbereich34 S.

In this paper we propose an approximation algorithm for scheduling malleable tasks with precedence constraints. Based on an interesting model for malleable tasks with continuous processor allotments by Prasanna and Musicus \cite{PrMu91,PrMu94,PrMu96}, we define two natural assumptions for malleable tasks: the processing time of any malleable task is non-increasing in the number of processors allotted, and the speedup is concave in the number of processors. We show that under these assumptions the work function of any malleable task is non-decreasing in the number of processors and is convex in the processing time. Furthermore, we propose a two-phase approximation algorithm for the scheduling problem. In the first phase we solve a linear program to obtain a fractional allotment for all tasks. By rounding the fractional solution, each malleable task is assigned a number of processors. In the second phase a variant of the list scheduling algorithm is employed. %In the phases we use two parameters $\mu\in\{1,\dots\lfloor (m+1)/2\rfloor\}$ and $\rho\in [0,1]$ for the allotment and the rounding, respectively, where $m$ is the number of processors. By choosing appropriate values of the parameters, we show (via a nonlinear program) that the approximation ratio of our algorithm is at most $100/63+100(\sqrt{6469}+13)/5481\approx 3.291919$. We also show that our result is asymptotically tight.
Statische URL
IDNummer des Berichts :
  • TR_0906