A Study Of Scheduling Games And Related Scheduling Problems

Scheduling problem is one of the classical combinatorial optimization problems。 In the traditional scheduling models, jobs only are negatively assigned to machines and excluded from decision-makers. In recent years, many researchers consider jobs as selfish agents to choose machines arbitrarily and introduce game-theoretical ideas to analyze scheduling problem. The thesis, which mainly deals with scheduling games and related scheduling problems, consists of five chapters.In Chapter1, we present related basic concepts, preliminary knowledge, the main results of the thesis and some useful notations.Chapter2mainly investigates the machine covering game on two uniform ma-chines with makespan policy. we give the tight parametric bounds of POS and SPOS about the ratio between the speeds of two machines.In Chapter3, we study some scheduling games with parallel processing policy. Firstly, for parallel-machine environment we give a characterization of list schedule based on which we show the relationship between nash equilibrium and list schedule. Secondly, we give some analysis for the inefficiency of nash equilibrium. For m identical machines, we get the exact POS for the scheduling game with social cost as the maximum load over the machines, and the exact POA, POS for the machine covering game. For two related machines, we show the tight parametric bounds of POA about the ratio between the speeds of two machines for the scheduling game with social cost as the maximum load over the machines and the machine covering game, respectively.Chapter4presents a measure about schedules called equilibrium ratio problem and shows full analysis for three machine types and three process modes, we give the tight bounds of strong equilibrium ratio for all scheduling models, and the tight bound of weak equilibrium ratio when we consider the scheduling model with identical machines and the preemptive process mode or uniform machines and the fractional process mode. we also show that the lower bound and the upper bound of weak equilibrium ratio only have the difference between a constant multiple for other scheduling models.In Chapter5, we consider the scheduling problem on identical machines with the objective to minimize the maximum sum of completion times per machine. When the number of the machines is not a part of input, we present a Dynamic Programming based on which we construct a FPTAS. When the number of the machines is a part of input, we, who prove that the problem is strong NP-hard, improve the upper bound of the worst-case ratio of the classic SPT algorithm to313/120≈2.6083and present a better algorithm with the worst-case ratio equal to2.