An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables

Abstract

We present an efficient polynomial time approximation scheme (EPTAS) for scheduling on uniform processors, i.e., finding a minimum length schedule for a set of n independent jobs on m processors with different speeds (a fundamental NP-hard scheduling problem). The previous best polynomial time approximation scheme (PTAS) by Hochbaum and Shmoys has a running time of $(n/\epsilon)^{O(1/\epsilon^2)}$. Our algorithm, based on a new mixed integer linear program (MILP) formulation with a constant number of integral variables and an interesting rounding method, finds a schedule whose length is within a relative error $\epsilon$ of the optimum and has a running time of $2^{O(1/\epsilon^2\log(1/\epsilon)^3)}+poly(n)$.