An Optimal Preemptive Algorithm for Online MapReduce Scheduling on Two Parallel Machines

Yiwei Jiang, Wei Zhou () and Ping Zhou ()
Additional contact information
Yiwei Jiang: School of Management and E-Business, Contemporary Business and Trade Research Center, Zhejiang Gongshang University, Hangzhou 310018, P. R. China
Wei Zhou: Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou 310018, P. R. China
Ping Zhou: College of Humanities, Zhejiang Business College, Hangzhou 310053, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2018, vol. 35, issue 03, 1-11

Abstract: In this paper, we study an online scheduling on two parallel machines in MapReduce-like system where each job contains two kinds of tasks: map tasks and reduce tasks. A job’s reduce tasks can only be processed after all its map tasks are finished. We assume that the map tasks are fractional and the reduce tasks are preemptive. Our objective is to minimize makespan. We show that the lower bound for this MapReduce scheduling problem is 2. We then present an online algorithm with competitive ratio of 2 and thus it is optimal.

Keywords: MapReduce; online algorithm; competitive ratio; makespan (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595918500136
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:35:y:2018:i:03:n:s0217595918500136

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595918500136

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().