Mixed coordination mechanisms for scheduling games on hierarchical machines

Abstract

Abstract In this paper, we study scheduling games under mixed coordination mechanisms on hierarchical machines. The two scheduling policies involved are ‐ and ‐ , where ‐ (resp., ‐ ) policy sequences jobs in nondecreasing order of their hierarchies, and jobs of the same hierarchy in nonincreasing (resp., nondecreasing) order of their processing times. We first show the existence of a Nash equilibrium. Then we present the price of anarchy and the price of stability for the games with social costs of minimizing the makespan and maximizing the minimum machine load. All the bounds given in this paper are tight.