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

Algorithms for two-stage hybrid flow shop in MapReduce systems

作　　者：魏麒 吴用 蒋义伟 赵云 WEI Qi;WU Yong;JIANG Yiwei;ZHAO Yun(Ningbo University of Finance and Economics,Ningbo 315175,China;School of Management and E-Business,Zhejiang Gongshang University,Hangzhou 310018,China;School of Sciences,Zhejiang Sci-Tech University,Hangzhou 310018,China)

机构地区：[1]宁波财经学院,宁波315175 [2]浙江工商大学管理工程与电子商务学院,杭州310018 [3]浙江理工大学理学院,杭州310018

出　　处：《系统工程理论与实践》2020年第5期1255-1265,共11页Systems Engineering-Theory & Practice

基　　金：浙江省哲社规划课题成果(19NDJC093YB);国家自然科学基金(11571013,11871327);宁波市自然科学基金(2019A610048,2019A610095)。

摘　　要：以极小化最大完工时间为目标,研究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)的参数最坏情况界.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 m1 machines in the first stage,while all the reduce tasks must be processed on the other m2 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{m1,m2}.For the variant where the map tasks are fractional,we provide two approximation algorithms H(2,J) and H(2,L) based on Johnson rule and LPT rule,and show that the worst-case ratios of the two algorithms are 2-1/m2 and 2,respectively.The computational experiments show that the performance of algorithm H(2,J) is generally better than that of algorithm H(2,L).However,it is the opposite when the total size of all the reduce tasks is greater than that of the map tasks and m2 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.

关 键 词：MAPREDUCE 混合流水作业 近似算法 最坏情况界 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]