SAVE THE DATE Tapia 2018 Orlando, FL September 19-22, 2018

2017 Tapia Conference

A Parallel Approximation Algorithm for Scheduling Parallel Identical Machines

Contributors

Presenter: Laleh Ghalami (Wayne State University)
Co-author: Daniel Grosu (Wayne State University)

Abstract

We present the design and analysis of a parallel approximation algorithm for the problem of scheduling jobs on parallel identical machines to minimize makespan. The design of the parallel approximation algorithm is based on the best existing polynomial-time approximation scheme (PTAS) for the problem. To the best of our knowledge, this is the first practical parallel approximation algorithm for the minimum makespan scheduling problem that maintains the approximation guarantees of the sequential PTAS and it is specifically designed for execution on shared-memory parallel machines. We implement and run the algorithm on a multi-core system and perform an extensive experimental analysis. The results show that our proposed parallel approximation algorithm achieves significant speedup with respect to both the sequential PTAS and the CPLEX-based solver that solve the integer program formulation of the problem.