摘要: 排序问题是组合优化的一个重要分支，近年来经典排序与博弈论相结合而形成的排序博弈受到了学者的关注。本文主要研究排序博弈中的若干问题及部分有较强应用背景的排序问题，其中多数问题的目标函数为总和型目标，全文共分六章。 第一章介绍了排序... 展开 排序问题是组合优化的一个重要分支，近年来经典排序与博弈论相结合而形成的排序博弈受到了学者的关注。本文主要研究排序博弈中的若干问题及部分有较强应用背景的排序问题，其中多数问题的目标函数为总和型目标，全文共分六章。 第一章介绍了排序问题，排序博弈的基本概念与重要结果。 第二章中，研究两个不同类机以极小化最大完工时间为社会费用的排序博弈模型Price of Anarchy(PoA)和Strong Price of Anarchy(SPoA)的下界。在第一个模型中机器遵循Shortest First规则，证明了对m台不同类机，PoA至少为m，并说明了界为紧界。在第二个模型中机器遵循EQUI规则，证明了对m台不同类机，SPoA至少为m。我们同时证明了任意不可中断，满足无关选择独立性和强局部性的规则的PoA和SPoA的下界至少为m，从而说明了Shortest First在这一类规则中的最优性。 第三章研究两台同类机以极小化总完工时间为目标函数的排序问题Q2‖∑Cj，给出了机器数为2，且s≥2时SPT算法最坏情况界的参数上界与下界，且上界和下界均较已有结果有较大改进。 第四章研究工件有不同大小的批排序问题。证明了m台平行机，即使所有工件加工时间均相等，以极小化最大完工时间为目标的批排序问题不可能有最坏情况界小于2的多项式时间近似算法，除非P=NP。对两台机，工件大小总和大于2这一特殊情形，给出了最坏情况界为1.95的改进算法。对单台机，工件具有相等加工时间，以极小化工件总完工时间为目标的批排序问题，给出了一个最坏情况界不超过9+√3/6的多项式时间近似算法，并证明了即使工件总大小不超过2，该问题也不存在FPTAS，除非P=NP。 第五章研究了不可靠工件排序问题。主要考虑工件成功概率和收益满足一定关系的特殊情形，对目标为极大化总期望收益问题，我们给出一个新的双重排序算法DLS。借助求解凸规划，证明了对m台机，DLS算法的最坏情况界至多为1.1054;对两台机，最坏情况界至多为2+4√2/7，至少为1.0094。我们还考虑了瓶颈型目标，即目标为极小化所有机器的最大期望收益和极大化所有机器的最小期望收益的排序问题，证明了DLS算法的最坏情况界分别为4m-1/3m和4m-2/3m-1。 第六章总结了本文的研究成果，给出了待研究的问题。 收起