排序问题一直是组合优化领域的活跃研究方向．传统的排序模型假设所有的工件属于一个排序者，而且整个排序过程中机器总是保持相同的性能．近年来，人们根据生产实际的需要不断拓展出新的排序问题.针对第一个假设，出现了多客户排序问题，每个客户拥有自己的工件，在共同的机器资源上安排工件使得各方的利益达到某种平衡.对于第二个假设，人们研究机器需要维护情形下的排序方案.机器维护有两个关键参数，维护的开始时刻和维护的时长.不同的参数环境提出了不同的排序问题，围绕上述的两点拓展，本文主要讨论下面几个新型排序模型：维护时间可变的单机排序问题，浮动维护下的线性退化工件单机排序问题和两个客户下的两台机流水作业排序问题.本文由四章组成．　　 第一章为绪论，主要介绍组合优化和排序的基本概念和预备知识．　　 第二章研究了维护时间可变的单机排序问题，其中维护的时长是维护开始时刻的非降函数．当极小化目标函数分别是最大完工时间，最大延迟和工件的完工时间和时，我们给出多项式时间的精确算法．而当目标函数为工件的赋权完工时间和时，我们证明了该问题是弱NP-困难的，并先后设计了一个(2+ε)-近似算法和一个完全多项式时间近似方案．　　 对一类特殊情形，即维护的时长是维护开始时刻的非降凹函数时，我们分别给出了2-近似算法和(1+√2/2+ε)-近似算法.这两个近似算法都是强多项式时间的．　　 最后，我们讨论了维护的时长是维护开始时刻的任意函数的情形，证明了对极小化（赋权）完工时间和的目标函数，不存在近似比为常数的多项式时间算法，除非P=NP.　　 第三章考虑了浮动维护下的线性退化工件单机排序问题．所谓浮动维护是指维护的时长固定，但维护的开始时间不晚于一个给定的时刻．对极小化最大完工时间以及极小化工件完工时间和两个目标函数，我们证明了弱NP-困难性，并分别给出了完全多项式时间近似方案.　　 第四章则研究两个客户下的两台机流水作业排序问题．每个客户只关心自己的工件最大完工时刻．为了将两个目标结合起来化成单目标优化问题，我们考虑了两类模型．一是将两个客户的目标函数赋权求和；二是以一个客户的目标为约束，然后极小化另一个客户的目标．对前者，我们证明了该问题是弱NP-困难的，然后设计了一个简单的近似算法，该算法可以帮助我们进一步提出完全多项式时间近似方案．对后者而言，该问题已知为NP-困难的．通过给出一个伪多项式时间的动态规划我们把其限定为弱NP-困难的．如果允许约束略为松弛，我们可以证明该问题存在完全多项式时间近似方案．