|本期目录/Table of Contents|

[1]韩曙光,郑聪.三台同类机MapReduce排序问题的最优算法[J].浙江理工大学学报,2019,41-42(自科四):527-531.
　HAN Shuguang,ZHENG Cong.An optimal preemptive algorithm for MapReduce scheduling on three uniform machines[J].Journal of Zhejiang Sci-Tech University,2019,41-42(自科四):527-531.
点击复制

三台同类机MapReduce排序问题的最优算法()
分享到：

浙江理工大学学报[ISSN:1673-3851/CN:33-1338/TS]

卷:
第41-42卷
期数:
2019年自科四期
页码:
527-531
栏目:
出版日期:
2019-06-20

文章信息/Info

Title:
An optimal preemptive algorithm for MapReduce scheduling on three uniform machines
文章编号:
1673-3851 (2019) 07-0527-05
作者:
韩曙光; 郑聪
浙江理工大学理学院，杭州 310018
Author(s):
HAN Shuguang;  ZHENG Cong
School of Sciences, Zhejiang Sci-Tech University, Hangzhou 310018, China
关键词:
MapReduce; 同类机排序; 完工时间; 最优算法
分类号:
O233
文献标志码:
A
摘要:
研究MapReduce环境下的可中断同类平行机排序问题。在MapReduce环境中，每个工件含有两种类型的任务集，即Map任务集和Reduce任务集。在加工完工件的Map任务集后才能开始加工Reduce任务集中的任务。考虑Map任务为可分的情况，即Map任务可以任意分割为不同的小任务并能在不同机器上同时进行并行加工，而对于Reduce任务则考虑允许中断的情形，目标设为极小化最大完工时间。针对三台同类机的离线排序问题，通过分解所有实例的类型，给出了最优解算法。

参考文献/References:

［1］ Dean J, Ghemawant S. MapReduce: Simplified data processing on large clusters［J］. Communications of the ACM, 2008,51(1):107-113.
［2］ Isard M, Prabhakaran V, Currey J, et al. Quincy: Fair scheduling for distributed computing clusters［C］//Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles, New York：IEEE, 2009:261-276.
［3］ Gufler B, Augsten N, Reiser A, et al. Load balancing in mapreduce based on scalable cardinality estimates［C］//In Data Engineering (ICDE) 2012 IEEE 28th International Conference on, Italy：IEEE, 2012:522-533.
［4］ Bechini A, Marcelloni F, Segatori A. A MapReduce solution for associative classification of big data［J］. Information Sciences, 2015, 332:33-55.
［5］ Zhu Y, Jiang Y, Wu W, et al. Minimizing makespan and total completion time in MapReducelike systems［C］// In INFOCOM’14. IEEE, 2014:2166-2174.
［6］ Jiang Y, Zhu Y, Wu W, et al. Makespan minimization for MapReduce systems with different servers［J］. Future Generation Computer Systems, 2017, 67:13-21.
［7］ 周维. 若干MapReduce排序问题的算法研究［D］.杭州:浙江理工大学,2017:5-11.
［8］ Jiang Y, Zhou W, Zhou P. An optimal preemptive algorithm for online MapReduce scheduling on two parallelmachines［J］.AsiaPacific Journal of Operational Research,2018,35(3):1850013.
［9］ Luo T, Zhu Y, Wu W, et al. Online makespan minimization in MapReduce like systems with complex reduce tasks［J］. Optimization Letters,2017,11(2):271-277.
［10］ Chen C, Xu Y, Zhu Y, et al. Online MapReduce scheduling problem of minimizing the makespan［J］. Journal of Combinatorial Optimization, 2017,33(2):590-608.

相似文献/References:

[1]江绪宇,李仁旺,方旭斌,等.基于Hadoop的产品制造过程的碳足迹核算研究[J].浙江理工大学学报,2018,39-40(自科2):211.
　JIANG Xuyu,LI Renwang,FANG Xubin,et al.Research on the carbon footprint accounting of product manufacturing process based on Hadoop[J].Journal of Zhejiang Sci-Tech University,2018,39-40(自科四):211.

备注/Memo

备注/Memo:
收稿日期： 2018-09-18
网络出版日期： 2018-11-01
基金项目： 国家自然科学基金项目(11571013，11471286，11701518)
作者简介： 韩曙光(1977-)，男，江苏建湖人，副教授，博士，主要从事组合优化方面的研究
更新日期/Last Update: 2019-09-16