Similar Machine Game Sorting Problem

Scheduling is an important branch of the combinatorial optimization theory.In tradi-tional scheduling problem,given a set of jobs and a set of machines,the decision makers always consider how to schedule all jobs on the machine well.This problem not only has high research value in theory,but also has wide application in reality practice.In this paper,we research the price of anarchy in game scheduling problems.In game scheduling problem,there is no central decision maker,each job can be seen as a selfish player,or each job has been possessed by an agent who pursues the maximum profit;the strategy set is a set of machines which can be chosen.The negative value of the job’s completion time is regarded as the utility function,the sum of all jobs completion time is regarded as the objective func-tion of the problem(the social cost).Since the Nash equilibrium solution may not be the optimal solution of this problem.Then,we studies the difference between the optimal solu-tion and the Nash equilibrium solution.Price of anarchy(PoA),it is usually to characterize the difference between the Nash equilibrium solution and optimal solution.Especially,the closer the PoA(price of anarchy)value is to 1 the closer the Nash equilibrium solution is to the optimal value.The first chapter of this paper is the preliminary knowledge and the background.In the second chapter,we study the 2 uniform parallel machines with LPT coordinate mechanism and n jobs game scheduling problem;we proved that the final stable solution of the game among agents is a Nash equilibrium solution and showed the upper bound of PoA is(?).Furthermore,we gave a lower bound of PoA by constructing a instance to prove it.In the third chapter,we generalized the problem in chapter 2 to the case where the number of machines is m,and proved the upper bound of PoA is(?)Similar to chapter 2,weshowed the lower bound of PoA is 3.