An EPTAS for scheduling on unrelated machines of few different types (Q5919620)

The authors consider the scheduling problem with unrelated parallel machines with minimizing the makespan, where only a constant number of machine types \(K\) exists. This means that two machines are of the same type if all jobs have the same processing time on these machines. Since even this special case of the problem is already strongly NP-hard for \(K = 1\), the authors present an efficient polynomial time approximation scheme (EPTAS) for constant \(K\), i.e., for any \(\epsilon > 0\), a schedule with a length of at most (\(1 + \epsilon\)) times the optimal makespan can be found in polynomial time in the input length and the exponent is independent of \(1 / \epsilon\). The basic scheme is presented in Section 2 and in Section 3, the running time is improved by the use of techniques that utilize results concerning the existence of solutions for integer programming programs with a simple structure. In Sections 4--6, three further problems are studied which also allow the derivation of an EPTAS, namely the Santa Claus Problem, where the minimum machine load has to be maximized (Section 4), the problem with unrelated machines and a constant number \(K\) of uniform machine types (Section 5), and the \(D\)-dimensional unrelated vector scheduling problem, where both the dimension \(D\) and the number \(K\) of machine types are constant (Section 7). For the derivation of the EPTASs, mainly mixed integer programming and rounding techniques have been applied. Finally, some possible directions of further investigations are briefly discussed in Section 7.