科研之友
微信
新浪微博
Facebook
分享链接
摘要
以极小化最大完工时间为目标,研究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))的参数最坏情况界.
- 单位
