Studies Of Online Scheduling And Game Scheduling

Scheduling is an important branch of combinatorial optimization,and most of Scheduling problems are NP-H.Not only has it the typical charac-teristics of Combinatorics,but it is also closely related to some hot topics in relative fields.The solutions of them involve many interdisciplinary fields.So the research of Scheduling has important theoretical significance.With the de-velopment of computer science,many new models and research methods have arisen in this field.In the modern scheduling,a number of positive results of online scheduling and game scheduling have also achieved.This dissertation s-tudies these two kinds of scheduling problems on parallel machines.The whole dissertation is split into three chaptersIn Chapter 1,the problems of combinatorial optimization and schedul-ing are introduced briefly,especially online scheduling and game scheduling The related researchers' works of online scheduling and game scheduling are reviewed at the same time.In addition,the results of our research are sum-marized.In Chapter 2,online scheduling on uniform parallel machine,Qm|online,rj|Cmax(m? 2),which the jobs have release times and the ob-jective function is to minimize the maximum completion time,is discussed And the competitive ratio of LS algorithm is studied.When the number of uniform parallel machines is 2 and not less than 3,the tight bounds of com- petition ratio are shown as(?),4-4/m-1 respectively.Besides,a modified LS algorithm,which is abbreviated to HLS and better than LS algorithm,is given,and its competition ratio is analyzedIn Chapter 3,game scheduling on identical parallel machine,pm?Cmax(m?2),which the jobs and machines are selfish,is studied.Be-cause of selfishness,jobs and machines play games with each other according to their own objective functions in this model.When a stable equilibrium state of the games is formed,the decision-making of jobs and machines will not be changed.This state is called dual equilibrium,abbreviated as DE.We use the method of weight function to study the PoA which is the supremum of ratio between the maximum completion time in the DE schedule and optimal schedule.Firstly,we discuss the case of two machines,and show that 8/7 is its'tight PoA.In addition,the PoA with the jobs' similar length coefficient r is a piecewise function of r.Then,when the number of machines is 3?m?9,4/3 is the tight upper bound of PoA of DE.When m?10,7/5-9/5(5m-3)is the upper bound of PoA.Our results are better than the only existing result of 7/5.