Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Improved approximation schemes for scheduling unrelated parallel machines

Jansen, Klaus and Porkolab, Lorant

MPI-I-98-1-026. November 1998, 14 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We consider the problem of scheduling $n$ independent jobs on $m$ unrelated
parallel machines. Each job has to be processed by exactly one machine,
processing job $j$ on machine $i$ requires $p_{ij}$ time units, and the
objective is to minimize the makespan, i.e. the maximum job completion time.
We focus on the case when $m$ is fixed and develop a fully polynomial
approximation scheme whose running time depends only linearly on $n$. In the
second half of the paper we extend this result to a variant of the problem,
where processing job $j$ on machine $i$ also incurs a cost of $c_{ij}$, and
thus there are two optimization criteria: makespan and cost. We show that for
any fixed $m$, there is a fully polynomial approximation scheme that, given
values $T$ and $C$, computes for any fixed $\epsilon > 0$ a schedule in $O(n)$
time with makespan at most $(1+\epsilon)T$ and cost at most $(1 + \epsilon)C$,
if there exists a schedule of makespan $T$ and cost $C$.

References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-98-1-026.ps241 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Jansen, Klaus and Porkolab, Lorant},
  TITLE = {Improved approximation schemes for scheduling unrelated parallel machines},
  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-026},
  MONTH = {November},
  YEAR = {1998},
  ISSN = {0946-011X},