排序理论是运筹学组合优化领域中最为活跃的分支之一.自上世纪50年代以来,一直备受生产制造、供应链管理、互联网等领域研究人员的关注,并随着理论研究的深入及实际生产生活的需要,出现了很多新的模型.本文主要研究三类排序问题中的新模型：一个新的混合流水作业排序模型,一个新的两阶段供应链排序模型和一个混合协调机制下的排序博弈模型.对于前两个模型核心在于分析问题的计算复杂性并给出高效的最优算法,对于第三个模型主要分析它的社会无序代价从而评判出该协调机制的优劣.全文共分四章.第一章首先介绍了排序问题、计算复杂性和算法、算法博弈论和排序博弈等的基本概念和理论背景,接着论述了与本文相关的三类排序问题的研究背景和已有主要成果.第二章讨论了一个两台机器两个加工工序的混合流水作业问题.每个工件都包含两个加工工序,第一个工序可以在任何一台机器上加工,它被称为柔性工序；但是第二个工序必须在第一个工序完成后只能放在第二台机器上加工.该问题的关键在于如何选择工件柔性工序的加工机器使最大完工时间（makespan）极小化.首先对于该问题的一般模型我们给出了一个完全多项式时间近似方案（FPTAS）,而对于工件加工时间均为单位时间的特殊情况,根据两台机器之间的缓存情况不同分成几个研究模型,我们分别给出了这些模型的最优算法并且发现了一个非常有趣的结果：机器间的缓存空间不少于2的前提下,再增加缓存空间并不会得到更好的结果.第三章研究了一个分批加工以准时交货为目的的排序问题,该问题相当于一个“生产-运输”两阶段的供应链问题.在这个问题中有K个客户的订单需要加工,每个订单包含若干个单位加工时间的工件并且有一个交货期.一个客户的订单被分成若干批次,当机器加工完一个批次的工件之后用具有载重限制的货车运送到客户仓库.客户要求准时交货,早于交货期或者晚于交货期都要承担一定惩罚费用,而每次用货车运送一批完工的工件到客户仓库都会产生定量的运输费用.研究的目标是找到一个加工安排方案使得工厂的总费用最小.首先在工件必须从0时刻开始加工的假设下（记作假设（a））,针对单客户模型,我们给出了最优调度的一些性质,在此基础上设计了一个多项式时间算法,并进而针对多客户模型的几个特例给出了动态规划算法.其次我们考虑更接近实际的模型,也就是不带上述假设（a）的情况下,针对单客户模型我们也给出了一个多项式时间算法.而对于多客户情况的几个特例也给出类似带假设（a）情况下的动态规划算法.第四章讨论了一个排序博弈问题.在这个排序问题中,每个工件是一个自私的参与者,它可以自主地选择一台机器加工以谋求自身加工费用（通常为工件的赋权完工时间）最小化.每个工件在0时刻到达并且不允许中断加工,而每台机器也是在0时刻达到并且可以任意选择自己的协调机制.这一点不同于之前绝大多数排序博弈问题的研究.在那些研究中,机器被要求统一按照某种协调机制而不像本章研究的问题那样,允许不同机器采用不同协调机制.本排序博弈问题中,共有两个协调机制可供不同机器选择,它们是赋权最小加工时间优先（wSPT）机制和按比例分配速度（PS）机制.而问题的社会目标为工件的赋权完工时间总和而不是以往的研究中通常所采用的最大完工时间（makespan）.对于该排序博弈问题,我们首先给出一个该问题的松弛线性规划,然后写出该线性规划问题的对偶规划问题.通过比较上述两个规划问题的最优目标以及该排序博弈问题的最优社会目标和混合纳什均衡解的最差社会目标这四个数值,从而得到这个排序博弈问题的混合社会无序代价为4.