Online Scheduling Problems On M Uniform Machines

This thesis mainly concems online uniform machine scheduling problems. We firstintroduce basic notions of scheduling problem, approximation algorithms andcompetitive analysis.In Chapter 2, we investigate online covering problem on m uniform machines,the objective is to maximize the minimum load of m machines. We analyze theparametric lower bound for the problem and the parametric competition ratio for LS_salgorithm. We prove that LS_s is the best possible on-line algorithm for this problem.The parametric competitive ratio is sum from j=1 to m S_j.In Chapter 3, we fist investigate online scheduling problem on m uniform machines,the objective is to minimize the maximum machine completion time. We prove that theparametric competition ratio for LS_c algorithm for the general problem, i.e. the speedsof the machines are S₁, S₂,…, S_m (S₁≤S₂≤…≤S_m), is less than (?) (sum from j=1 to m S_j+S_m (m-k))/(sum from j=k to m S_j).Then we prove the parametric lower bound for the problem of three special machines,i.e. the speeds of the machines are 1,1, s (1＜s＜2), is...