Finite Resource Game Ranking Problem With Constant Speed Machine With Activation Cost

In this paper, we investigate job scheduling games on uniform machines with activation cost in limited resources. The initial state of each machine is not activated. And activating each machine incurs an activation cost. There is no central controller and each job is treated as a game player. They will choose machines with the objective of minimizing their individual cost which is the load on its chosen machine plus its share in the machine’s activation cost. We use theprice of anarchy (POA) to measure the quality of Nash Equilibrium (NE). In this paper, we take synthetically limited uniform machines and activation cost into account, then respectively investigate different objective function of job scheduling games on two and m uniform machines with activation cost.The first chapter mainly introduces the background, related theoretical knowledge and the development of the scheduling problem, game theory and game scheduling. Then we summarize the main work and the innovations of this paper in brief.In the second chapter, we mainly consider a model, Q2(·), B=1,a|ut=Cj|n∑i=1Cj,of job scheduling games on two uniform machines with activation cost. In the model, the speed of two machines are 1 and a, respectively. And activating each machine incurs an activation cost B, which is equal to its speed. The social cost n∑Cj is the sum of all the jobs’individual cost C and the objective is to minimize the social cost. We obtain the upper bound a+1 of POA according to the analysis of the POA, then prove it and provide an example to illustrate the low bound a-1.In the third chapter, we mainly consider two models,i.e. Qm(·),B=1|ut=-Cj|n∑j=1Cj and Qm(·),B=1|ut=-Cj|Cmax, of job scheduling games on m uniform machines with the same activation cost. In these models, there are m machines with different speed. The speed of the machine M, is a. and we assume a1<a2<…<am and a1=1. P is the sum of all the jobs’ processing time.The activation cost B of each machine is 1.In the first model, the social cost n∑Cj is the sum of all the jobs’individual cost Cj and the objective is to minimize the social cost. According to the analysis of the POA, we obtain the upper bound m∑i=1ai; In the second model, the social cost Cmax is the maximum job’s individual cost and the objective is to minimize the social cost. According to the analysis of the POA, we obtain the upper bound n∑i=1ai(1+1/P).In the fourth chapter,we mainly consider a model,Qm(·),B=ai|ut=-Cj|Cmax,of job scheduling games on m uniform machines with the different activation cost.In the model,there are m machines with different speed.The speed,which is equal to its activation cost B,of the machine Mi is ai and we assume a1<a2<…<am and a1=1.The socCial cost Cmax is the maximum job’s individual cost C, and the objective is to minimize the social cost.According to the analysis of the POA,we obtaIn the upper bound n∑i=1ai(1+am/p).