b'@techreport{JansenPorkolab98-1-026,'b'\nTITLE = {Improved approximation schemes for scheduling unrelated parallel machines},\nAUTHOR = {Jansen, Klaus and Porkolab, Lorant},\nLANGUAGE = {eng},\nURL = {http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-026},\nNUMBER = {MPI-I-1998-1-026},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {1998},\nDATE = {1998},\nABSTRACT = {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$.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'