《运筹学与控制论综述》由会员分享，可在线阅读，更多相关《运筹学与控制论综述（27页珍藏版）》请在金锄头文库上搜索。
1、恒速机下的有限资源博弈排序最优性研究摘要摘要排序问题是一类组合最优化问题,由于排序问题中的处理机、任务或作业是有限的,绝大部分排序问题是从有限个可行解中找出一个最优解,使目标函数达到极小.本文主要研究有限资源的博弈排序问题,我们考虑的资源是相同的,博弈的社会成本是实用的.在恒速机博弈排序模型中,每一个工件都可以自主选择一个合适的机器来加工它自己,这样每个工件的目标就是使它自己的成本最小.工件的成本是指它所选择的那台机器的总完工时间.本文的结构安排如下： 第一章为绪论部分,主要介绍了排序问题、博弈论和纳什均衡问题、博弈排序的产生背景和主要内容以及后两章内容需要用到的一些预备知识. 第二章考虑了恒
2、速机下的博弈排序模型.在纳什均衡中,在每个工件的策略都不改变的情况下,任何一个工件都不能通过单方面的改变自己的策略来降低它的成本,但是纳什均衡不一定是最优的,实际上还常常与最优值存在很大差距.在这里我们使用（the price of anarchy）和（the price of stability）来分析纳什均衡的质量.当目标函数是总完工时间时,求得界和界.当目标函数是时间表长度时,求得界. 第三章考虑了两台和台带激活费用的恒速机模型,研究的整体目标函数是机器的总完工时间和激活费用之和,最后我们用来衡量纳什均衡时的最差的整体目标函数值与最优值之间的差异.两台机器时,我们假设机器的速度分别是1和
3、,每台机器的激活费用和它的速度相等,.台机器时,我们假设机器的激活费用都是1,不随每台机器的速度变化,分别求得两种情况下的界. 关键词:博弈排序；纳什均衡；恒速机；激活费用；AbstractIAbstractScheduling problem is a kind of combinatorial optimization problems, due to the processor task or assignment is limited, so most of the scheduling problems is to find an optimal solution from limi
4、ted feasible solutions, as to achieve the minimum of the objective function. In this paper, we investigate resource allocation games for job scheduling when the resource are limited. The resource we considered are identical and the social costs of the games are utilitarian. In terms of machine sched
5、uling, assignment of jobs to machines in which selfish agents, representing individual jobs, select machines for processing the jobs, and each job will be minimize its cost. The structure of this article is as follows:The first chapter is an introduction, it mainly introduces the combinatorial optim
6、ization problems, the background of game scheduling and some preliminary knowledge. In the second chapter, we consider the load balancing game in uniform machines. A Nash equilibrium(NE) is a strategy profile, in any NE assignment, no job can reduce its cost by unilaterally changing its machine. But
7、 in terms of a given social objective, such an Nash equilibrium is not necessarily, indeed can often be far from optimal. We use the notions of the price of anarchy() and the price of stability() to analyze the quality of NE solutions.when the The objective function is Total completion time,we prove
8、 theand the. When the objective function is the makespan, we prove the . In the third chapter, we consider a system with two uniform machines and a fixed number of uniform machines. The social cost is the sum of the system makespan and activation cost of machines. We assess the quality of Nash equil
9、ibrium in terms of the .we assume that the speed of the machine is 1 and respectively, and the activation of each machine cost is equal to its speed when there are two machines. we assume that the machine activation cost is 1 and dont change with the speed of each machine when there are machines, we
10、 prove the of two cases.Keywords： Game scheduling; Nash equilibrium; Uniform machines; activation cost; price of anarchyI目录目录摘要I第1章 绪论11.1 排序问题的介绍11.2 博弈论和纳什均衡问题的介绍21.3 博弈排序问题的介绍31.4 本文研究的主要内容4第2章 无激活费用的恒速机博弈排序模型62.1 引言62.2 问题描述62.3 台恒速机上社会成本为总完工时间的博弈排序问题82.4 台恒速机上社会成本为时间表长度的博弈排序问题112.5 总结13第3章 带激活费
11、用的恒速机博弈排序143.1 引言143.2 问题描述143.3 两台带激活费用的恒速机分析153.4 台带激活费用的恒速机分析163.5 总结17参考文献20在读期间发表的学术论文及研究成果23致谢24II第1章 绪论第1章 绪论本章主要介绍了研究问题的背景,有关概念及其相关的研究进展,并简要说明了本文研究的主要成果及创新点.1.1 排序问题的介绍排序（scheduling）问题一开始主要应用于机器制造,后来被广泛应用,运输调度、计算机网络系统、生产管理等很多领域都要用到排序的理论和算法.排序是随时间对有限资源进行分配来执行一个给定的工作或活动,排序模型在工厂的应用和计算机系统的应用中起到很
12、重要的作用.其他常见的排序问题有:项目调度,人员安排,制定时间表等.排序问题已经非正式的研究了几个世纪,Gantt Chart用一个图形表示了在第一次世界大战中任务和资源随着时间的推移情形,这是应用排序的第一个正式模型,1950年代首次使用数学模型分析机器的调度问题,1970进一步研究了计算复杂性,现在,排序问题又广泛应用于现代制造业环境和供应链协调中.排序其实是一类重要的组合优化问题,它是利用一些机器（machine）、处理机（processor）或资源（resource）完成一批给定的任务（task）或作业（job）,使其结果最优,结果最优指的是使目标函数达到最小,而目标函数通常是对工件或
13、任务的完工时间的长短、处理机的利用率、机器的总的费用等的描述.排序问题的三要素包括处理机、任务或作业和目标函数.处理机的数量类型和环境不同,作业或任务和资源的约束条件更是错综复杂,而且目标函数不同,形成了种类繁多的排序类型.我们普遍采用Graham等人创立的三参数表示法（three-field representation）来描述一个排序问题9.一般排序问题表示为：,其中,域表示的是处理机的数量、环境和类型；域表示的是作业或任务的性质、资源的数量,加工要求或者限制、作业或任务的种类和对加工的影响等条件,它可以同时包含许多项；域表示的是这个排序问题的目标函数.域（机器环境） ：指的是单处理机（s
14、ingle machine）.：个同速机,它指的是每台机器的速度都是一样的. ：个恒速机,它指的是机器的速度是不一样的,而且每台机器的速度都是一个常数,但是机器的速度并不依赖于被加工的工件.:个变速机,它指的是每台机器的速度不同,但是机器的速度依赖于被加工的任务.域（工件的加工约束和限制） : 任务的加工时间. ：任务的到达时间.如果中不出现,则表示所有的工件在0时刻都可以加工. ：对任务限定的完工时间.若不按期完工,则有一定惩罚. ：工件的权重,它表示工件相对于其他的工件的重要程度.域（要优化的目标函数） ：最大完工时间,即时间表长,它等于排序最后一个工件的完工时间.,：总完工时间和,加权总
15、完工时间和.：最大延误,即最大工件延迟时间.1.2 博弈论和纳什均衡问题的介绍博弈论是指研究多个个体或团队之间在特定条件制约下的对局中利用相关方的策略,而实施对应策略的学科.它是应用数学的一个分支,也是运筹学的一个重要组成部分,在很多领域都有广泛的应用.一般认为,博弈主要可以分为合作博弈和非合作博弈.合作博弈研究的主要是当人们达成合作协议时如何分配合作所得到的收益,就是所谓的收益分配问题；非合作博弈研究的主要是人们在利益相互制约的资源分配问题中如何选择自己的策略使自己的收益最大,就是策略决策问题.非合作博弈强调的是个人理性,个人的最优决策,其结果可能是有效率的,也可能是无效率的.本文研究的主要是非合作博弈. 博弈广泛应用于资源分配中,例如：在作业调度应用中,任务分配给机器处理,同样,在沟通或交通网络,路由流量分配给网络链接.这些设置就是许多有趣的组合优化问题,但因为他们经常由多个战略用户决定,一个用户的个人收益由其他用户的决策决定,在资源分配分析中,博弈论已经成为一种必不可少的工具.在本文中,我们运用非合作博弈的理论研究资源分配问题,研究工件排序问题,博弈论的核心观点是假设每个客户都有战略上的考虑,都要使自己的成本最小,而不是最优化总
