A Number Of Studies On Approximation Algorithm Of On Line Scheduling

Scheduling problem is one of the significant combinational optimization problems. It aims to use some resources, such as processors or machines and man powers, to complete a set of assignments or tasks optimally. On-line scheduling is one of the crucial branch of it. In this paper, we mainly deal with the on-line scheduling for jobs with release times on parallel machine. Several approximating algorithms are presented and also their performance ratios are analyzed. The thesis consists of three chapters.Chapter 1 briefly introduces some basic notions and recent results of com-binational optimization, scheduling problems and approximation algorithms, and so on.In chapter 2, we consider the scheduling problems of related machines and unrelated machines. On the basis of the algorithm presented by J.Aspnes et al, we take into account the case that the jobs have arbitrary release times and new algorithms are given. In the case of related machines, the performance ratio of the new algorithm is 12, which is a constant. In the case of unrelated machines, we give a new algorithm with performance ratio of O(logn).We analyzed a special condition in chapter 3:the jobs'release times are not decreasing and all of the processing times are unit 1. We showed that the LS algorithm is an optimal algorithm in this case.