期刊文献+

最大加权完工时间排序博弈问题的协调机制

A Coordination Mechanism for a Scheduling Game to Minimize the Maximum Weighted Completion Time
下载PDF
导出
摘要 研究以最小化最大加权完工时间为目标的排序博弈问题的协调机制。相应的排序博弈模型中,有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
  • 相关文献

参考文献8

  • 1Graham R L,Lawler E L,Lenstra J K,et al.Optimization and approximation in deterministic sequencing and scheduling:A survey[J].Annals of Discrete Mathematics,1979,5(2):287-326.
  • 2Koutsoupias E,Papadimitriou C.Worst-case equilibria[C].Trier:Proceedings 16th STACS,LNCS,1999,1563:404-413.
  • 3Christodoulou G,Koutsoupias E,Nanavati A.Coordination mechanisms[C].Turku:Proceedings of the 31st International Colloquium on Automata,Languages and Programming(ICALP),2004,345-357.
  • 4Graham R L.Bounds for certain multiprocessing anomalies[J].Bell System Technical Journal,1966,45(9):1563-1581.
  • 5Graham R L.Bounds on multiprocessing timing anomalies[J].SIAM Journal of Applied Mathematics,1969,17(2):416-429.
  • 6Finn G,Horowitz E.A linear time approximation algorithm for multiprocessor scheduling[J].BIT Numerical Mathmatics,1979,19(3):312-320.
  • 7Schuurman P,Vredeveld T.Performance guarantees of local search for multiprocessor scheduling[J].INFORMS Journal on Computing,2007,19(1):52-63.
  • 8Immorlica N,Li L,Mirrokni V S,et al.Coordination mechanisms for selfish scheduling[J].Theoretical Computer Science,2009,410(17):1589-1598.

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部