Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959374 | European Journal of Operational Research | 2017 | 25 Pages |
Abstract
We study parallel-machine scheduling games with deteriorating jobs. The processing time of a job increases proportionally with its starting time by a positive deterioration rate. Each job acts selfishly aiming to minimize its completion time while choosing a machine on which it will be processed. Machines are equipped with coordination mechanisms to diminish chaos caused by jobs' competition. We consider three coordination mechanisms in this paper, namely Smallest Deterioration Rate first, Largest Deterioration Rate first and MAKESPAN policy. Under these mechanisms, we precisely quantify the inefficiency of their Nash Equilibriums by investigating the Price of Anarchy (PoA) and the Price of Stability (PoS), concerning minimization of social costs including the makespan and the total machine load. By using some new methods, we obtain parametrical bounds on the PoA and PoS, and demonstrate that most of these bounds are tight.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Qianqian Chen, Ling Lin, Zhiyi Tan, Yujie Yan,