Pareto优化排序问题研究

发布时间:2018-02-02 19:43

  本文关键词: 排序 Pareto最优点 平行批 继列批 分族工件 两代理 多项式时间算法 出处:《郑州大学》2016年博士论文 论文类型:学位论文


【摘要】: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最优点。
[Abstract]:Pareto optimal sorting (also known as trade-off sorting) is an important research direction in the field of sorting theory. It synthetically considers multiple performance indexes and makes an effective compromise between them. Pareto optimal sorting aims to enumerate all the best of Pareto. And find a corresponding Pareto optimal sort for each Pareto. Pareto optimal sorting is characterized by its theoretical difficulty and strong application. When we find all the best Pareto advantages of a Pareto optimization scheduling problem, The decision makers can make reasonable production plan according to the actual demand. Therefore, the research of Pareto optimization scheduling has important theoretical significance and broad application prospect. This dissertation studies some Pareto optimization scheduling questions. Title. Thesis is divided into six chapters: 路Chapter 1 briefly introduces the application background of ranking theory, In this paper, the basic theory and method of Pareto optimal ranking are introduced. In the second chapter, we study the optimization scheduling problem of unbounded parallel batches Pareto (1 p-batchnib 鈮,

本文编号:1485320

资料下载
论文发表

本文链接:https://www.wllwen.com/shoufeilunwen/jckxbs/1485320.html


Copyright(c)文论论文网All Rights Reserved | 网站地图 |

版权申明:资料由用户136c1***提供,本站仅收录摘要或目录,作者需要删除请E-mail邮箱bigeng88@qq.com