排序问题的博弈分析和多目标排序

排序理论是运筹学组合最优化领域中研究最为活跃的分支之一，本项目将深入研究排序的两个新课题：排序问题的博弈分析和多目标排序问题，核心内容是算法设计和最坏情况分析。对排序博弈，研究均衡排序的存在性及其性质，设计符合要求的排序机制。对多目标排序问题，考虑算法的双目标最坏情况界，以及多组竞争工件、工件或机器可选择等模型。我们还将研究应用领域的一些具体排序问题。对以上这些问题，我们将探讨它们的计算复杂性、多项式时间近似方案的存在性或难近似性，以及快速近似算法的设计。这些问题国际上的研究刚刚起步或起步不久，有较大难度，本项目将对它们进行前瞻性研究，获得创新性成果。

排序理论是运筹学组合最优化领域中研究最为活跃的分支之一，本项目主要研究排序问题的博弈分析和多目标排序问题，核心内容是算法设计和最坏情况分析。三年来，项目组在排序博弈的均衡有效性分析、多目标排序以及相关排序问题的研究中取得了一系列成果。对同类机整体目标为最小机器完工时间，工件费用为所在机器的完工时间的排序博弈，我们给出了两台机时以机器速度比为参数的PoA，SPoA，PoS和SPoS的参数紧界，三台机一种特殊情况下的PoA值。对两台同类机，局部机制为并行加工，分别给出了整体目标为makespan和最小机器完工时间时PoA的参数紧界。我们研究了以机器数和makespan之和为目标函数的平行机在线排序问题，改进了问题的下界，并设计了新的算法。对极小化每台机器上加工工件总完工时间的最大值的平行机排序问题，我们研究了问题的复杂性，给出了SPT算法最坏情况界新的上界与下界，并设计了最坏情况界为2的新算法，且该算法同时可使总完工时间达到最小。我们还考虑了目标为极小化总完工时间的有机器维护时段的排序问题，给出了不同维护时段设置下平行机排序问题SPT算法最坏情况界的估计。当机器台数为2且每台机器上只有一个维护时段时，证明了SPT算法是最坏情况界最小的多项式时间近似算法。对单台机，机器上有一个不可操作时段，目标为极小化总完工时间问题，设计了最坏情况界较小的近似算法。对单台机，半可恢复维护时段问题，我们讨论了不同目标函数下问题的复杂性和近似算法。