期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 263, 期 2, 页码 380-389出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2017.05.021
关键词
Scheduling; Parallel machines; Nash Equilibrium; Price of Anarchy; Deteriorating jobs
资金
- Department of Education of Zhejiang Province of China [Y201533189]
- National Natural Science Foundation of China [11671356, 11271324, 11471286]
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. (C) 2017 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据