恒速机上与误工问题有关的纳什均衡（NE）研究

发布时间：2017-08-23 13:12

  本文关键词：恒速机上与误工问题有关的纳什均衡（NE）研究

  更多相关文章： 博弈排序 纳什均衡 恒速机 局部规则 APOA

【摘要】：排序问题是一类重要的组合最优化问题,它是利用一些处理机、机器或资源,最优的完成一批给定的任务或作业.博弈排序是排序问题的重要组成部分,是传统的排序论与博弈论的交叉.在博弈排序问题中我们考虑将n个工件放在m台机器上加工,每个“局中人”选择一台机器来加工其工件,使其目标函数值达到最优.纳什均衡是一种博弈的解的概念,一个博弈中包含两个或更多个局中人,假设每个局中人了解其他局中人的策略并且每个局中人不会因为单方面改变他自己的策略而获益.一般来说,纯策略纳什均衡不一定存在但是混合策略纳什均衡是普遍存在的.本文我们只探讨纯策略纳什均衡.在排序模型中,每个工件的加工时间是jC,工件的社会效用定义为j-C.没有一个中央协调,每个工件选择能使自己尽早完工的机器,而无视中心目标的性能,这可能会导致混乱.为了解决这一冲突,每台机器提前宣布自己的局部排序规则,依此规则安排在该机器上加工的工件.例如,SPT规则,被安排到这台机器上的工件按加工时间的非减序加工.如果排序规则仅仅依赖于该机器工件的加工时间,称作强局部规则.本文主要研究了机器在EDD局部排序规则下恒速机上目标函数分别为最大误工、总误工、误工任务数以及在LW局部排序规则下目标函数为加权总误工任务数的博弈排序问题的纳什均衡状态.本文结构安排如下:第一章为绪论,主要介绍了排序问题、协调机制、博弈论和纳什均衡问题、博弈排序问题的产生和它的主要内容以及国内外研究现状.第二章主要介绍了m台恒速机上,每台机器的局部排序规则为EDD,目标函数为最大误工和总误工的博弈排序问题.在纳什均衡中,在每个工件的策略都不改变的情况下,任何一个工件都不能通过单方面的改变自己的策略来降低它的成本.但是纳什均衡不一定是最优的,实际上还常常与最优值存在很大差距.我们通常用POA(the price of anarchy)来衡量纳什均衡的稳定性.在本文中由于目标函数的最优值可能是0,因此我们又定义了APOA(absolute price of anarchy).在本章中我们分别求出了目标函数为最大误工与总误工的博弈排序问题APOA的上界.第三章首先介绍了两台恒速机上,每台机器的局部规则为EDD,目标函数为误工任务数的博弈排序问题;每台机器的局部规则为LW,目标函数为误工任务数的博弈排序问题.然后我们将机器环境扩展到m台恒速机上,分别求出在各自排序规则下上述问题纳什均衡状态下APOA的值.
【关键词】：博弈排序 纳什均衡 恒速机 局部规则 APOA
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O223
【目录】：

• 摘要3-4
• Abstract4-7
• 第1章 绪论7-13
• 1.1 排序问题7-8
• 1.2 协调机制8-9
• 1.3 博弈论与纳什均衡9
• 1.4 博弈排序问题9-10
• 1.5 相关研究现状及主要工作10-13
• 第2章 恒速机上目标函数为最大误工和总误工的博弈排序模型13-20
• 2.1 引言13
• 2.2 问题描述13-15
• 2.3 m台恒速机上目标函数为最大误工的博弈排序模型15-18
• 2.4 m台恒速机上目标函数为总误工的博弈排序模型18-19
• 2.5 总结19-20
• 第3章 恒速机上目标函数为误工任务数和加权误工任务数的博弈排序模型20-25
• 3.1 引言20
• 3.2 问题描述20-21
• 3.3 两台恒速机上,目标函数为误工任务数和加权误工任务数的博弈排序问题21-22
• 3.4 m台恒速机上,目标函数为误工任务数和加权误工任务数的博弈排序问题22-24
• 3.5 总结24-25
• 参考文献25-27
• 在读期间发表的学术论文及研究成果27-28
• 致谢28

【相似文献】

中国期刊全文数据库 前10条

1 蒋军;颉录有;董晨钟;万建杰;;高离化态类Ne离子的与X射线激光有关的3p-3s跃迁的理论研究[J];原子与分子物理学报;2008年03期

2 贾飞;林承键;张焕乔;杨峰;贾会明;徐新星;吴振东;刘祖华;张高龙;张春雷;詹文龙;肖国清;徐瑚珊;王建松;孙志宇;王猛;雷相国;张雪荧;胡正国;张宏斌;徐治国;陈若富;黄天衡;章学恒;高启;郑川;杨彦云;岳柯;涂小林;张亚鹏;唐彬;;激发态~(17)Ne双质子2p发射的实验[J];中国原子能科学研究院年报;2008年00期

3 王同生,叶为文,马忠乾;在Ne~(22)照射U~(238)核反应中观察到反常截面的金同位素[J];物理学报;1966年06期

4 雷印生,张诏祥,廉英武;Ne原子的光电流光谱理论和实验研究[J];量子电子学;1986年04期

5 钟旭滨,刘炳模,鲍琢玉;Ne原子射频放电光电流效应及其高激发态能级的测量[J];中国激光;1991年06期

6 徐光裕;;~3He-~(20)Ne稳定横向塞曼激光器[J];激光与光电子学进展;1981年02期

7 赵恩广,李先卉,陈生忠,王潍潍;相互作用对统计谱分析的影响——~(20)Ne原子核的形状因子[J];科学通报;1988年06期

8 焦哲,吴志勇,邝耀麟,除治平,BenoitJN;门静脉高压鼠动脉对NE的低反应与内皮细胞的关系[J];上海第二医科大学学报;1999年S1期

9 陈新跃;王岳军;范蔚茗;彭头平;葛铁辉;;琼西南NE向韧性剪切带构造特征及其~(40)Ar-~(39)Ar年代学约束[J];地球化学;2006年05期

10 周达君，程捷，，李润华;Ne原子2P_j能级寿命的测定[J];中国激光;1994年09期

中国重要会议论文全文数据库 前6条

1 王康宁;;猪禽饲料NE测定及其需要量研究[A];饲料营养研究进展（2010）[C];2010年

2 王海军;乔明琦;张惠云;;经前期综合征肝气逆证猕猴模型血清与尿中去甲肾上腺素(NE)测定分析[A];中国中西医结合学会第七次全国实验医学学术研讨会论文汇编[C];2004年

3 许瑾;戴康;沈异凡;;Rb(5D_J)-He,Ne的精细结构能量转移[A];第四届西部十二省（区）市物理学会联合学术交流会论文集[C];2008年

4 贾飞;林承键;张焕乔;杨峰;贾会明;徐新星;吴振东;刘祖华;张高龙;张春雷;;~(17,18)Ne激发态~2He集团发射的实验判据[A];二00九全国核反应会暨生物物理与核物理交叉前沿研讨会论文摘要集[C];2009年

5 王昌斌;邢丕峰;罗阳明;;Ne同位素色谱的制备[A];中国工程物理研究院科技年报（1999）[C];1999年

6 冯飞;徐国建;;快眼动睡眠剥夺对抑郁模型大鼠海马5-HT,NE及腺苷的影响[A];中华医学会第十次全国精神医学学术会议论文汇编[C];2012年

中国重要报纸全文数据库 前2条

1 记者 刘春辉;华为推出NE系列路由器新品[N];人民邮电;2002年

2 文戈;中国第一奢侈品品牌NE·TIGER续写传奇[N];中国工业报;2008年

中国硕士学位论文全文数据库 前3条

1 杨杰;恒速机上与误工问题有关的纳什均衡（NE）研究[D];曲阜师范大学;2016年

2 彭昕;NE对离体脑微血管内皮细胞缺血性损伤的作用[D];重庆医科大学;2007年

3 张彬;慢性阻塞性肺疾病大鼠al-AT和NE的表达及糖皮质激素的治疗作用和机制研究[D];河北医科大学;2012年

本文编号：725215