Scheduling MapReduce jobs on identical and unrelated processors

DOI10.1007/s00224-019-09956-6zbMath1446.68023OpenAlexW2991100652WikidataQ126641243 ScholiaQ126641243MaRDI QIDQ778521

Georgios Zois, Vasilis Vassalos, Dimitris Fotakis, Orestis Papadigenopoulos, Ioannis Milis

Publication date: 2 July 2020

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-019-09956-6

zbMATH Keywords

linear programmingheuristicsschedulingsimulationsprecedence constraintsapproximation algorithmsMapReduce

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Uses Software

• MapReduce
• Dryad
• Spark

Cites Work

• Unnamed Item
• An approximation algorithm for the generalized assignment problem
• Structure of a simple scheduling polyhedron
• Heuristics for scheduling unrelated parallel machines
• GYM: A Multiround Distributed Join Algorithm
• The Complexity of Flowshop and Jobshop Scheduling
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Hardness of Approximating Flow and Job Shop Scheduling Problems
• Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems
• Bounds on Multiprocessing Timing Anomalies
• The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders