Operations Research Transactions ›› 2020, Vol. 24 ›› Issue (3): 57-66.doi: 10.15960/j.cnki.issn.1007-6093.2020.03.004

Previous Articles     Next Articles

Online MapReduce scheduling on two uniform machines

JIANG Xiaoyan, SHUAI Tianping*   

  1. School of Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China
  • Received:2018-01-17 Published:2020-09-05

Abstract: In this paper, we investigate a class of online over-list scheduling problem in MapReduce system. We are given two uniform machines, and a list of jobs arrive one by one, each job consists of one Map task and one Reduce task. The map task can be arbitrarily split and processed on both machines simultaneously, while the reduce task has to be processed on a single machine. After a job arrived, we should assign a(some) machine(s) to process its map and reduce task, which aims to minimize the makespan. We show that the classical LSc algorithm has competitive ratio $1+1/s$ when $s\geq (1+\sqrt{5})/2$ and $1+s/(s+1)$, otherwise. If the length of Map task is greater than or equal to the length of Reduce task for each job, then the competitive ratio is at most $1+1/(2s)$ when $s\geq (1+\sqrt{3})/2$ and $1+s/(2s+1)$ otherwise.

Key words: MapReduce, online scheduling, list scheduling, competitive ratio

CLC Number: