Scheduling unrelated parallel machines: Linear programming strikes back

In this paper we show how to improve a recent approximation scheme for scheduling jobs on a fixed number of unrelated parallel machines. Given a set of n jobs and a set of m processors with processing times p_{ij} of job j on processor i, the goal is to find a non-preemptive schedule with minimum or approximate makespan. The previous best algorithm by Fishkin and the authors runs in time O(n) + (log m/epsilon)^{O(m^2)}. By first preprocessing the input to obtain a reduced problem instance with at most min{ n, (log m/epsilon)^{O(m)} } jobs, and then by using dynamic and linear programming for different groups of jobs we are able to obtain an approximation scheme with running time O(n) + 2^{O(m log (m/epsilon))} \le O(n) + (log m/epsilon)^{O(m log m)}. If epsilon is relatively small (e.g. epsilon < 1/m), the running time of our scheme can be bounded by O(n) + (1/epsilon)^{O(m)} = O(n) + 2^{O(m log(1/epsilon))}