排序是为加工若干工件而对资源按时间进行高效率分配.排序的好坏直接影响着费用的高低和利润的大小.在经典排序问题中,往往只有一个目标函数并且工件仅属于一个代理.本文研究两类两个代理在两台机器上的排序问题,每个代理都有各自的工件集和与其对应的目标函数,它们在两台机器上完成各自工件,每个代理都想让自己的目标函数最小化,并且这个目标函数只与工件完工时间有关.问题在于如何安排工件的加工次序以便满足各个代理对其目标函数的要求.本文主要研究以下两类问题:1)两个代理的最大完工时间ε函数问题目标函数是使一个代理的最大完工时间小于等于某一个常数时,另一个代理的最大完工时间最小化问题.对于这个问题,首先给出当代理B的的最大完工时间小于等于某一个常数,代理A的最大完工时间最小化的复杂性证明,然后根据最长它机加工时间优先排序(LAPT)规则,提供伪多项式算法,给出其复杂度.2)使最大完工时间的权重和函数最小化问题目标函数是使两个代理的最大完工时间的权重和函数最小化.对于这个问题,首先给出当代理B的权重是α时的最小化最大完工时间权重函数普通的复杂性证明,然后根据最长它机加工时间优先排序(LAPT)规则,提供伪多项式算法.最后,当权重系数为1时,给出一个近似算法;当权重系数大于1时,给出另一个近似算法.