| 两台自私型机器上自私工件排序的PoA紧界 |
| |
| 引用本文： | 成夏炎,何滢,赵聪聪,李荣珩. 两台自私型机器上自私工件排序的PoA紧界[J]. 运筹学学报, 2022, 26(3): 109-119. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.008 |
| |
| 作者姓名： | 成夏炎 何滢 赵聪聪 李荣珩 |
| |
| 作者单位： | 1. 湖南第一师范学院, 湖南长沙 4102052. 计算与随机数学教育部重点实验室, 湖南师范大学数学与统计学院, 湖南长沙 410081 |
| |
| 摘 要： | 本文研究了两台自私型机器上有自私型工件的关于二元均衡的排序问题。对任意工件序列$L$, 证明了二元均衡排序的PoA的紧界为$frac{8}{7}$。如果工件尺寸在区间$[1, r](rge1)$内, 得到了二元均衡排序的PoA的紧界为关于$r$的分段线性函数。
|
| 关 键 词： | 自私型机器 排序 紧界 纳什均衡 |
| 收稿时间： | 2022-01-28 |
Tight Price of Anarchy for selfish task scheduling on two selfish machines |
| |
| Affiliation: | 1. Hunan First Normal University, Changsha 410205, Hunan, China2. Key Laboratory of High Performance Computing and Stochastic Information Processing, Department of Mathematics, Hunan Normal University, Changsha 410081, Hunan, China |
| |
| Abstract: | In this paper, we study selfish task scheduling on two selfish machines with respect to Dual Equilibrium, called Dual Equilibrium Schedule. For any job list $L$, we show that the Price of Anarchy of Dual Equilibrium Schedule is $frac{8}{7}$. If the job sizes are constrained in $[1, r](rge1)$, this research states that the tight PoA(Price of Anarchy) of Dual Equilibrium Schedule is a piecewise linear function of $r$. |
| |
| Keywords: | selfish machines scheduling tight bound Nash equilibrium |
|
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载免费的PDF全文 |
|
