A Parallel Approximation Algorithm for Scheduling Parallel Identical Machines
October 19, 2016
Track: ACM SRC
We propose a parallel approximation algorithm for the problem of scheduling jobs on parallel identical machines to minimize makespan, based on the best existing PTAS. This is the first practical parallel approximation algorithm for the problem that maintains the approximation guarantees of the sequential PTAS and it is designed for execution on shared-memory parallel machines.