Inefficiency analysis of the scheduling game on limited identical machines with activation costs

作者:Xie, F (Xie, Fang)^{[ 1 ]} ; Zhang, YZ (Zhang, Yuzhong)^{[ 2 ]} ; Bai, QG (Bai, Qingguo)^{[ 3 ]} ; Xu, Z (Xu, Zhe)^{[ 1 ]} 

We investigate the scheduling game on a fixed number m of identical machines that no machines are initially activated and each machine activated incurs the same activation cost. Every job, as a selfish player, is interested in minimizing its own individual cost composing of both the load of its chosen machine and its share in the machine's activation cost, whereas the social cost focuses on the sum of makespan and total activation cost. The inefficiency of pure Nash equilibria is assessed by the Price of Anarchy (PoA) and Price of Statibility (PoS). First, when the jobs' total length is no larger than a single machine's activation cost, we demonstrate that m is the tightness upper bound of PoA and PoS equals to 1. Then, for the case that the total length is large, we prove that the PoA is tightly bounded by (m + 1)/2. Finally, a lower bound of the PoS is also given. (C) 2015 Elsevier B.V. All rights reserved.