排序问题是一类经典的组合优化问题。在传统的排序模型中，工件都只是被动的加工对象，并不参与加工过程的决策。近年来，有许多学者根据实际需要将工件看成是可以自由选择机器加工的主体，并用博弈的思想分析排序问题。本文主要研究排序博弈以及相关排序问题。全文由五章组成。　　 第一章为绪论，介绍相关的基本概念与预备知识、本文主要结果以及一些常用记号。　　 第二章研究了makespan机制下排序博弈的均衡分析。我们主要给出了两台同类机模型下以极大化机器最小负载为整体目标的POS和SPOS的关于机器速度比的完全参数紧界。　　 第三章研究了parallel processing机制下的排序博弈问题。首先，我们给出了同型机环境下LS排序的一个特征刻画，并由此说明了纳什均衡与LS排序的关系。其次，我们对纳什均衡的无效性进行了分析。对m台同型机模型，我们分别给出了以极小化makespan为整体目标的POS和以极大化机器最小负载为整体目标的POA，POS。对两台同类机模型，我们分别给出了以极小化makespan为整体目标和以极大化机器最小负载为整体目标的POA的完全参数界。　　 第四章研提出了一种衡量排序的新指标-平衡度，对三种机器类型和三种加工模式下排序模型的平衡度给出了全面的分析。对所有排序模型的强平衡度给出了紧界，对同型机和可中断加工模式下、同类机和可分割加工模式下排序模型的弱平衡度也给出了紧界，并对其他排序模型的弱平衡度给出了上界和下界，他们在相差一个常数倍意义下是紧的。　　 第五章研究了目标函数为极小化机器最大总完工时间的同型机排序问题。对该问题，当机器台数给定时，我们给出了动态规划以及完全多项式时间近似方案：当机器台数作为输入的一部分时，证明了该问题是强NP-难的，将经典的SPT算法的最坏情况界改进到不超过313/120≈2.6083，还设计了一个最坏情况界为2的近似算法。