# MPI-I-98-1-026

## 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$.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 241 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: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-026

**BibTeX**
`@TECHREPORT{``JansenPorkolab98-1-026``,`

` 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},`

`}`