Large Bounds For Jobs With Similar Processing Times Using The LPT-algorithm

In this thesis,we mainly discuss the off-line scheduling problem for jobs with similar processing time and the jobs are ordered in nonincresing processing time on two parallel and identical machines.The objective function is to minimize the maximam completion time of all machines.The worst performance ratio of the LPT algorithm is analysed.For the jobs with similar and nonincressing processing time,we prove that the worst performance ratio of LPT algorithm is(?)When 11/8 ≤ r≤3/2,we get the same performance with[1].When r<11/8,we get the worst performance smaller than[1]and it is tight.In Chapter 1,we introduce some preliminary knowledge and basic con-cept,including combinatorial optimization problem,approximation algorithm,scheduling problem,LS and LPT algorithm.In Chapter 2,we prove the worst performance ratio of LPT algorithm for 2 identical machine on which jobs have similar and nonincreasing processing time.In Chapter 3,we summarize the whole thesis and give some suggestions for the future work.