Some Algorithm Researches For MapReduce Scheduling Problems

MapReduce framework is established as the standard computation framework for parallel processing of massive amounts of data.Scheduling in MapReduce environments has become an important research topic in scheduling theory and received a significant amount of attention during the last years.In this thesis,we extend the MapReduce online scheduling problem of Huang's work to two uniform machines and three identical machines.The problem we considered in this thesis can be described as follows.Given a set of machines and a list of jobs which is arrived one by one.Each job contains a set of map tasks and a set of reduce tasks,and the processing times of both Map and Reduce tasks become known to the decision maker once the job is revealed.A decision on the schedule of both map and reduce tasks has to be made immediately and irrecoverably on the release of the job.The Map task can be arbitrarily split and processed on some machines simultaneously while the reduce tasks are non-preemptive,all the Map tasks must finish before the execution of any Reduce tasks of the same job.The goal is to minimize the makespan,i.e.,the completion time of the last completed Reduce task.In chapter 2,we consider the problem on two uniform machines.We show that the classical LSc algorithm has competitive ratio (?) for general case and at most (?) when|Mj|?|Rj| holds for all jobs.At last,we show that there exists no online algorithm with competitive ratio less than 1+1/2s+2.In chapter 3,we study the problem with three identical machines.We proposed an optimal online algorithm(generalized List Scheduling)with competitive ratio 5/3 in general case,and 3/2 when |Mj|?|Rj|holds for all jobs j.At last,we summarize our results and list some further research directions in chapter 4.