On-line Scheduling For Jobs With Arbitrary Release Times On Uniform Machines

In this thesis,we consider online scheduling for jobs with non-decreasing and arbitrary release times on the parallel uniform machine system.In the first part:Cho and Sahni(1980)are the first to consider the on-line scheduling problem on m uniform machines.They showed that the LS algorithm for Qm/online/Cmax(m≥2)has competitive ratio not greater than(?).When si=1(i=1,2,…,…,m-1)and Sm=s>1,they proved that the algorithm LS has a competitive ratio 1+m-1/m+s-1min{s,2}≤3-4/m+1 and the bound 3-4/m+1 is achieved when s=2(m≥3).Aspnes et al.(1997)are the first to try to design algorithms better than LS for Qm/online/Cmax.They presented a new algorithm that achieves the competitive ratio of 8 for the deterministic version,and 5.436 for its randomized variant.Later the previous competitive ratios are improved to 5.828 and 4.311,respectively,by Berman et al.(2000).In this paper,we add a new constraint that the release time of jobs are non-decreasing.Compared with the previous model,our model is more complicated.We should consider more factors in the analysis of performance ratio.The worst performance ratio of U algorithm isThe second part:on the basis above,we take the jobs with non-decreasing release time instead of jobs with arbitrary release time and show that the worst performance ratio of U algorithm is:Although the result is bigger than that of before,the application scope is more extensive.The detailed proof is given in chapter 3.In Chapter 1 we introduce some basic knowledge about combinatorial op-timization problem,approximation algorithms and the progress of scheduling problem.In Chapter 4 we summarize the whole thesis and give some suggestions for the future work.