排序作为近代应用数学的一个分支，有着深切的实际背景和广博的应用领域。主要是将生产、管理等事件中出现的一些运筹问题加以提炼，然后利用数学方法求解问题。它广泛应用于工厂，生产调度，管理科学，计算机科学和工程技术等众多领域。其本质是组合优化问题，即在问题的有限可行解集中求出最优解。但是在实际生产过程中，由于一些前提条件的限制导致某些排序问题得不到最优解；或者需要很长的运行时间和极大的存储空间才能找到最优解。为了求解实际问题，我们可以采用近似算法，即在较短的运行时间内得到问题的近似解来替代最优解。从而简化算法，降低时间复杂性。为了具有实用性，近似算法得到的近似解与最优解之间必须满足一定的误差精度。本文对两种机器模型的近似算法进行研究。　　本研究分为三个部分：第一章主要介绍排序问题的相关定义和三参数表示法，并介绍了几类排序问题的研究背景及本文在此基础之上的改进工作。第二章主要研究带有不可用区间工件中断可恢复的平行机排序问题。分别讨论了两种不同的目标函数。使最大的完工时间最小是其中一个目标函数。本章所考虑的第一个问题是一般意义下NP?困难的，因此需要寻找满足指定误差精度的近似解。在较短的运行时间内利用削减状态空间的方法设计了一个全多项式时间的近似方案)(FPTAS，并得到该问题的近似解。该近似方案具有强多项式的运行时间，算法的时间复杂性为O(n3/ε2)，这里n是输入工件的个数，ε是误差精度。另一个目标函数是使加权总完工时间最小。本章所考虑的第二个问题同样是一般意义下NP-困难的。为了找到满足指定误差精度的近似解，利用划分程序的方法得到了一个FPTAS。该算法的运行时间为O)(n5L5/ε4)，其中n为加工工件的个数，L为输入规模,ε为误差精度。第三章主要研究带有退化效应和拒绝的m台恒速机排序问题。工件具有退化效应和允许被拒绝。退化工件的加工时间是线性单增函数且与它的开始时间有关。目标函数是使最大的递送完成时间与被拒绝工件的总惩罚之和最小。这个问题是一般意义下NP?困难的，为了找到满足指定误差精度的近似解，利用凑整输入数据的方法得到了一个FPTAS。其时间复杂性为O(n2m-1Lm-1/εm-1)，其中n为加工工件的个数，L为输入规模,ε为误差精度。