排序问题是组合优化中经典的NP-困难问题之一，在许多文献中被广泛研究，所以对于这个问题的研究是设计它的近似算法.研究排序问题的方法涉及组合最优化理论的各个分支，如线性规划与整数规划、动态规划、最大流问题、匹配问题、计算复杂性理论等.排序问题中，一般指派问题是指在给定机器和工件的情况下，每个工件j在机器i上的加工时间和加工费用分别为cij，Pij.每台机器至多加工T单位的时间.我们需要决策每个工件在哪台机器上加工，在每台机器加工时间不超过T的条件下，使得总的加工费用最小.无关机排序问题是一般指派问题的一个特例，它只考虑每个工件的加工时间，即任何一个工件在任意一个机器上的加工费用为零.本文我们考虑通过一般指派问题的2-近似算法，给出无关机排序的一个更紧的界.　　在这篇文章中，首先我们在第一章介绍关于排序问题的研究背景及国内外研究现状和一些预备知识;其次，第二章中，我们介绍了一个关于极小化最大完工时间的无关机排序问题的常数近似算法;第三章我们介绍了Shmoys等人提出的一般指派问题的2-近似算法;最后，第四章中我们在一般指派问题的2-近似算法的基础上，给出了一个更好的无关机排序问题的算法，利用此算法得到的最大完工时间不会超过之前已有算法的最大完工时间2T.