short PTAS) have been studied for makespan minimization. A PTAS for a minimization problem is a family of algorithms $(A_\epsilon)_{\epsilon>0}$ such that for every fixed $\epsilon >0$ and for every instance $I$ with optimal value $OPT_I$ the algorithm $A_\epsilon$ yields a solution of at most value $(1+\epsilon) OPT_I$ in a running time polynomial in the size of the input $|I|$. We call $(A_\epsilon)_{\epsilon>0}$ efficient PTAS (EPTAS) if it has a running time of the form $f(\frac{1}{\epsilon})* |I|^c$ for some $c\in O(1)$ and a not necessarily polynomial function $f$. Finally if the running time is fully polynomial in $|I|$ and $\frac{1}{\epsilon}$ we call $(A_\epsilon)_\epsilon$ fully PTAS (FPTAS).

For the classical makespan minimization problem it is known that the problem is strongly NP-hard and there are known PTAS’s [@schedptas; @schedptasimpro] and furthermore EPTAS’s [@jeptas1; @jeptas2]. One known generalization of the machine scheduling problem is to change the model of machines. In the unrelated machines model, the height or processing time of jobs also depends on the machine it is running on. For this variant there are known $2$-approximations by Lenstra, Shmoys and Tardos [@unrelated1] and an improvement with a $2-\frac{1}{m}$- approximation by Shchepin and Vakhania [@unrelated2]. Also a lower bound of $\frac{3}{2}$ 