排序问题是一类重要的组合优化问题,随着在实际领域的应用以及理论研究方面的不断深入,衍生出各种不同类型的排序问题模型。本文主要研究几类不同的排序问题,侧重于不同模型下近似算法的设计以及算法的最坏情况界估计。本文总共分为五章。第一章对组合优化问题、排序问题以及算法复杂性的相关概念作了简单介绍,然后对主要工作成果进行了梳理。第二章讨论m台平行机上极小化完工时间平方和问题Pm‖∑Gj2。我们利用非凸二次规划估计GSPT算法给出的排序目标值,进而给出了GSPT算法解决该问题的最坏情况界,当m为偶数时,最坏情况界为当m为奇数时,最坏情况界为第三章研究工件加工部分可分的平行机排序问题。工件可被分割成加工时间为整数的若干部分,同一工件的不同部分可在同一时刻于不同机器上加工,目标为极小化加权总完工时间。我们给出了一个最坏情况界为4/3近似算法。第四章在保密计算的框架之下研究两类经典的排序问题Pm‖Cmax与Bm||Cmax。在以上问题中,工件分属于不同的单位,不同单位相互之间也不希望泄漏彼此保有的信息。我们的工作实现了在不暴露隐私的前提下将问题转化为可以公开的排序问题,并且在求解公开的排序问题之后,各单位能够给出自己的加工策略,以使多方能安全合作。第五章探讨两类随机排序问题1‖∑Uj和F2|dj=d|ΣUj。对工件加工时间所服从的正态分布和伽马分布作了比文献已有研究更一般的假设,设计了相应的算法。初步的数值试验保证了所得算法的有效性