工件有到达时间的多代理排序问题

论文摘要

所谓排序,就是在一定的约束条件下分配时间资源去完成一些任务,使一个或多个目标达到最优.近年来,多代理排序问题越来越引起国际同行的重视,这是排序论研究中发展比较迅速的—个排序模型.在多代理排序模型中,多个代理商互相竞争使用一个公共的加工资源,代理商之间在加工各自的工件时互相影响,在关于公共资源的使用上互相协商.本文主要研究了有两个代理的排序问题:有两个代理,每个都有一个工件集合.两个代理商都想在一个公共资源上加工自己的工件,并希望最小化各自的目标函数,这个目标函数只和各自工件的完工时间有关.因此,问题是,如何安排工件的加工顺序,使得在支持两个代理商之间的协商的基础上,使各自的目标函数尽可能小.本文中,我们考虑一种特殊的两个代理排序模型.要求在对一个代理商的目标函数值可以接受的条件下使得另一个代理商的目标函数达到最小.我们将两个代理商记为A和B,代理商A的工件集记为JA,代理商B的工件集记为JB.设JA={J1A, J2A,…,JnAA},JB = {J1B, J2B,…,JnBB}.我们称这两个工件集中的工件分别为A-工件和B-工件.进二步假设B-工件有非负的到达时间,记为rjB,而A-工件的到达时间为0.两个代理的目标函数均是最大完工时间.于是,我们考虑的模型可记为:（?）,其中,CmaxA和CmaxB分别对应A和B的目标函数,也就是说,我们的目标是要找一个可行排序σ使得在保证B-工件的最大完工时间不超过一个固定值（代理商B的可接受条件）的前提下A-工件的最大完工时间最小.在Agnetis等人（2004）（Scheduling Problems with Two competing Agents）的文章中,并没有考虑工件的到达时间.因此,本文的研究是对已有文献的进一步发展.本文的主要结论如下:（1）证明了问题（?）在一般意义下是NP-困难的.（2）给出了问题（?）的拟多项式时间最优的算法.（3）给出了问题（?）的全多项式时间的近似方案.（4）证明了问题（?）在一般意义下是NP-困难的.

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 排序的介绍
• 1.2 多代理排序
• 1.3 排序的记号
• 1.4 相关结果
• 1.5 本文主要结果
• 第二章 带有到达时间的多代理排序问题
• 2.1 预备知识
• 2.2 带有到达时间的多代理排序问题
• 后记
• 参考文献
• 致谢