论文部分内容阅读
排序问题在管理科学、计算科学和控制科学等领域有广泛的应用,代理排序问题则是近十年兴起的。代理排序可以利用博弈论的基本方法来对各个代理的目标进行权衡;也可以利用组合优化方法,将多目标问题转化为约束限制优化问题、Pareto最优问题或单目标优化问题。本文主要基于两代理排序的约束限制优化模型,研究单机和平行机环境下的两代理排序问题。 对于单机环境,我们研究了工件具有达到时间、目标函数均为最大完工时间的两代理排序问题。我们利用划分问题证明了该问题是NP-hard的,然后为其设计了限制情形的PTAS。对于平行机环境,我们首先研究了m台平行机两个代理目标函数均为完工时间和的问题,设计了该问题的拟多项式时间算法,并由此说明了该问题是普通意义下NP-hard的,而且基于拟多项式时间算法,给出了该问题限制情形下的FPTAS。最后我们考虑了平行机台数m不作为输入参数、两个代理目标函数均为最大完工时间的两代理排序问题。基于物体尺寸为有限个的装箱问题的动态规划算法,我们给出了限制情形下两代理排序问题的PTAS。