随着社会的进步和经济的发展，机器排序问题在我们工作和生活中的应用越来越多.它已成为运筹学和组合最优化中最重要的研究领域之一.大多数经典排序文献所考虑的工件仅属于一个代理.在实际应用中，被加工的工件往往属于不同的代理.为了满足不同代理的需要，决策者需要在多个代理的利益之间进行平衡.这就产生了多代理排序.　　 多个代理的机器排序问题可以描述如下:有k个代理，分别有各自的工件集Jx={Jx1，…，Jxnx}（1≤x≤k），并且n=∑ki=1ni.每一工件Jxi的加工时间、工期和权重分别为pxi、dxi和wxi（1≤i≤ni）.有m台机器，代理们必须在共同的加工资源（即m台机器）上来加工他们的工件.每个代理都想最小化自己的目标函数.本学位论文主要研究了以下排序问题.　　 在第二章中，我们考虑了两个代理的平行批处理机上的机器排序中的两个问题.第一个问题是批容量无界的平行批排序问题，第二个问题是批容量有界的平行批排序问题，其中一个代理以工件的最大完工时间为目标函数，另外一个代理以他的工件的最大延迟为目标函数.排序目标是使得两个代理的目标函数的线性加权和最小.对这两个问题，在生成两个代理的目标的所有的Pareto最优点的基础上，我们均给出了多项式时间算法.　　 在第三章中，我们考虑了工件可拒绝的两个代理的单机排序问题.在该问题中，我们有两个代理A和B，分别具有工件集JA和JB.对于每个代理来说，其工件可以被接收从而放在机器上加工，也可以被拒绝但要支付一定的拒绝费用.在满足代理B的接收工件的目标函数fB与他的所有的被拒绝工件的总的拒绝费用之和不超过给定的数值Q(Q＞0)的前提下，排序目标是使代理A的接收工件的目标函数fA与他的所有的被拒绝工件的总的拒绝费用之和最小，其中fA和fB分别是各自工件完工时间的非减函数.当两个代理取不同的目标函数时，我们证明了问题是NP-困难的.当两个代理分别以工件的最大完工时间、最大延迟、加权完工时间和及加权误工工件数为目标函数时，我们分别给出对应问题的拟多项式时间算法，同时，当代理A以他的工件的最大完工时间为目标函数，代理B以他的工件的最大延迟为目标函数，并且代理B的所有的工件都被接收时，我们分别给出一个动态规划算法，一个2-近似算法和一个全多项式时间近似方案(FPTAS).　　 在第四章中，我们考虑了带有维修区间的两个代理的单机排序问题.在该问题中，机器上有一些维修区间而使得机器在这一时间段内不能使用.这两个代理的工件不得不在剩余的区间上加工.排序目标是最小化两个代理目标的线性组合.当两个代理分别取不同的目标函数:最大完工时间，最大延迟，所有工件的加权完工时间和，所有工件的总的误工等，我们分别给出对应问题的多项式时间算法或拟多项式时间算法.　　 在第五章中，我们考虑了具有提前费用的多个代理的单机排序中的三个问题.　　 (1)第一个问题中，我们有k=2个代理，其中第一个代理的工件的加工时间都相等，并且两个代理的工件的工期都相等.第一个代理的目标函数是工件的加权提前和，第二个代理的目标函数是他的工件的最大提前.目标是找一个最优排序使第一个代理的工件的加权提前和最小使得第二个代理的工件的最大提前不超过固定的值.对该问题，我们给出一个多项式时间算法.　　 (2)第二个问题中，我们有k个代理.前k-1个代理的目标函数是各自工件的最大提前，第k个代理的工件的工期相等，并且目标函数是工件的总的提前.目标是寻找一个最优排序使第k个代理的工件的总的提前最小使得前k-1个代理的各自工件的最大提前不超过给定的上界.对该问题我们给出了一个多项式时间算法.　　 (3)第三个问题中，我们有k=2个代理.每个代理的工件有一个工件提前的非减费用函数.每个代理以各自的最大费用函数为目标函数.对该问题，我们分析了关于两个代理的目标函数的所有Pareto最优解.　　 在第六章中，我们考虑了m台平行机上带有维修区间的列表在线排序问题.如果一个工件在加工完之前遇到维修区间，则等机器被维修完之后该工件需要重新加工.我们称这种情形是“不可中断的”.排序的目标函数是工件的最大完工时间.当m=2且维修区间的长度小于或等于工件的最大加工长度时，我们给出该问题的竞争比的下界是2.79129，并给出一个竞争比是2.79633的在线算法.当机器台数m≥4时，我们证明了若维修区间的长度大于工件的最大加工长度，没有竞争比为常数的在线算法;假如维修区间的长度小于或等于工件的最大加工长度，不存在竞争比小于3的在线算法.并且给出一个竞争比是4-1/m的在线算法.