Abstract:

In this paper, we investigate game scheduling of jobs in two kinds of limited number of uniform machines with activation cost. The number of machines with speed 1 and activation cost B in the first category is limited. Similarly, the number of machines with speed a(>1) and activation cost aB in the second category is also limited.  Jobs are served as self-interested players who choose a machine with the objective of minimizing their individual cost without considering other players' cost and the total social cost. A job's cost is composed of its machine's load and its share in the machine's activation cost, which is proportionally shared with respect to its size. We design different algorithms for different cases. Then, every assignment obtained by each different algorithm is proved to be a Nash equilibrium.

Key words: game scheduling, Nash equilibrium, activation cost, proportional sharing rule