A PTAS for Scheduling Unrelated Machines of Few Different Types

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}$