2016/02/17 by Dimitris Fotakis, Fotakis, Dimitris, Ioannis Milis +7
Computer Science · Engineering · Mathematics · #Algorithm #Approximation algorithm #Artificial intelligence #Cloud Computing and Resource Management #Computer science #Data Structures and Algorithms (cs.DS) #Execution time #FOS: Computer and information sciences #Heuristic #Job scheduler #Job shop scheduling #Mathematical optimization #Mathematics #Optimization and Search Problems #Parallel computing #Schedule #Scheduling (production processes) #Scheduling and Optimization Algorithms #Upper and lower bounds #cs.DS
paper · pdf · doi:10.48550/arxiv.1602.05263
published in arXiv (Cornell University) (Cornell University)
arxiv created 2016/02/17 · openalex publication_date 2016/02/17 · arxiv updated 2016/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider non-preemptive scheduling of MapReduce jobs with multiple tasks in the practical scenario where each job requires several map-reduce rounds. We seek to minimize the average weighted completion time and consider scheduling on identical and unrelated parallel processors. For identical processors, we present LP-based O(1)-approximation algorithms. For unrelated processors, the approximation ratio naturally depends on the maximum number of rounds of any job. Since the number of rounds per job in typical MapReduce algorithms is a small constant, our scheduling algorithms achieve a small approximation ratio in practice. For the single-round case, we substantially improve on previously best known approximation guarantees for both identical and unrelated processors. Moreover, we conduct an experimental analysis and compare the performance of our algorithms against a fast heuristic and a lower bound on the optimal solution, thus demonstrating their promising practical performance.