MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Linear-time approximation schemes for scheduling malleable parallel tasks

Jansen, Klaus and Porkolab, Lorant

November 1998, 15 pages.

Status: available - back from printing

A malleable parallel task is one whose execution time is a function of the number of (identical) processors alloted to it. We study the problem of scheduling a set of $n$ independent malleable tasks on a fixed number of parallel processors, and propose an approximation scheme that for any fixed $\epsilon > 0$, computes in $O(n)$ time a non-preemptive schedule of length at most $(1+\epsilon)$ times the optimum.

  • Attachement: (236 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Jansen, Klaus and Porkolab, Lorant},
  TITLE = {Linear-time approximation schemes for scheduling malleable parallel tasks},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-98-1-025},
  MONTH = {November},
  YEAR = {1998},
  ISSN = {0946-011X},