A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach

TLDR

The problem is to schedule independent jobs on uniform processors of varying speeds to minimize the makespan. The authors propose a polynomial approximation scheme for minimizing makespan on uniform parallel processors. They use a dual approximation approach that transforms infeasible superoptimal dual solutions into feasible, near‑optimal schedules. The scheme achieves any desired ε‑relative error in polynomial time, improving the previous 40 % bound.

Abstract

We present a polynomial approximation scheme for the minimum makespan problem on uniform parallel processors. More specifically, the problem is to find a schedule for a set of independent jobs on a collection of machines of different speeds so that the last job to finish is completed as quickly as possible. We give a family of polynomial-time algorithms $\{ {A_\varepsilon } \}$ such that $A_\varepsilon $ delivers a solution that is within a relative error $\varepsilon $ of the optimum. This is a dramatic improvement over previously known algorithms; the best performance guarantee previously proved for a polynomial-time algorithm ensured a relative error no more than 40 percent. The technique employed is the dual approximation approach, where infeasible but superoptimal solutions for a related (dual) problem are converted to the desired feasible but possibly suboptimal solution.