Faster EPTAS for Scheduling on Uniform Machines
We present an efficient polynomial-time approximation scheme (EPTAS) for the problem of scheduling jobs on parallel uniform machines that improves all previously known EPTAS for the problem. Our algorithm uses a Mixed Integer Linear Program (MILP) formulation for a relaxed version of the problem. We simplify the MILP by repeatedly removing carefully selected sets of jobs and machines until all integer variables have been removed. Then, we build up the solution through the use of a dynamic programming approach, enumeration, and linear program solving. Notable about our approach is that our algorithm only uses an LP solver, different from previous EPTAS approaches where MILP solvers are necessary.
Preview
Rights
Use and reproduction:
No license. The provisions of the German Copyright Act (UrhG) apply.
Please note that individual components of the publication may be subject to other licensing or copyright conditions.
