论文部分内容阅读
Pareto优化排序(又称trade-off排序)是排序论领域中的一个重要研究方向。它综合考虑多个性能指标,并在这些性能指标之间进行有效折衷。Pareto优化排序旨在枚举所有的Pareto最优点,并为每个Pareto最优点找到一个对应的Pareto最优排序。Pareto优化排序的特点是理论难度大而应用性强。当我们找到一个Pareto优化排序问题的所有Pareto最优点之后,决策人员就可以据此并结合实际需求制定合理的生产计划。因此,Pareto优化排序的研究具有重要的理论意义和广阔的应用前景。本学位论文研究了若干Pareto优化排序问题。学位论文共分六章：·第一章简述了排序论的应用背景、发展历程、常用记号和术语等,重点介绍了Pareto优化排序的基本理论与方法,并对与本文相关的一些研究结果进行了综述。·第二章研究了无界平行批Pareto优化排序问题1|p-batch,b≥n|#(Cmax,fmax),给出了一个O(n4)-时间算法,并通过构造实例说明,由He等人[29]建立的关于Pareto最优点个数的上界n(n-1)/2+1是紧的。·第三章研究了带分族工件的无界平行批排序问题1|p-batch,family-job,b≥ n|#(Cmax,Lmax)对该问题的一般情形给出了一个O(n2K|1)-时间算法。当工件族个数K为固定常数时,我们设计的算法是多项式时间算法。同时,我们也证明了问题1|p-batch,family-job,b≥n|#(Cmax,Lmax)至多有O(nK+1)个Pareto最优点。·第四章研究了带分族工件和工件到达时间的无界平行批Pareto优化排序问题1|p-batch,family-job,b≥n,rj|#(Cmax,Fmax)当工件族个数K是任意整数时,我们证明了单指标问题1|p-batch,family-job,b≥n,rj|Fmax是强NP-困难的；当工件族个数K是固定常数时,我们给出了问题1|p-batch,family-job,b≥ n,rj|#(Cmax,Fmax)的一个O(n3K+3)-时间算法。·第五章研究了如下五个相关联的继列批排序问题：(Ⅰ)1|s-batch,b< n|#(Cmax,fmax),(Ⅱ)1|(?),s-batch,b=2|Lmax,(Ⅲ)1|(?),s-batch,b=2|Lmax(Ⅳ)1|(?),s-batch,b≥n|#(Cmax,fmax),(Ⅴ)1|(?),s-batch,b≥n|#(Cmax,Lmax).我们对问题(Ⅰ)和(Ⅳ)分别给出了O(n4)-时间算法；对问题(V)给出一个O(n2)-时间算法；同时,也证明了问题(Ⅱ)和(Ⅲ)都是强NP-困难的。·第六章研究了两代理Pareto优化排序问题1||#(∑CjA,fmax),其中,∑CjA表示代理A的工件的完工时间和,fmax表示所有工件的最大费用,也被称为全局目标函数。对该问题,我们给出一个O(n4)-时间算法。当fmax=Lmax时,算法的时间复杂性可以降至O(n3logn).同时,我们也证明了问题1||#(∑CjA,fmax)至多有O(n2)个Pareto最优点。