On-line Scheduling On Uniform Parallel Machines

Scheduling problem is the classical combinatorial optimization problem, online scheduling is one of focal problems investigated in scheduling at present.This thesis mainly deals with some models which are jobs release time on uniform machines and algorithms competitive analysis.The thesis are made up of three chapters .In chapter 1 we give a brief introduction and basic notion of scheduling problem,competitive analysis,approximation algorithm.Summarize online models and their results which appear in recent years.chapter 2 investigates the online scheduling model for jobs with arbitrary release time and machines is a speed ofs_i = 1(1≤i≤m - 1),s_m = s > 1.The goal is to minimize the maximum machine completion time. In the chapter ,we mainlyconsider two problems : 1When m = 2,we present a tight bound of the performanceratio2 +(?). 2For the case of m uniform machines we follower as LS'algorithm andshow its competitive ratio is3 +(?).In chapter 3 we consider the online scheduling problems for jobs with arbitrary release time and machine is a speed ofs₁, s₂…s_m(s₁≤s₂≤…≤s_m),where the goal is to minimize the maximum machine completion time.We give new algorithm and prove the competitive ratio is count 20.