代理排序问题是近十年来发展的一类新兴排序问题，与传统排序问题不同，代理排序问题中的工件分别属于两个或多个不同的代理人，所有代理人有各自的目标，但共享加工资源。这类排序问题有许多实际应用，所以受到越来越多研究者的关注。本文主要考虑一些代理排序问题的复杂性，近似算法以及在线算法，并分析算法的近似比或竞争比。　　第一章主要介绍了组合优化问题和排序问题的一些概念，以及代理排序问题的研究现状。　　第二章中，考虑同速机上两代理排序问题的两个模型。在这两个模型中，其目标分别为极小化代理A的时间表长和总完工时间和，同时代理B的时间表长不超过一个目标值。证明了这两个问题是NP-难的，并且可以在拟多项式时间内解决。进一步，分别对这两个问题设计了完全多项式时间近似方案。　　在第三章中，进一步研究了第二章中的第一个模型，即极小化代理A的时间表长同时代理B的时间表长不超过一个目标值，并且设计了两个近似算法。当机器台数m任意时，设计了一个O(n)的算法，其性能比为2-1/m，即由该算法给出的代理A的时间表长不超过最优值的2-1倍，同时代理B的时间表长不超过阀值的2-1/m倍，并且证明了这个比值证明是紧的。进一步，当m=2时，设计了一个O(nlogn)算法，其性能比为1+√17/4≈1.28，小于3/2，并且该比值是弱紧的。　　第四章研究了一个两台同速机上的多代理排序问题，每个代理的目标为极小化时间表长。对于该问题，设计了一个（1+1/6，2+1/6，…，g+1/6）-近似算法。该算法可以得到一个时间表，它的第i个完成的代理的时间表长与其最小时间表长的比不超过i+1/6，并且证明了这个性能比向量是紧的。　　第五章考虑了一个单机在线两代理排序问题，两个代理的工件适时到达，其目标为极小化两代理的时间表长的线性组合，即CAmax+θCBmax，其中θ≥1。对于该问题，设计了一个竞争比为1+2θ+θ2/2+2θ+θ2在线算法。对于θ≤1+√5/2的特殊情形，设计了一个最好可能的在线算法。　　最后，在第六章对本文做了总结和展望。