A PTAS for Scheduling Unrelated Machines of Few Different Types

Abstract

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} \ge 0$. The goal is to minimize the makespan, i.e. the maximum completion time of the longest-running machine. Unless $\mathrm {P}= \mathrm {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 \ne 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 }$.

Research supported by DFG project JA612/14-2, “Entwicklung und Analyse von effizienten polynomiellen Approximationsschemata für Scheduling- und verwandte Optimierungsprobleme”.