A PTAS for Scheduling Unrelated Machines of Few Different Types

to full text (882 kB)   ZIP
involved person(s) / institution(s)author :
datePublished :
  • June 2015
size31 S.

Scheduling on Unrelated Machines is a classical optimization problem where $n$ jobs have to be distributed to $m$ machines. Each of the jobs $j \in \{1, \ldots, n\}$ has on machine $i \in \{1, \ldots, m\}$ a processing time $p_{ij} \geq 0$. The goal is to minimize the makespan, i.e.\ the maximum completion time of the longest-running machine. Unless $P = NP$, this problem does not allow for a
polynomial-time approximation algorithm with a ratio better than $\frac{3}{2}$. A natural scenario is however that many machines are of the same type, like a CPU and GPU cluster: for each of the $K$ machine types, the machines $i \neq i'$ of the same type $k$ satisfy $p_{ij} = p_{i'j}$ for all jobs $j$. For the case where the number $K$ of machine types is constant, this paper presents an approximation scheme, i.e.\ an algorithm of approximation ratio $1+\varepsilon$ for $\varepsilon > 0$, with an improved running time only
single exponential in $\frac{1}{\varepsilon}$.
Static URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000271
IDNumber of report :
  • TR_1506