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.

Vorschau

Logo BII

Rechte

Nutzung und Vervielfältigung:

Keine Lizenz. Es gelten die Bestimmungen des deutschen Urheberrechts (UrhG).

Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.