2014/05/11 by Arad, Dor, Mordechai, Yael, Shachnai, Hadas
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1405.2530
We consider the problem of scheduling n jobs to minimize the makespan on m unrelated machines, where job j requires time pij 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 ∈ (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/h < 2T. For the restricted version of the problem, where for each job j and machine i, pij ∈ \pj, ∞\, we show that a simpler algorithm yields a better bound, thus improving for highly feasible instances the best known ratio of 33/17 + ε, for any fixed ε>0, due to Svensson.