工件带有恶化效应的博弈排序问题-数学专业论文.docxVIP

万方数据 万方数据 曲 阜 师 范 大 学 研 究 生 学 位 论 文 独 创 性 声 明 （根据学位论文类型相应地在“□”划“√”） 本人郑重声明：此处所提交的博士□/硕士□论文《工件带有恶化效应的 博弈排序问题》,是本人在导师指导下,在曲阜师范大学攻读博士□/硕士□学位 期间独立进行研究工作所取得的成果.论文中除注明部分外不包含他人已经发 表或撰写的研究成果.对本文的研究工作做出重要贡献的个人和集体,均已在 文中以明确的方式注明.本声明的法律结果将完全由本人承担. 作者签名： 日期： 曲 阜 师 范 大 学 研 究 生 学 位 论 文 使 用 授 权 书 （根据学位论文类型相应地在“□”划“√”） 《工件带有恶化效应的博弈排序问题》系本人在曲阜师范大学攻读博士 □/硕士□学位期间,在导师指导下完成的博士□/硕士□学位论文.本论文的研 究成果归曲阜师范大学所有,本论文的研究内容不得以其他单位的名义发表. 本人完全了解曲阜师范大学关于保存、使用学位论文的规定,同意学校保留并 向有关部门送交论文的复印件和电子版本,允许论文被查阅和借阅.本人授权 曲阜师范大学,可以采用影印或其他复制手段保存论文,可以公开发表论文的 全部或部分内容. 作者签名： 日期： 导师签名： 日期： 3 摘要 摘要 摘 要 博弈排序问题是排序论与博弈论的一个交叉问题,就是从一个博弈的观点研究排序问 题.每个参与者在博弈中的个人目标都是极小化自己的个人成本,我们把这个定义为此工 件所在机器的负载.极大化社会价值是我们所考虑的社会目标.纳什均衡时的总时间往往 不是最小的,有时候与最优值相差很大,所以,我们常用 PoA 这个参数来衡量纳什均衡的目 标函数值与最优值之间的差距.其中, PoA 是指纳什均衡排序中的任意一个排序的社会目 标值与最优值的比率的最坏情况界. 本文主要研究了工件带有恶化效应的博弈排序问题.工件具有恶化效应即工件的实际 加工时间会随着工件的开工时间的增加而增加,即工件的实际加工时间除了工件本身的基 本加工时间外还需要加上工件的开工时间与恶化率的乘积.本文研究了机器环境为 m 台同 速机的情况. 第一章主要介绍了排序问题和博弈排序的相关概念,以及相关领域的进展,并简要概 括了文章的主要工作和创新点. 第二章我们主要考虑了工件的加工时间是开工时间的线性增加函数的同速机排序问 题.目标函数分别为极小化工件的总完工时间和极小化机器的总负载.当工件具有不同的 基本加工时间和相同的恶化率时,我们给出了目标函数的 PoA 值. 第三章我们研究了工件带有恶化效应的同速机排序问题.目标函数为极小化总完工时 间.当每个工件都具有相同的基本加工时间和相同的恶化率时,我们得到了目标函数的 PoA 值. 关键词：同速机排序；恶化效应；纳什均衡； PoA 4 Abstr Abstract Abstract Game scheduling problem is a cross problem of scheduling theory and game theory, which means to study the scheduling problem in terms of game theory. Each of the participants personal goal is to minimize personal cost, and we define this as the load of the machine which processes his jobs. Maximizing social value is the social goal we considered, this is defined as the minimum machine load. The total time in Nash equilibrium is always not the minimum, sometimes deviates significantly from the optimal value. Therefore, we often use the PoA to measure the gap between the optimal value and the objective function of Nash equilibrium. The PoA refers to the worst bound for the ratio of social value in NE scheduling and the social value in the optimal scheduling. In this paper, we mainly studie