@techreport{JansenPorkolab98-1-026,
TITLE = {Improved approximation schemes for scheduling unrelated parallel machines},
AUTHOR = {Jansen, Klaus and Porkolab, Lorant},
LANGUAGE = {eng},
URL = {http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-026},
NUMBER = {MPI-I-1998-1-026},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {1998},
DATE = {1998},
ABSTRACT = {We consider the problem of scheduling $n$ independent jobs on $m$ unrelated <br>parallel machines. Each job has to be processed by exactly one machine, <br>processing job $j$ on machine $i$ requires $p_{ij}$ time units, and the <br>objective is to minimize the makespan, i.e. the maximum job completion time. <br>We focus on the case when $m$ is fixed and develop a fully polynomial <br>approximation scheme whose running time depends only linearly on $n$. In the <br>second half of the paper we extend this result to a variant of the problem, <br>where processing job $j$ on machine $i$ also incurs a cost of $c_{ij}$, and <br>thus there are two optimization criteria: makespan and cost. We show that for <br>any fixed $m$, there is a fully polynomial approximation scheme that, given <br>values $T$ and $C$, computes for any fixed $\epsilon > 0$ a schedule in $O(n)$ <br>time with makespan at most $(1+\epsilon)T$ and cost at most $(1 + \epsilon)C$, <br>if there exists a schedule of makespan $T$ and cost $C$.},
TYPE = {Research Report / Max-Planck-Institut für Informatik},
}