Semi On-line Scheduling For Jobs With Similar Lengths

This thesis of Master is composed of three chapters. We mainly study two problems of semi on-line scheduling with the job length in [1,r] on m parallel machines. The first problem can be formally defined as follows. A sequence of jobs is to be scheduled on m parallel identical machines. In this semi on-line situation, the jobs's release times are normally non-decreasing. we study the competitive ratio of algorithm LS then obtain a better result. The second problem we study the situation a sequence of jobs is to be scheduled on m parallel uniform machines.In chapter 1, Introduces the background of the problem-researching and the recent development of the research in this field.besides. we give basic notion of competitive ration, algorithm LS, and so on.In chapter 2, we mainly study the competitive ration of algorithm LS from two different sides and we obtain some results.In chapter 3, we give a new algorithm for the second situation and prove the competitive ration.