de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Report

#### Improved approximation schemes for scheduling unrelated parallel machines

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44695

Jansen,  Klaus
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45212

Porkolab,  Lorant
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Locator
There are no locators available
##### Fulltext (public)

1998-1-026
(Any fulltext), 11KB

##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Jansen, K., & Porkolab, L.(1998). Improved approximation schemes for scheduling unrelated parallel machines (MPI-I-1998-1-026). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-7B69-4
##### Abstract
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$.