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

摘要：

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

关键词：MapReduce、同类机、近似算法、Makespan

所属期刊栏目：34

分类号：O223(运筹学)

资助基金：浙江省哲学社会科学规划课题19NDJC093YB;浙江省自然科学基金LY19A010002;国家自然科学基金11571013

在线出版日期：2019-04-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：83-90