MapReduce系统中的两阶段混合流水作业调度算法

以极小化最大完工时间为目标,研究MapReduce系统中的两阶段混合流水作业调度问题.每个工件都包含两个任务集,即map任务集和reduce任务集.所有map任务必须在第一阶段的m1台平行机上加工,而reduce任务则必须在第二阶段的m2台平行机上加工.一个工件的reduce任务只有在该工件的所有map任务完成后才能开始加工.所有reduce任务不允许中断.对map任务不可中断情形,给出了一个最坏情况界为2-1/max{m1,m2}的近似算法.对map任务可任意分割情形,分别给出了基于Johnson规则和LPT规则的近似算法H(2,J)和H(2,L),并证明了这两个算法的最坏情况界分别为2-1/m2和2.通过数值实验发现,一般情况下H(2,J)性能要优于H2,L,但在reduce任务的总加工时间大于map任务且m2较大时则相反.最后,当map任务和reduce任务的总加工时间成比例关系时,给出了算法H(2,J)的参数最坏情况界.

Algorithms for two-stage hybrid flow shop in MapReduce systems

A two-stage hybrid flow-shop problem of minimizing makespan in MapReduce systems is considered. Each job consists of two sets of tasks, namely the map tasks and reduce tasks. All the map tasks must be processed on m₁ machines in the first stage, while all the reduce tasks must be processed on the other m₂ machines in the second stage. A job's reduce tasks can only be processed after all its map tasks are finished. All the reduce tasks are non-preemptive. For the variant where the map tasks are preemptive, we provide an approximation algorithm with a worst-case ratio of 2-1/max{m₁,m₂}. For the variant where the map tasks are fractional, we provide two approximation algorithms H_(2,J) and H_(2,J) based on Johnson rule and LPT rule, and show that the worst-case ratios of the two algorithms are 2-1/m₂ and 2, respectively. The computational experiments show that the performance of algorithm H_(2,J) is generally better than that of algorithm H_(2,J). However, it is the opposite when the total size of all the reduce tasks is greater than that of the map tasks and m₂ is large. Finally, we present a parametric worst-case ratio of algorithm H_(2,J) for a special case where the total processing time of the map tasks is proportional to that of the reduce tasks.