Premium
Coordination mechanisms for scheduling games with machine modification
Author(s) -
He Chaoyu,
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.12875
Subject(s) - job shop scheduling , computer science , scheduling (production processes) , price of anarchy , mathematical optimization , schedule , nash equilibrium , price of stability , mathematics , economics , monetary policy , monetary economics , operating system
This paper studies scheduling games with machine modification. A set of jobs is to be processed on a set of identical machines. An initial schedule before the modification of machines is given as a prior. Then some machines are removed and some new machines are added. Each job has the right either to stay on its original machine if the machine is not removed, or to move to another machine. The choices of all jobs after the machine modification constitute a new schedule. The individual cost of each job is its completion time, which is determined by the scheduling policy that the machines follow. We present properties of the Nash equilibriums under generalizations of the classical scheduling policies such as LPT, SPT and Makespan. For the social cost of minimizing the makespan, we establish the Price of Anarchy and Price of Stability of the games, and majorities of the parametric bounds are tight for each combination of the number of final machines, the number of added machines and the number of removed machines.