Premium
Mixed coordination mechanisms for scheduling games on hierarchical machines
Author(s) -
Chen Qianqian,
Tan Zhiyi
Publication year - 2021
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12558
Subject(s) - price of anarchy , scheduling (production processes) , nash equilibrium , computer science , hierarchy , price of stability , job shop scheduling , mathematical optimization , coordination game , mathematical economics , distributed computing , mathematics , economics , computer network , routing (electronic design automation) , market economy , monetary policy , monetary economics
In this paper, we study scheduling games under mixed coordination mechanisms on hierarchical machines. The two scheduling policies involved are L G ‐ L P T and L G ‐ S P T , where L G ‐ L P T (resp., L G ‐ S P T ) 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.