Tighter Bounds for Makespan Minimization on Unrelated Machines

Dor Arad, Yael Mordechai, Hadas Shachnai

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 algor…