本文研究的是代理竞争排序问题。有两个代理人,它们分别拥有若干个工件共同在机器上加工。我们讨论的是代理竞争排序的约束优化模型,即目标在使一个代理的最大完工时间不超过某个常数的情形下,极小化另一个代理的最大完工时间。对工件是否带有到达时间的两种情形,我们分别证明了问题都是NP-hard的,分别提出了各自的近似算法,证明了算法在最坏情况下的性能比。　　 对于不带到达时间情形下的排序问题,我们假设其中一个代理的工件必须同时在m台机器上加工。针对这一情形,我们提出了近似算法,证明了算法在最坏情形下的性能比为2-12m,并且给出了紧的例子。　　 对于带到达时间情况的排序问题,我们分别对一个代理的工件加工是可中断的或不可中断的情形进行研究,并且假定其中一个代理的工件必须同时在m台机器上加工,而另一个代理的工件在若干台机器上同时加工。对于可中断的情形,我们给出了根据加工机器数优先的列表排序算法,证明了算法在最坏情形下的性能比为2-12m,且界是紧的。对于不可中断的情形,我们认为一个不可中断的最优值至少是可中断的最优值的两倍。　　 我们还讨论了可控加工时间的多代理竞争排序的复杂性。