The Parallel Machine Game Scheduling Problem With Weight

In resource allocation applications, tasks are assigned to resources to be performed, for example, parallel machine scheduling. Recently, the analysis of operations research applications has applied game-theoretic concepts and tools, that is, game schedules.In this paper, we study three models of resource allocation game schedules: load-balancing game on identical machines, cost-sharing game involving resource activation costs on identical machines and load-balancing game on uniform machines. It is worth stressing that this is the first study about the three models, in which, each job has a weight and the objective function is the total weighted cost. The cost of a job is either the congestion time( defined as the load of the machine on which the job is scheduled) or the complex cost( composed of its machine’s load and its share in the machine’s activation cost).In contrast to a traditional scheduling problem in which a central authority makes scheduling decisions, a job now belongs to an player who decides which machine will process his/her job to minimize his/her own cost. In the long run, decisions of the players, usually result in a Nash equilibrium(NE) at which no individual player will benefit from any unilateral deviation for the current resource allocation. However, such an equilibrium is not necessarily, indeed can often be far from, optimal. It is important, therefore, to analyze the quality of NE solutions in terms of social optimality.We use the commonly accepted notions of the price of anarchy( PoA) and the price of stability( PoS) to analyze the quality of NE solutions. For each game problem, we analyze the quality of NE solutions and provide a parametric bound on the PoA and PoS.We denote the minimum and maximum weights, respectively, by minw and maxw. Then in the first model, we show ￡￡-+--PoSnmnm1)1()1(2min1wPoA ￡. In the second model, we show ( )2121 wPoSPoA+￡￡￡r, in which,min maxwww =,min1pr=. In the third model, we show that ÷???è?+￡ 1mnPoAm, in which,min maxwww =, 1s andmsare respectiely the minimum and maximum machine speeds.