Please wait a minute...
高校应用数学学报
高校应用数学学报  2017, Vol. 32 Issue (4): 473-486    
    
一个混合协调分配机制下自私调度问题的社会无序代价分析
魏麒1;2, 蒋天颖1
1. 宁波大红鹰学院金融贸易学院, 浙江宁波315100;
2. 上海大学数学系, 上海200444
Price of anarchy of a scheduling game with hybrid coordination mechanisms
WEI Qi1;2, JIANG Tian-ying1
1. School of Finance and Trade, Ningbo Dahongying University, Ningbo 315100, China;
2. Department of Mathematics, Shanghai University, Shanghai 200444, China
 全文: PDF 
摘要： 自私调度问题是一类应用于互联网和云计算的特殊调度问题. 不同于传统调 度问题, 它的每个工件是一个自私的参与者, 可以自主地选择一台机器加工以谋求自 身加工费用最小化. 针对机器可以自由选择WSPT机制或PS机制的混合协调分配机 制自私调度问题, 通过设计一个该问题的松弛线性规划, 然后写出该线性规划的对偶 规划. 比较上述两个规划的最优目标值, 以及该自私调度问题的最优社会费用和混 合Nash均衡解的最差社会费用这四个数值, 分析出该自私调度问题的混合社会无序代价为4.
关键词： 自私调度;  社会无序代价;  协调分配机制;  对偶规划    
Abstract: Scheduling game is a kind of special scheduling problem used in Internet and cloud computing. Different from the traditional scheduling problem, each job is controlled by a selfish agent and it is only interested in choosing one machine to minimize its own cost. A scheduling game with hybrid coordination mechanisms is considered. There are $n$ selfish jobs and $m$ unrelated machines. The machine can choose WSPT policy or PS policy, and the social cost is the total weighted completion times of all jobs. A linear programming relaxation for this problem is designed firstly. Then by discussing the relationship between the linear programming and its dual, the main conclusion is given: The mixed Price of Anarchy (MPoA) of this scheduling game is exactly 4.
Key words: scheduling game    price of anarchy    coordination mechanism    dual linear programming
收稿日期: 2016-07-26 出版日期: 2018-12-01
CLC:  O223  
基金资助: 国家自然科学基金(71372001); 浙江省教育厅一般科研项目(Y201636738); 大红鹰学院博士科研启动项目(1320169007)
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
魏麒
蒋天颖

引用本文:

魏麒, 蒋天颖. 一个混合协调分配机制下自私调度问题的社会无序代价分析[J]. 高校应用数学学报, 2017, 32(4): 473-486.

WEI Qi, JIANG Tian-ying. Price of anarchy of a scheduling game with hybrid coordination mechanisms. Applied Mathematics A Journal of Chinese Universities, 2017, 32(4): 473-486.

链接本文:

http://www.zjujournals.com/amjcua/CN/    或    http://www.zjujournals.com/amjcua/CN/Y2017/V32/I4/473

[1] 严羽洁. 单台机以总完工时间为目标的批排序问题[J]. 高校应用数学学报, 2017, 32(4): 462-472.