×

Improved algorithms for MapReduce scheduling on uniform machines. (Chinese. English summary) Zbl 1438.90122

Summary: This paper considers makespan minimization scheduling on uniform machines in MapReduce system. Each job consists of two sets of tasks: namely map tasks set and reduce tasks set. A job’s reduce task can only be processed after all its map tasks are finished. The map task is fractional, i.e., it can be arbitrarily divided on different machines in parallel, while the reduce task is not fractional. We consider two variants of the problem: namely preemptive and non-preemptive reduce tasks. For the preemptive variant, we provide an approximation algorithm with a worst-case ratio of \(2 - \frac{{{s_1}}}{{\Sigma_{j = 1}^m{s_j}}}\), where \(s_i\) is the speed of machine \({\sigma_i}\) and \({s_1} \ge {s_2} \ge \dots \ge {s_m}\). For the non-preemptive variant, we provide an approximation algorithm with a worst-case ratio of \(2 + \frac{{\sqrt 3}}{3}\). The result of the paper is an improvement over the previous work.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite