排序理沦是组合优化这门学科的一个重要组成部分，有着深刻的实际背景和广阔的应用前景．随着现代工业的发展，经典的排序模式已被突破，新的模式层出不穷，离散可控排序就是发展最为迅速的新方向之一．经典排序模式中的工件之间带有前后约束的延误排序问题是NP困难的．本文就离散加工时间的可控排序、离散到达时间的可控排序和延误排序中的五个模型做了如下工作． 一．离散可控排序1．本文首次研究了离散加工时间的可控排序中，目标函数是有限的总压缩费用(总压缩费用约束)下极小化最大完工时间，单机，工件有不同到达时间，即1|r<,j>，dm| C<,max>/TPC问题，我们设计了伪多项式时间的动态规划算法，并给出了相应的FPTAS算法． 2．本文首次研究了离散加工时间的可控排序中，目标函数是有限的总压缩费用(总压缩费用约束)下极小化最大完工时间，同型机，工件到达时间都相同，即P<,M>|dm|C<,max>/TPC问题，我们设计了伪多项式时间的动态规划算法，并给出了相应的FPTAS算法． 3．本文首次研究了离散到达时间的可控排序中，目标函数是极小化总压缩费用与最大完工时间之和，单机，即1|r<,j>,dr|C<,max>+TRC问题，我们指明了其强NP-困难性，并且我们设计了在给定任意序下如何选择到达时间的一个最优算法，从而得出这个问题存在最差性能比是2的近似算法． 二．延误排序 1．虽然对于不带前后约束的延误排序已经有许多近似算法，其中包括后移算法．然而，迄今为止，对于带有前后约束的延误排序的近似算法在国内外还没有见过报道．对问题1|prec|∑T<,j>，我们把不带前后约束的延误排序的后移算法移植到工件之间带有前后约束的情况，提出一个多项式时间的近似算法．这个算法可以快速地得到这种延误问题的近似解． 2．Emmons条件在求解单台机器延误问题中起着十分重要的作用，本文对陶霖和唐国春提出的弱于Emmons条件的所谓改进的Emmons条件的证明再进一步改进，简化，并完善了相应的预排序算法．