MapReduce同类机排序问题的改进算法

Improved algorithms for MapReduce scheduling on uniform machines

研究了MapReduce系统中极小化最大完工时间的同类机排序问题.每个工件包含两类任务集:Map任务集和Reduce任务集.工件的Reduce任务必须在该工件的所有Map任务完成后才能开始加工.Map任务是可分的,即可以被任意分割并在多台机器上同时加工,而Reduce任务是不可分的.针对m台同类机离线模型,分别考虑了Reduce任务可中断和不可中断两种情形.对于可中断情形,设计了一个近似比为2-■的近似算法,其中g_1≥1,s_i为机器σ_i的加工速度且s_1≥s_2≥…≥s_m;对于不可中断情形,则给出了一个近似比为2+3^(1/2)/3的近似算法.上述结果是对已有文献的改进.

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 tasks can only be processed after all its map tasks are finished. The map task is fractional, i.e., it can be arbitrarily split processed on di?erent 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-∑g1j=1sj/∑mj=1sj, where si is the speed of machine σi and s1 ≥ s2 ≥……≥sm.For the non-preemptive variant, we provide an approximation algorithm with a worst-case ratio of 2+√3/3. The result of the paper is an improvement over the previous work.