Algorithm Research For Some Map Reduce Scheduling Problems

While popularized by Google,MapReduce is a programming model and an associated implementation for processing and generating large data sets.This thesis mainly focuses on MapReduce parallel machine scheduling problems.On makespan minimization,the thesis considers the offline scheduling model on m uniform machines and online scheduling model on two uniform machines.On the minimum machine completion time maximization,the thesis studies the offline scheduling model on identical machines.The thesis contains five chapters.In chapter 1,we first introduce some basic concepts of the scheduling problem and MapReduce.In chapter 2,we mainly study offline MapReduce scheduling problem on m uniform machines where the map tasks are parallelized while the reduce tasks are non-parallelizable.Our goal is to minimize makespan.Both preemptive and non-preemptive reduce tasks are considered.For preemptive reduce tasks,we design an approximation algorithm with the worst case ratio of 2-(?),where s1?s2?…?sm and si is the speed of machine ?i.For non-preemptive reduce tasks,we give an approximation algorithm with worst case ratio of 2+(?).In chapter 3,we consider online MapReduce scheduling problem on two uniform ma-chines with makespan minimization.We first give the lower bounds for preemptive and non-preemptive reduce tasks.For preemptive reduce tasks,we present an optimal online algorithm with competitive ratio of(?),where s? 1 is the ratio between speeds of two machines.For non-preemptive reduce tasks,we show that the LS-like algorithm is optimal and its competitive ratio is 2s-1/s+1 if s<(?)and(s+1)/s if s?(?).In chapter 4,we study offline MapReduce scheduling problem on identical machines.The goal is to maximize the minimum machine completion time.For preemptive reduce tasks,we present an optimal algorithm for three parallel machines.For non-preemptive reduce tasks,we consider the cases of two machines,three machines and general m machines,and then design approximation algorithms whose tight worst case ratios are 4/3,3/2 and m,respectively.Finally,we suggest topics for future research.In chapter 5,we summarize our results and list some remarking conclusions,for the future study.