排序是为加工若干工件而对资源按时间进行高效率分配.排序的好坏直接影响着费用的高低和利润的大小.在经典排序问题中，往往只有一个目标函数并且工件仅属于一个代理.本文研究几类两个代理单机排序问题.每个代理都有各自的工件集和与其对应的目标函数，它们共用一台机器来完成各自工件.每个代理都想让自己的目标函数最小化,并且这个目标函数只与工件完工时间有关.问题在于如何安排工件的加工次序以便满足各个代理对其目标函数的要求.本文主要研究以下几类问题：　　1)最小化总误工损失问题　　第一个代理的目标函数为总误工损失，第二个代理的目标函数为总完工时间或者总误工工件数.目的是找到一个排序，让第一个代理的目标函数值最小，并且保证另一个代理的目标函数值不超出给定上界.对于这两个排序问题，提出相应拟多项式时间算法.　　2)工件可拒绝的排序问题　　考虑第一个代理的目标函数分别是最大完工时间与总拒绝惩罚之和，最大延迟与总拒绝惩罚之和，总误工损失与总拒绝惩罚之和.第二个代理的目标函数均为总权误工工件数.对于这三种排序问题，证明它们是一般意义下的NP-难问题，并提出相应的拟多项式时间算法.　　3)带到达时间可中断的排序问题　　第一个代理中的工件有不同到达时间且允许中断，以总误工损失为目标函数;第二个代理中的工件不允许中断且被安排在固定时间窗口加工.给出这个排序问题的一个算法和时间复杂度.