Two Types Of MapReduce Job Sorting Problems In The Same Order

With the advent of the era of big data,the storage unit has risen from the common TB to NB,one NB is 2⁶⁰TB.At the time of the soaring commercial value of big data,big data mining,analysis,data security,storage and other issues have brought huge challenges to the performance of computer system.The emergence of Map Reduce system has brought the possibility of rapid processing of big data,which is a large-scale module oriented.Ac-cording to the parallel operation model and methods of processing,this paper studies the problems of minimizing the maximum completion time of Map Reduce in the same sequence job scheduling.The first chapter introduces the basic knowledge of classical scheduling problems and Map Reduce programming models.In the second chapter,we study the scheduling problem of F₂|MapReduce|C_max with the Map Reduce framework.Here,the job is composed of map task and reduce task.Map task can be processed in parallel while the reduce task can not be processed in parallel.The reduce task of each job is divided into m processes,which are processed on m machines with the same speed.Each process must wait until the end of the previous process,and the first process must wait until it's map task is finished.Firstly,when m=2,if the map task is larger than the reduce task,the problem is polynomial time solvable,and the MRJ algorithm is the optimal algorithm.The third chapter is mainly about the analysis when the reduce task processing process is more than two processes.When the processing time of the map task is 0,the problem is reduced to a polynomial problem which is F_m||C_max.In the classical scheduling problem,is NP-hard,so it's easy to know the problem of F_m|MapReduce|C_max is NP-hard.From the analysis,the worst-case bound of MRA algorithm for the problem F_m|MapReduce|C_max is 2-1/m,the bound is tight,the m is number of the machines.The fourth chapter summarizes the problems in this paper and looks forward to the future of the research work.