恒速机下的有限资源博弈排序最优性研究

发布时间：2017-08-05 04:06

  本文关键词：恒速机下的有限资源博弈排序最优性研究

  更多相关文章： 博弈排序 纳什均衡 恒速机 激活费用 POA

【摘要】：排序问题是一类组合最优化问题,由于排序问题中的处理机、任务或作业是有限的,绝大部分排序问题是从有限个可行解中找出一个最优解,使目标函数达到极小.本文主要研究有限资源的博弈排序问题,我们考虑的资源是相同的,博弈的社会成本是实用的.在恒速机博弈排序模型中,每一个工件都可以自主选择一个合适的机器来加工它自己,这样每个工件的目标就是使它自己的成本最小.工件的成本是指它所选择的那台机器的总完工时间.本文的结构安排如下:第一章为绪论部分,主要介绍了排序问题、博弈论和纳什均衡问题、博弈排序的产生背景和主要内容以及后两章内容需要用到的一些预备知识.第二章考虑了恒速机下的博弈排序模型.在纳什均衡中,在每个工件的策略都不改变的情况下,任何一个工件都不能通过单方面的改变自己的策略来降低它的成本,但是纳什均衡不一定是最优的,实际上还常常与最优值存在很大差距.在这里我们使用POA(the price of anarchy)和POS(the price of stability)来分析纳什均衡的质量.当目标函数是总完工时间时,求得POA界和POS界.当目标函数是时间表长度时,求得POA界.第三章考虑了两台和m台带激活费用的恒速机模型,研究的整体目标函数是机器的总完工时间和激活费用之和,最后我们用POA来衡量纳什均衡时的最差的整体目标函数值与最优值之间的差异.两台机器时,我们假设机器的速度分别是1和a,每台机器的激活费用和它的速度相等,.m台机器时,我们假设机器的激活费用都是1,不随每台机器的速度变化,分别求得两种情况下的POA界.
【关键词】：博弈排序 纳什均衡 恒速机 激活费用 POA
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223
【目录】：

• 摘要3-4
• Abstract4-6
• 第1章 绪论6-11
• 1.1 排序问题的介绍6-7
• 1.2 博弈论和纳什均衡问题的介绍7-8
• 1.3 博弈排序问题的介绍8-9
• 1.4 本文研究的主要内容9-11
• 第2章 无激活费用的恒速机博弈排序模型11-19
• 2.1 引言11
• 2.2 问题描述11-13
• 2.3 m台恒速机上社会成本为总完工时间的博弈排序问题13-16
• 2.4 m台恒速机上社会成本为时间表长度的博弈排序问题16-18
• 2.5 总结18-19
• 第3章 带激活费用的恒速机博弈排序19-24
• 3.1 引言19
• 3.2 问题描述19-20
• 3.3 两台带激活费用的恒速机POA分析20-21
• 3.4 m台带激活费用的恒速机POA分析21-22
• 3.5 总结22-24
• 参考文献24-27
• 在读期间发表的学术论文及研究成果27-28
• 致谢28

【参考文献】

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

1 CHEN Bo;LI SongSong;ZHANG YuZhong;;Strong stability of Nash equilibria in load balancing games[J];Science China(Mathematics);2014年07期

，

本文编号：623054