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

• 作者: 吴用 蒋义伟 魏麒
• 来源期刊: 高校应用数学学报A辑
• 学科: 数学
• 关键词: MapReduce 同类机 近似算法 Makespan
• 年，卷（期）: 2019,（1）
• 页码范围: 83-90
• 页数: 8页
• 分类号: O223
• 字数: 4153字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蒋义伟	浙江工商大学管理工程与电子商务学院	4	0	0.0	0.0
2	魏麒	宁波财经学院金融贸易学院	4	2	1.0	1.0
3	吴用	宁波财经学院金融贸易学院	2	0	0.0	0.0