Scheduling games on uniform machines with activation cost

作者：Xie, Fang^*; Xu, Zhe; Zhang, Yuzhong; Bai, Qingguo

来源：Theoretical Computer Science, 2015, 580: 28-35.

DOI：10.1016/j.tcs.2015.02.023

• Uniform machine scheduling
• Cost sharing games
• Price of Anarchy
• Price of Stability
• Nash Equilibrium

In this paper, we investigate job scheduling games on uniform machines. Activating each machine incurs an activation cost in accordance with its speed. Jobs are self-decision-making players choosing machines with the objective of minimizing their own individual cost. Here, a job's individual cost is defined as the load of its chosen machine plus its activation cost, which is proportionally shared with respect to its size. We first propose an algorithm when there are m kinds of unlimited number of uniform machines, and it is proved to be a Nash Equilibrium (NE) algorithm by using the induction method. Because of equilibria always being far from optimal solutions, the inefficiency of pure NE is measured with the social objective of minimizing the maximum individual cost. Assuming that the longest job is alpha times as large as the unit activation cost, together with alpha >= a(2), we obtain that both the Price of Anarchy (PoA) and Price of Stability (PoS) are equal to 1. Otherwise, they are bounded by (alpha + 1)/2 root alpha. Finally, we provide an example to illustrate the tight bound.

• 出版日期2015-5-17
• 单位北京航空航天大学; 华中科技大学; 曲阜师范大学