期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

单机排序模型下自利任务的无秩序代价分析与机制设计 被引量：2

Price of Anarchy and Mechanism Design for Single Machine Scheduling among Selfish Tasks
下载PDF
导出
摘要 研究单机排序模型下自利任务的资源分配问题:每个任务具有异构的正规型目标,系统也具有独立的全局目标.由于任务的自利性,无序竞争常导致系统全局目标的恶化,造成无秩序代价.为此,采用非合作博弈建立单机下该问题的模型,定义Nash均衡调度,定量分析Nash均衡调度的无秩序代价,并设计一种可以平衡独立自利任务和系统目标的协调机制,仿真验证机制的有效性. The problem of scheduling selfish tasks on sequencing model of single machine is studied,where each task has heterogeneous regular objective and system also has an independent global objective.Because of tasks＇ selfishness,anarchistic competition would deteriorate the global performance,and then,result in price of anarchy.Hence,corresponding noncooperative game is introduced to model the case of single machine and an equilibrium result named Nash equilibrium schedule is given.The tight price of anarchy of Nash equilibrium schedule is analyzed quantitatively and a coordination mechanism is designed to balance the requirements among selfish tasks and system.Numerical example is also given for illustration.
作者 王长军 王志宏 贾永基
机构地区 东华大学旭日工商管理学院
出处 《东华大学学报（自然科学版）》 CAS CSCD 北大核心 2010年第6期680-685,702,共7页 Journal of Donghua University(Natural Science)
基金 国家自然科学基金资助项目(70772073 60874076)
关键词 单机 排序模型 自利任务 无秩序代价 协调机制 single machine sequencing model selfish tasks price of anarchy coordination mechanism
分类号 C935 [经济管理—管理学]
  • 相关文献

参考文献25

  • 1SIMCHI-LEVI D,KAMINSKY P,SIMCHI-LEVI E.供应链设计与管理:概念、战略与案例研究[M].3版.北京:中国人民大学出版社,2009.
  • 2ROUGHGARDEN T.Selfish Routing and the Price of Anarchy[M].Massachusetts:The MIT Press,2005.
  • 3KUTANOGLU E,WU S D.On Combinatorial Auction and Lagrangean Relaxation for Distributed Resource Scheduling[J].IIE Transactions,1999,31(9):813-826.
  • 4KOUTSOUPIAS E,PAPADIMITRIOU C.Worst-case Equilibria[C]//Proceeding of the 16th Internstional Symposium on Theorctical Aspects of Computer Science,Berlin:Springer,1999:404-413.
  • 5OWEN G.Game Theory[M].3rd ed.San Diego:Academic Press Inc,1995.
  • 6NISAN N,ROUGHGARDEN T,TARDOS E,et al.Algorithmic Game Theory[M].Cambridge:Cambridge University Press,2007.
  • 7ANDELMANN,FELDMAN M,MANSOUR Y.Strong Price of Anarchy[J].Games and Economic Behavior,2009,65(2):289-317.
  • 8GAO Y.The Price of Anarchy in Finance:Quantifying the Degrce of Confusion of Subprime Credit Crisis[R/OL].(2009-02-17)[2009-10-15].http://ssrn.com/abstract= 1343524.
  • 9HAVIV M,ROUGHGARDEN T.The Price of Anarchy in an Exponential Multi-server[J].Operations Research Letters,2007,35(4):421-426.
  • 10GEORGIA P,GUILLAUME R.The Price of Anarchy in Supply Chains:Quantifying the Efficiency of Price-only Contracts[J].Management Science,2007,53(8):1249-1268.

二级参考文献37

  • 1Guha S,Khuller S.Improved methods for approximating node weighted steiner trees and connected dominating sets.2006.http://www.springerlink.com/index/XJ2CGKEJGDWDC1TP.pdf
  • 2Colell AM,Whinston M,Green J.Microeconomic Theory.New York:Oxford University Press,1995.
  • 3Tan G,Jarvis SA.A payment-based incentive and service differentiation mechanism for peer-to-peer streaming broadcast.2006.http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=4015719&arnumber=4015732&count=54&index=11
  • 4Li D,Wu J,Cui Y,Liu J.QoS-Aware streaming in overlay multicast considering the selfishness in construction action.2006.http://netlab.cs.tsinghua.edu.cn/～lidan
  • 5Deering S.Multicast routing in internetworks and extended LANs.In:Landweber L,ed.Proc.of the Communications Architectures and Protocols.Stanford:ACM Press,1988.55-64.
  • 6Francis P.Yoid:Extending the Internet multicast architecture.2006
  • 7Chu YH,Rao SG,Zhang H.A case for end system multicast.IEEE Journal on Selected Areas in Communication,2002,20(8):1456-1471.
  • 8Chawathe Y.Scattercast:An architecture for internet broadcast distribution as an infrastructure service[Ph.D.Thesis].Berkekey:University of California,2000.
  • 9Jain S,Mahajan R,Wetherall D,Borriello G.Scalable self-organizing overlay.Technical Report,Washington University,2000.
  • 10Kwon M,Fahmy S.Topology-Aware overlay networks for group communication.2006.pub.html

共引文献3

同被引文献28

  • 1Wang Changjun Xi Yugeng.Rolling optimization algorithm based on collision window for single machine scheduling problem[J].Journal of Systems Engineering and Electronics,2005,16(4):816-822. 被引量：4
  • 2MAISTER D H. The psychology of waiting lines [M]// CZEP1EL J A, SOLOMON M R, SURPRENANT C F. The service encounter: Managing employee/customer interaction in service businesses. Lexington: Lexington Books, 1985: 113-123.
  • 3MuRPHYPRJ,WOODDF.当代物流学[M].北京:中国人民大学出版社,2009.
  • 4KENNETH R B, SMITH J C. A multiple-criterion model for machine scheduling[J]. Journal of Scheduling, 2003, 6(1):7-16.
  • 5LUH P B, HOITOMT D J, MAX E, et al. Schedule generation and reeonfiguration for parallel machines[J]. IEEE Transactions on Robotics and Automation, 1990, 6 (6) : 687 -696.
  • 6KETHLEYA R B, BAHARAM A. Single machine scheduling to minimize total weighted late work: A comparison ofscheduling rules and search algorithms [J]. Computers Industrial Engineering, 2002, 43(3) : 509-528.
  • 7PINEDO M. Scheduling: Theory, algorithms and systems [M]. New Jersey: Prentice Hall, 1995.
  • 8CHENG T E, LIU Z H. Parallel machine scheduling to minimize the sum of quadratic completion times [J]. IIE Transactions, 2004, 36(1):11-17.
  • 9SUN X Q, NOBLE J S, KLEIN C M. Single-machine scheduling with sequence dependent setup to minimize total weighted squared tardiness[J]. IIE Transactions, 1999, 31 (2) : 113-124.
  • 10ROTHKOPF M H. Scheduling independent tasks on parallel processors[J]. Management Science, 1966, 12: 437-447.

引证文献2

二级引证文献4

东华大学学报（自然科学版）
2010年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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