| This paper mainly studies uniform machine scheduling problems,and the objective function is to maximize the minimum finishing time.This problem can also be called machine covering problem.In this paper we mainly focus on this kind of problem that only one of these machines has processing speed which is different from the others.The algorithm that we study is the famous off line algorithm LPT.This algorithm first sort all the jobs with non increasing job size,then process the jobs one by one on the machine that cun'ently have minimum load.In chapter 1,we first introduce basic notions of scheduling problem,approximation algorithms and competitive analysis.In chapter 2,we mainly study 3 uniform machines scheduling problems with processing speeds of 1,1,s and 1,s,s with s＞1,and we prove the LPT algorithm's parametric worst case ratio and give the tight bound with s in some range.Further more,we have the constant tight bounds of both problems.In chapter 3,we investigate scheduling problems with m uniform machines,where we have processing speeds of 1,1,...,s(s＞1).We prove that this problem the tight bound with s in some range when m≥4. |
