Title: An EPTAS for Scheduling on Unrelated Machines of Few Different Types,
Abstract: In the classical problem of scheduling on unrelated parallel machines, a set
of jobs has to be assigned to a set of machines. The jobs have a processing
time depending on the machine and the goal is to minimize the makespan, that is
the maximum machine load. It is well known that this problem is NP-hard and
does not allow polynomial time approximation algorithms with approximation
guarantees smaller than $1.5$ unless P$=$NP. We consider the case that there
are only a constant number $K$ of machine types. Two machines have the same
type if all jobs have the same processing time for them. This variant of the
problem is strongly NP-hard already for $K=1$. We present an efficient
polynomial time approximation scheme (EPTAS) for the problem, that is, for any
$\varepsilon > 0$ an assignment with makespan of length at most
$(1+\varepsilon)$ times the optimum can be found in polynomial time in the
input length and the exponent is independent of $1/\varepsilon$. In particular
we achieve a running time of $2^{\mathcal{O}(K\log(K)
\frac{1}{\varepsilon}\log^4 \frac{1}{\varepsilon})}+\mathrm{poly}(|I|)$, where
$|I|$ denotes the input length. Furthermore, we study three other problem
variants and present an EPTAS for each of them: The Santa Claus problem, where
the minimum machine load has to be maximized; the case of scheduling on
unrelated parallel machines with a constant number of uniform types, where
machines of the same type behave like uniformly related machines; and the
multidimensional vector scheduling variant of the problem where both the
dimension and the number of machine types are constant. For the Santa Claus
problem we achieve the same running time. The results are achieved, using mixed
integer linear programming and rounding techniques.