工件带有恶化效应的博弈排序问题

发布时间：2018-02-08 15:38

本文关键词： 同速机排序恶化效应纳什均衡 PoA　出处：《曲阜师范大学》2015年硕士论文　论文类型：学位论文

【摘要】：博弈排序问题是排序论与博弈论的一个交叉问题,就是从一个博弈的观点研究排序问题.每个参与者在博弈中的个人目标都是极小化自己的个人成本,我们把这个定义为此工件所在机器的负载.极大化社会价值是我们所考虑的社会目标.纳什均衡时的总时间往往不是最小的,有时候与最优值相差很大,所以,我们常用PoA这个参数来衡量纳什均衡的目标函数值与最优值之间的差距.其中,PoA是指纳什均衡排序中的任意一个排序的社会目标值与最优值的比率的最坏情况界.本文主要研究了工件带有恶化效应的博弈排序问题.工件具有恶化效应即工件的实际加工时间会随着工件的开工时间的增加而增加,即工件的实际加工时间除了工件本身的基本加工时间外还需要加上工件的开工时间与恶化率的乘积.本文研究了机器环境为m台同速机的情况.第一章主要介绍了排序问题和博弈排序的相关概念,以及相关领域的进展,并简要概括了文章的主要工作和创新点.第二章我们主要考虑了工件的加工时间是开工时间的线性增加函数的同速机排序问题.目标函数分别为极小化工件的总完工时间和极小化机器的总负载.当工件具有不同的基本加工时间和相同的恶化率时,我们给出了目标函数的PoA值.第三章我们研究了工件带有恶化效应的同速机排序问题.目标函数为极小化总完工时间.当每个工件都具有相同的基本加工时间和相同的恶化率时,我们得到了目标函数的PoA值.
[Abstract]:The ordering problem of game is a cross problem between the theory of ranking and the theory of game, which is to study the problem of ordering from the point of view of a game. The individual goal of each participant in the game is to minimize their own personal cost. We define this as the load on the machine in which the workpiece is located. Maximizing social value is the social goal we consider. The total time of Nash equilibrium is often not the smallest, sometimes very different from the optimal value, so, We use PoA as a parameter to measure the difference between the objective function value and the optimal value of Nash equilibrium, where PoA is the worst-case bound of the ratio of the social target value to the optimal value of any sort in the Nash equilibrium ranking. In this paper, we mainly study the problem of game ordering of workpiece with aggravation effect, that is, the actual processing time of workpiece increases with the start time of workpiece. That is, the actual processing time of the workpiece needs to be added to the product of the starting time and the deterioration rate of the workpiece in addition to the basic processing time of the workpiece itself. In this paper, the related concepts of ordering problem and game ordering are discussed. And progress in related areas, In the second chapter, we mainly consider that the processing time of the workpiece is the linear increasing function of the starting time and the same speed machine sort problem. The objective function is the total of the minimal chemical parts, respectively. Completion time and minimization of the total load of the machine. When the workpiece has different basic processing times and the same deterioration rate, We give the PoA value of the objective function. In chapter 3, we study the scheduling problem of the same speed machine with deterioration effect. The objective function is to minimize the total completion time. When each workpiece has the same basic processing time and. At the same rate of deterioration, We get the PoA value of the objective function.
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223

【相似文献】