同类机博弈排序问题

发布时间：2021-12-22 08:47

　　排序,也称为调度,是组合优化理论中的一个重要分支。对于传统的排序问题,给定工件集和机器集,为了达到某个目标值,决策者们通常考虑如何将工件最好的安排到机器上进行加工。这个问题不仅在理论上具有很高的研究价值,在现实中也拥有广泛的应用背景。本文主要研究的是博弈排序问题中无秩序代价,即在排序问题中考虑博弈理论。在博弈排序问题中,没有中央决策者的存在,每个工件被看作是自私的博弈者或每个工件为一个代理所拥有,他们追求个体的最大利益;工件的策略集为可选择的机器集。工件的完工时间的相反数作为工件的效用函数,以所有工件的完工时间和（社会成本）为该问题的目标函数。由于自由博弈产生的纳什均衡解不一定是系统的最优解,因此,纳什均衡解与最优解之间的差异的大小是我们所要讨论的问题。常用无秩序代价（PoA）来刻画纳什均衡解和最优解之间的差距。特别地,PoA值越接近于1说明纳什均衡解对应的目标函数值与最优值越接近。本文的第一章介绍了排序问题的背景知识、基本概念和定义。第二章研究了协调机制为LPT的2台同类机目标函数为所有工件的完工时间和的博弈排序问题。我们证明了在LPT的协调机制下,各代理之间的自由博弈达到的稳定状态... 

【文章来源】：曲阜师范大学山东省

【文章页数】：27 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 排序问题的背景和相关概念
    1.2 博弈排序
        1.2.1 博弈论的基本概念
        1.2.2 博弈排序的协调机制和纳什均衡
        1.2.3 无秩序代价的定义
    1.3 研究现状
    1.4 本文的主要结果及章节安排
第2章 Q_2(LPT)|ut=-C_j| ∑C_j问题
    2.1 问题的模型
    2.2 问题的PoA分析
    2.3 总结
第3章 Q_m(LPT)|ut=-C_j|∑C_j题
    3.1 问题的模型
    3.2 问题的PoA分析
    3.3 总结
参考文献
致谢



本文编号：3546112