排序理论是组合最优化理论的重要组成部分，如果在排序过程中有一个系统管理员来安排相应任务，那么往往会得到比较理想的解。但是，随着互联网的发展，在许多排序过程中由系统管理员来强加控制是不可行的，因为互联网的用户具有独立性和自利性，他们“自私”地追求自身的利益最优，而不在乎是否造成社会资源的浪费。若没有合理的资源使用机制，这种自利性往往会使结果与理论最优值偏差巨大。因此设计合理的机制以影响、引导独立和“自私”的用户的选择从而减少社会资源的浪费将具有重大的理论意义。　　本文所研究的博弈排序模型描述如下：模型中有m台平行机M1,M2,…,Mm, n个待加工的“自私”工件，形成工件集合J={1,2,…,n},工件j的加工时间为pj，每个工件对应一个局中人，每个工件j的目标是最小化自身的完工时间，全局目标函数是某一关于工件完工时间的函数。协调机制是排序规则的集合，它明确每台机器所实行的排序规则。工件可根据系统的机制自主选择有利于优化自身目标函数的机器进行加工。一个工件j的策略集为Xj={M1,M2,…,Mm},j={1,2,…,n}。每个工件的策略选定后形成策略局势X∈X1×X2×…×Xn，在其他工件不改变策略的情况下，没有一个工件可通过单方面改变策略（即移动到另一台机器）从而减少自身完工时间的策略局势称为纳什均衡。　　本文研究三类平行机博弈排序问题的协调机制。　　首先，我们探讨具有两台平行机，其全局目标函数为最小化最大完工时间的博弈排序问题。SPT-LPT机制是指一台机器按工件加工时间的不减顺序排序，另一台机器按工件加工时间的不增顺序排序。我们设计了一种算法，并证明相应博弈排序问题的纳什均衡集等于这一算法的解的集合，然后证明当工件数不小于4时，对于相应博弈排序问题，SPT-LPT机制的无秩序代价为4/3。　　其次，我们探讨具有m台平行机，每个工件j有一权重wj，全局目标函数为最小化最大加权完工时间的博弈排序问题。最大权重优先机制是指第i(i=1,2,…,m)台机器将选择了它的工件按权重从大到小排序，若权重相同，则序号小的工件优先排，并于(i-1)ε时刻开始不间断地加工工件，直到所有选择了它的工件完工。我们设计了一种算法，并证明相应博弈排序问题的纳什均衡集等于这一算法得到的排序，然后证明对于相应博弈排序问题，最大权重优先机制的无秩序代价至少为3/2。　　最后，我们探讨具有m台批容量无界的并行分批处理机，全局目标函数为最小化最大完工时间的博弈排序问题。同批机制是指第i(i=1,2,…,m)台机器将所有选择了它的工件置于同一批，于(i-1)ε时刻开工。我们分析了相应博弈排序问题的纳什均衡解的情况，然后证明对于相应排序博弈问题，同批机制的无秩序代价为1。