Preemptive Algorithms For Scheduling Under A Grade Of Service

This thesis mainly study preemptive algorithms for scheduling under a grade of service. It consists of three chapters.In Chapter 1, we introduces some notation and preliminary for parallel machines scheduling problem.In Chapter 2, we investigate the preemptive offline algorithms for scheduling under a grade of service. First we study the preemptive off-line algorithm for scheduling on m identical machines. We give an optimal algorithm within O(n). Then we study the preemptive offline scheduling on two uniform machines. And an optimal algorithm with the time complexity O(n~2) is given. For preemptive offline scheduling on two identical machines, as a special case of the problem, we also give an optimal algorithm for preemptive offline scheduling on two identical machines.In Chapter 3, we consider the preemptive online algorithms for scheduling under a grade of service. We mainly study the problems for two identical machines and two uniform machines. In these problems, we could not violate a basic service rule of "first-come-first serve" . For two identical machines, we give an optimal online algorithm whose competitive ratio is 3/2. For two uniform machines, two cases are considered. One is the machine with higher grade has bigger speed, the other is the machine with higher grade has smaller speed. For the first case, we give an optimal algorithm. For the other, we give an approximation algorithm, the gap between its competitive ratio and the lower bound of the problem is 0.2228 at most.