Online makespan minimization in MapReduce-like systems with complex reduce tasks

被引：19

作者：

Luo, Taibo ^{[1
]}

Zhu, Yuqing ^{[2
]}

Wu, Weili ^{[3
,5
]}

Xu, Yinfeng ^{[1
]}

Du, Ding-Zhu ^{[4
,5
]}

机构：

[1] Sichuan Univ, Sch Business, Chengdu 610065, Peoples R China

[2] Calif State Univ Los Angeles, Dept Comp Sci, Los Angeles, CA 90032 USA

[3] Taiyuan Univ Technol, Taiyuan 030024, Shanxi, Peoples R China

[4] Ton Duc Thang Univ, Fac Informat Technol, Div Algorithms & Technol Networks Anal, Ho Chi Minh City, Vietnam

[5] Univ Texas Dallas, Richardson, TX 75080 USA

来源：

OPTIMIZATION LETTERS | 2017年 / 11卷 / 02期

基金：

中国国家自然科学基金;

关键词：

MapReduce; Big data; On-line scheduling;

D O I：

10.1007/s11590-015-0902-7

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In the MapReduce processing, since map tasks output key-value pairs, and reduce tasks take the pairs output by the map tasks and compute the final results. Therefore, reduce tasks are unknown until their map tasks are finished. Also, we assume that map tasks are preemptive and parallelizable, but reduce tasks are non-parallelizable. With these assumptions, we study the scheduling of minimizing makespan. Both preemptive and non-preemptive reduce tasks are considered. We prove that no matter if preemption is allowed or not, any algorithm has a competitive ratio at least 2-1/h, we then give two optimal algorithms for these two versions.

引用

页码：271 / 277

页数：7