排序问题本质是一类组合最优化问题，即要找到一个最优算法来求出该问题的最优解。对于几类经典排序问题，已经找到最优算法并且获得最优解。但在实际生产生活中，由于某些前提因素的限制和新增加的一些变量导致一些排序问题得不到最优解；或者需在相当大的运行时间内才能找到最优解（如动态规划算法），这些都不是我们想要的结果，为了能在较短的运行时间内解决此类排序问题，我们利用较好的算法得到的近似解来替代最优解。本文对几类排序问题的近似算法进行研究。主要内容为：　　第一章主要对排序问题的定义和三参数表示法进行描述，并介绍几类排序问题的研究背景及本文在此基础上所做的工作。　　第二章主要研究带有拒绝工件和机器维修区间的单机排序问题。目标是找到一个全多项式近似方案(FPTAS)，在该方案下得到近似解使满足一定的误差要求，同时给出该近似方案的时间复杂性为O(n2/ε2)。　　第三章主要研究带有退化工件和机器维修区间的单机排序问题。考虑的是单机上工件允许被拒绝，工件的加工时间是关于它的开工时间的线性单增函数且机器在某时间段内不能连续进行加工的排序问题。目的是找到最优解极小化问题(公式略)。对此问题给出了一个FPTAS，其时间复杂性为O(n4L3/ε2)。　　第四章主要研究带有退化工件和机器维修区间的平行机排序问题。目标是找到一个近似解使满足一定的误差要求。该问题是NP-难的，对此给出一个全多项式近似方案(FPTAS)，时间复杂性为O(n6L6/ε2)。