The Analysis Of The LS Algorithm For Jobs With Release Times

Scheduling is an important branch of combinatorial optimization problems, which uses some processors, machines or resources to accomplish optimally a batch of given tasks or jobs. It has been extensively applied in the fields of manufacture management and allocation, network communication, theorems of computer science and so on. This thesis is mainly on the analysis of the List Scheduling(LS) algorithm for jobs with release times on m identical parallel machines. The objective function is to minimize the makespan. Three chapters are included in this thesis. In chapter one some definitions, notations and basic information about the competitive performance of algorithm are briefly introduced and the characteristics of model of on-line (Semi-on-line)scheduling for jobs with release times are described. In the second chapter, a much more simple proof is given for the tight performance ratio of the LS algorithm when the release times is a non-decreasing sequence. In chapter three, the LS algorithm is analyzed for the semi-online scheduling model in which the jobs' processing times is non-increasing order. Two resultsare given. Firstly it is shown that R(m,LS)≤(?)whenr₁≤r₂≤…≤r_n. Secondly it is shown that R(m, LS)≤2 if the release times are arbitrary.