Online Scheduling On Two Hierarchical Uniform Machines And MapReduce Scheduling Problem

Scheduling problem, one of the important combinatorial optimization problems, has been widely used in management science, computer science and engineering technology, and many other fields. This thesis mainly investigates two kinds of scheduling problems: one is the online hierarchical scheduling problem on two uniform machines and the goal is to minimize the total completion time of all jobs, the other is MapReduce scheduling in flow shop, whose goal is to minimize the makespan.The thesis contains four chapters.In chapter 1, we introduce some basic concepts and theories of the scheduling problem and MapReduce.In chapter 2, we mainly consider the online hierarchical scheduling problem on two u-niform machines. The speed of the machine Mi is vi(i =1,2). Our goal is to minimize the total completion time of all jobs. Each job has a unit processing time and a hierarchy. The job with a lower hierarchy can only be processed on the first machine and the job with a higher hierarchy can be processed on any one of two machines. For the first case where v1= 1 and v2= s(s≥1), we show that the lower bound is at least 20/(?)≈1.299 and then present an optimal algorithm. For the second case where v1=s(s≥1) and v2=1, we also show that the lower bound is at least (?)/2≈1.372 and then present an optimal algorithm. Finally, we give some discussion.In chapter 3, we study MapReduce scheduling problem in flow shop. The goal is to minimize makespan. MapReduce processing essentially consists of two phases: the map phase and the reduce phase. Corresponding, each job is divided into two types of tasks: map tasks and reduce tasks. Map task is executed in the map phase and reduce task in reduce phase, and the reduce phase cannot begin until the map phase ends. Reduce task is non-preemptive. The first stage consists of m1 parallel machines and the second stage m2 parallel machines. Two variants of the problem are considered. If the Map task is non-preemptive, we give an approximation algorithm with worst-case ratio of 2 -1/m. If the Map task is fractional, we mainly discuss the case of p(Rj) = βp(Mj)(0<β<+∞). We give an approximation algorithm and prove its worst-case ratio is at most 2-1/m2-(1- m2)1/1+∞m1. Finally, we suggest topics for future research.In chapter 4, we summarize our results and list some remarking conclusions for the future study.