【摘要】研究了两个代理的单机排序问题。其中一个代理以工件总迟后相关的为目标函数(总迟后和加权总迟后),第二个代理以最大费用函数为目标函数。排序问题的目标就是寻找一个序列,使得在第二个代理的目标函数不超过给定的上界的情况下,第一个代理的目标函数最小。对于总迟后的情形,并给出拟多项式时间的动态规划算法。当第一个代理中的工件具有相等工期时,考虑了加权总迟后问题,并给出了一个多项式时间算法。最后对于总迟后问题给数值实验。