Tighter Bounds for Makespan Minimization on Unrelated Machines

We consider the problem of scheduling $n$ jobs to minimize the makespan on $m$ unrelated machines, where job $j$ requires time $p_{ij}$ if processed on machine $i$. A classic algorithm of Lenstra et al. yields the best known approximation ratio of $2$ for the problem. Improving this bound has been a prominent open problem for over two decades. In this paper we obtain a tighter bound for a wide subclass of instances which can be identified efficiently. Specifically, we define the feasibility factor of a given instance as the minimum fraction of machines on which each job can be processed. We show that there is a polynomial-time algorithm that, given values $L$ and $T$, and an instance having a sufficiently large feasibility factor $h\in (0,1]$, either proves that no schedule of mean machine completion time $L$ and makespan $T$ exists, or else finds a schedule of makespan at most $T+L\mathrm{/}h<2T$. For the restricted version of the problem, where for each job $j$ and machine $i$, $p_{ij}\in \{p_j,\mathrm{\infty }\}$, we show that a simpler algorithm yields a better bound, thus improving for highly feasible instances the best known ratio of $33\mathrm{/}17+ϵ$, for any fixed $ϵ>0$, due to Svensson.