Online Hierarchical Scheduling On Parallel Machines To Minimizie The Total Completion Time

Scheduling problem is a very active branch in the field of operations research.It is widely used in many fields,such as computer science,management science and engineering technology.This thesis studies the online hierarchical scheduling on parallel machines with objective of minimizing the total completion time The first chapter briefly introduces the basic theory of scheduling and the hierarchical scheduling problem.The second chapter studies online hierarchical scheduling on parallel machines where has two hierarchies.Each job has a unit processing time and a hierarchy of 1 or alternatively2.The job with hierarchy of 1 can only be processed on the machine with hierarchy 1 and the job with hierarchy 2 can be processed on any one of machines.The objective is to minimize the total completion time.For the case where the first machine has a hierarchy of 1 and the remainder machines have a hierarchy of 2,we present an online algorithm with competitive ratio of ,which is better than the previous result.For the case where the first machines have a hierarchy of 1 and the remainder machines have a hierarchy of 2,we provide a lower bound The third chapter studies the online hierarchical scheduling problem on three parallel identical machines with two hierarchies.For the case where one machine with hierarchy 1and two machines with hierarchy 2,we present an optimal online algorithm with competitive ratio of 17/14.For the case where two machines with hierarchy 1 and one machine with hierarchy 2,we present an optimal online algorithm with competitive ratio of 43/36.The fourth chapter gives the concluding remark and suggests several topics for future research.