一个混合协调分配机制下自私调度问题的社会无序代价分析  

Price of anarchy of a scheduling game with hybrid coordination mechanisms

作　　者：魏麒 蒋天颖[1] WEI Qi;JIANG Tian-ying(School of Finance and Trade, Ningbo Dahongying University, Ningbo 315100, China;Department of Mathematics, Shanghai University, Shanghai 200444, China)

机构地区：[1]宁波大红鹰学院金融贸易学院,浙江宁波315100 [2]上海大学数学系,上海200444

出　　处：《高校应用数学学报（A辑）》2017年第4期473-486,共14页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金(71372001);浙江省教育厅一般科研项目(Y201636738);大红鹰学院博士科研启动项目(1320169007)

摘　　要：自私调度问题是一类应用于互联网和云计算的特殊调度问题.不同于传统调度问题,它的每个工件是一个自私的参与者,可以自主地选择一台机器加工以谋求自身加工费用最小化.针对机器可以自由选择WSPT机制或PS机制的混合协调分配机制自私调度问题,通过设计一个该问题的松弛线性规划,然后写出该线性规划的对偶规划.比较上述两个规划的最优目标值,以及该自私调度问题的最优社会费用和混合Nash均衡解的最差社会费用这四个数值,分析出该自私调度问题的混合社会无序代价为4.Scheduling game is a kind of special scheduling problem used in Internet and cloud computing.Di?erent from the traditional scheduling problem,each job is controlled by a selˉsh 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 selˉsh 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ˉrstly.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 exactly4.

关 键 词：自私调度 社会无序代价 协调分配机制 对偶规划 

分 类 号：O223[理学—运筹学与控制论]