Sorting Of Similar Machines In MapReduce Minimizes The Problem Of Maximum Completion Time

MapReduce is a popular batch data processing framework that enables massive amounts of such data to be organized and then analyzed on a distributed cluster of nodes preserving the principles of data locality and bringing computation closer to where the data resides.This paper mainly focuses on MapReduce uniform machine scheduling problems.For mini-mizing the maximum completed time on online scheduling.The structure of this article are following:In chapter 1,we first introduce some basic concepts of the scheduling problem and MapRe-duce.In chapter 2,we mainly study online MapReduce scheduling problem on h uniform ma-chines where the map tasks are parallelzable while the reduce tasks are non-parallelizable,the job sequence J = ?J1,J2,···} is released online over list.For a given job Ji,denote the set of its map tasks as Mi and that of reduce tasks as Ri,The information of Mi and Ri is not known until Ji is released.Therefore map tasks are processed firstly.Our goal is to minimize the maximum makespan.In this section,we assume that reduce tasks can be interrupted.For the preemptive condition,we design an approximation algorithm and also give the upper bound of the competitive ratio.In chapter 3,we study non-preemptive reduce tasks on h uniform machines,the job is released online over list.Our goal is to minimize the maximum makespan.The same as the chapter 2,map tasks are first considered,and reduce tasks are scheduling by LPT.For the non-preemptive condition,we design an approximation algorithm and also the upper bound of the competitive ratio is given.In chapter 4,we summarize the main contents of the paper and provide references for future efforts.