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.
[1] Benchini A, Marcelloni F, Segatori A. A MapReduce solution for associative classification of big data[J]. Information Sciences, 2015, 332:33-35.
[2] Kolb L, Thor A, Rahm E. Load balancing for MapReduce-based entity resolution[C]//Proceeding of the 28th International Conference onData Engineering(ICDE), 2012:618-629.
[3] Chen C, Xu Y, Zhu Y, et al. Online MapReduce scheduling problem of minimizing the makespan[J]. Journal of Combinatorial Optimization, 2017, 33:590-608.
[4] Huang J, Zheng F, Xu Y, et al. Online MapReduce processing on two identical parallel machines[J]. Journal of Combinatorial Optimization, 2018, 35(1):216-223.
[5] Zaharia M, Konwinski A, Joseph A, et al. Improving MapReduce performance in heterogeneous environments[C]//Proceeding of the 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI 08), 2008, 29-42.
[6] Moseley B, Dasgupta A, Kumar R, et al. On scheduling in MapReduce and flow-shops[C]//Proceedings of the twenty-third annual ACM symposium on parallelism in algorithms and architectures, 2011, 11:289-298.
[7] Luo T, Zhu Y, Wu W, et al. Onlinemakespan minimization in MapReduce-like systems withcomplex reduce tasks[J]. Optimization Letter,2017, 11:271-277.
[8] Zhu Y, Jiang Y, Wu W, et al. Minimizingmakespan and total completiontime in MapReducelike systems[C]//INFOCOM, IEEE, 2014, 2166-2174.
[9] Wang J, Li X. Task scheduling for MapReduce in heterogeneous networks[J]. Cluster Computing, 2016, 19(1):197-210.
[10] Jiang Y, Zhu Y, Wu W, et al. Makespan minimization for MapReduce systems with different severs[J]. Future Generation Computer Systems, 2017, 67:13-21.
[11] Epstein L, Noga J, Seiden S, et al. Woeginger G.Randomized on-line scheduling on two uniform machines[J]. Journal of Scheduling, 2001, 4(2):71-92.
