摘要
研究以最小化最大加权完工时间为目标的排序博弈问题的协调机制。相应的排序博弈模型中,有m台平行机和n个工件,工件j的加工时间为pj,权重为ωj。每个工件可自主选择机器进行加工,它的目标是最小化自身的完工时间,全局的目标是最小化最大加权完工时间。本文针对该问题设计协调机制,证明该机制的纳什均衡存在且唯一,并证明该机制的无秩序代价为2-1/m。
In this paper a scheduling game to minimize the maximum weighted completion time is considered.There are mparallel machines and njobs.The processing time of job jis pj,and its weight isωj.Each job's individual cost is its completion time.The social cost is the largest weighted completion time.A coordination mechanism for the scheduling game problem is designed.The existence and the uniqueness of Nash Equilibrium of the scheduling game is showed.It is also showed that the price of anarchy of the coordination mechanism is 2-1/m.
出处
《中国海洋大学学报(自然科学版)》
CAS
CSCD
北大核心
2015年第7期137-140,共4页
Periodical of Ocean University of China
基金
国家自然科学基金项目(11201439
11271341)
教育部博士点专项基金新教师基金项目(20120132120001)
山东省自然科学基金青年基金项目(ZR2012AQ12)资助
关键词
排序
博弈
协调机制
纳什均衡
无秩序代价
scheduling
game
coordination mechanism
Nash Equilibrium
price of anarchy