冯 琪，孟金涛，郑玉晖

（1．中原工学院，郑州450007；2．郑州航空工业管理学院，郑州450015）

两个代理的单机排序问题研究

冯 琪1，孟金涛2，郑玉晖1

（1．中原工学院，郑州450007；2．郑州航空工业管理学院，郑州450015）

研究了两个代理的单机排序问题．其中第一个代理以完工时间和为目标函数，第二个代理以误工工件个数为目标函数．排序问题的目标是寻找一种排序，使得在第二个代理的目标函数不超过给定上界的情况下，第一个代理的目标函数最小．本文还对这一问题设计了一个拟多项式时间算法．

排序；两个代理；拟多项式时间算法

广义而言，排序问题可以理解为“最优地分配资源于时间区间去完成一定的任务”．其中，资源可以有不同的种类，例如人力、物力、机器、能源及工具等资源；任务也有各种解释，如从制造系统的机器加工到计算机系统的信息处理等．但是任务具有相同的特性，它们都有准备时间、交工期限、权重、任务之间的先后约束以及描述完成任务与资源分配之间依赖关系的目标函数．因此，我们可以一般性地将排序问题看成是“最优地分配机器的时间去加工一些工件”．排序问题产生的背景主要是机器制造，后来被广泛应用于服务业、制造业、运输业、管理、计算机科学等领域．

所谓多代理（客户）排序，是指有多个代理（客户），每一个代理都有各自的工件集和各自的目标函数，并且所有代理的工件竞争使用共同的资源．它有广泛的应用，例如在一些共同……