Parallel Machine Game Scheduling Problem With Activation Cost

This thesis mainly investigates the game scheduling problems on parallel machines with activation costs.The so called activation cost is machine-related cost which is due to machine activated.It has an effect on the structure of cost function and also influences on the player’s decision.Game scheduling is divided into machine game scheduling and job game scheduling.In the thesis,we consider the related model.The structure and main content of the thesis is organized as follows:In chapter 1,we clarify the main research background and research progress,and the main content and innovations.The first model(Chapter 2)is about the problem of machine scheduling games on two uniform machines with activation cost.We have obtained the price of anarchy(POA)and the strong price of anarchy(SPOA)as functions of the ratio between the speed of the two machines.The second model(Chapter 3)is about the problem of job scheduling games on unlimited uniform machines with activation cost.In this part,we have researched are that minimizing the sum of completion time among all jobs.We have designed an algorithm and testified it is a Nash Equilibrium.Certainliy,we also have an analysis for POA.