排序论是运筹学的重要组成部分，在最初研究排序论的几十年中，学者们主要研究排序问题的算法，排序中的工件遵从算法的安排，但是现实中存在着许多问题，当中工件具有独立性和自利性，它们只关心自身的利益，忽视因此而造成的资源浪费。因此设计协调机制来引导工件的选择达到均衡的同时尽量优化社会资源的支配有着重大的意义。排序模型一般由m台机器M1, M2,,Mm和n个工件1,2,, n组成。给定一个排序，工件j的开工时间记为S j，完工时间记为C j。具体的排序模型主要由机器环境，工件特征和目标函数来决定。　　本文考虑的排序模型可概括为四种类型：(1)机器为m台平行机，每个工件具有一个权重j，全局目标是最小化最大加权完工时间。(2)机器为m台相关机，机器M i的速度为si，工件j的负载为l j，工件j在机器M i上的加工时间是l j si，每个工件具有一个权重j，全局目标是最小化最大加权完工时间。(3)机器为m台并行批处理平行机，机器最多可将b个工件作为一批进行加工，同一批中工件的开工时间和完工时间是相同的。该模型的全局目标是最小化最大完工时间。(4)机器为m台并行批处理相关机，机器M i的速度为si，工件j的负载为l j，工件j在机器M i上的加工时间是l j si，全局目标是最小化最大完工时间。　　本文研究的是上述排序问题在博弈环境下的情形。在博弈环境下，每个工件对应一局中人，每个工件的目标是最小化自身的完工时间，工件具有独立的选择权，工件可根据机器的排序规则选择有利于自己的机器进行加工。每个工件j的策略集X j为机器的集合，即X j {M1, M2,, Mm}。每个工件的策略选定后形成一策略局势X，X X1X2Xn实际是一从工件集合J到机器集合{M1, M2,, Mm}的映射。一策略局势称为纳什均衡，若在其他工件不改变策略的情况下，没有工件能通过单独改变自己的策略减小自身的完工时间。每台机器都有一个排序规则，这个规则决定在它上面加工的工件的加工顺序。所有机器的排序规则的集合称为协调机制。可以看出,给定协调机制和工件的策略局势,则每个工件的完工时间确定。无秩序代价是衡量协调机制好坏的重要指标,指的是在最坏情况下纳什均衡解的值与最优值之比。　　本文针对上述四种排序博弈问题设计协调机制,分析纳什均衡的存在性和求解方法,估计相应机制的无秩序代价,主要有如下结论：(i)对于平行机机器环境、全局目标为最小最大化加权完工时间的排序博弈问题,分析了最大权重优先机制的无秩序代价,证明它的无秩序代价为2-1/m。(ii)将最大权重优先机制应用到了机器为相关机、全局目标为最小化最大加权完工时间的排序博弈问题,证明该问题在最大权重优先机制下的纳什均衡解是存在且唯一的,并且最大权重优先机制的无秩序代价的上界为l+(m-1)smax/(ms)。(iii)对于并行批处理平行机、全局目标为最小化最大完工时间的排序博弈问题,设计了ε-FBLPT协调机制,证明该协调机制的纳什均衡解是存在且唯一的,并且该协调机制的无秩序代价的上界为2-2/(3b)-1/(3max{m,b}),同时估计了无秩序代价的下界,证明在m=b时,该协调机制的无秩序代价是紧的。(iv)将ε-FBLPT协调机制应用到了机器为并行批处理相关机、全局目标为最小化最大完工时间的排序博弈问题,可以证明该问题在ε-FBLPT协调机制下的纳什均衡是存在且唯一的,并且ε-FBLPT协调机制的无秩序代价的上界为1+Smax(1-1/max{m,b})/s.在m=2的情况下ε-FBLPT协调机制的无秩序代价的上界为2-1/max{2,b}。(v)证明上述四种排序博弈问题在相应的协调机制下都是势博弈。