本文主要研究了有多个代理（客户）的排序问题。在这样的问题中,存在着多个代理,每个代理拥有一个特定的工件集合。所有代理的工件都需要在相同的机器上被加工。每个代理的目标函数往往不同,且仅仅依赖于其自身工件的完工时间。我们的任务分三个方面：1)取各个代理目标函数的加权和作为一个总的目标函数,寻找使得总目标函数达到最小的工件序；2)在其它代理的目标函数值受限的条件下,寻找使得某个代理的目标函数达到最小的工件序；3)找到所有的非支配（nondominated）工件序,供决策者权衡各代理之间的利益得失以选择一个可以接受的序。这里的非支配序是指这样的一个序,若改变它使得一个或多个代理的目标函数值比现在小,那么改变以后的序中,必有其他一个或多个代理的目标函数值比现在大。本文第二章介绍了一个特殊的多代理问题：订单问题。订单问题中,每个订单是一个代理,m份订单共有n个工件需要在同一台机器上加工,这n个工件分属k个不同的类,当机器从加工某一类中的工件转向加工不同于它的第j类工件时,需要一个安装时间sj。问题是寻找一个使得m份订单的完工时间之和最小的加工顺序。这一章中,根据安装时间,订单完工的定义的不同,分了三种情形,分别给出了多项式时间算法,分支定界算法和一个启发式算法。第三章就离线和在线模式考虑了一个两代理单机排序问题。两个代理各有一个集合的独立的工件,在不同的时刻到达,或可中断,或不可中断,需要在同一台机器加工。两个代理都不同程度地希望尽早完工,取他们时间表长的加权和为考虑的目标函数。在离线模式下,工件可中断时有最优解；在线模式中,工件可中断时给出了一个竞争比为1+1/θ最优在线算法,不可中断时给出一个2+1/θ的在线算法。第四章又考虑了一个带类安装时间的问题,共两个代理,每个代理的目标均是最小化其时间表长。问题分成两种形式：第一种是求解限制最优问题,即在一个代理的时间表长受限的条件下寻找使得另一代理的时间表长最小的加工顺序,这个问题等价于我们定义的一个有尾巴的背包问题；第二种形式是研究其所有非支配序的数目和特征。第五章考虑了工件加工时间退化的两代理排序问题。工件的加工时间pj=bjt,t≥to,其中bj是工件j的退化率,t,to分别是工件j的开始加工时间和到达时间。考虑的目标有时间表长,总完工时间和最大延迟。每个代理任取一个作为其评价标准,取两个代理的评价标准的加权组合作为问题的目标函数。第五章就这样的六个组合分别给出了多项式算法。第六章考虑了这样的排序问题：有n个工件在同一时刻同时到达同一机器等待被加工,也希望在同一时刻完成加工。如某工件不能如期完工而延误了该工件的下道加工,则货主会向加工方索取赔偿；反之,如工件提前完工而使该工件可提前下道加工,则货主会给予加工方一定的奖励。因此,对加工方来说要降低成本需考虑一延误惩罚、超前有奖类目标函数,可记之为∑j=1n（αjTj-βjEj）。以此作为目标函数,考虑了工件加工时间同其开始加工时间有关且工件可拒加工的两个排序问题。对这两个排序问题,在指出它们的NP-hard性后,对它们作了详细分析并给出了相应算法。