本文關(guān)鍵詞： 排序 Pareto最優(yōu)點(diǎn) 平行批 繼列批 分族工件 兩代理 多項(xiàng)式時(shí)間算法　出處：《鄭州大學(xué)》2016年博士論文　論文類(lèi)型：學(xué)位論文

【摘要】：Pareto優(yōu)化排序(又稱trade-off排序)是排序論領(lǐng)域中的一個(gè)重要研究方向。它綜合考慮多個(gè)性能指標(biāo),并在這些性能指標(biāo)之間進(jìn)行有效折衷。Pareto優(yōu)化排序旨在枚舉所有的Pareto最優(yōu)點(diǎn),并為每個(gè)Pareto最優(yōu)點(diǎn)找到一個(gè)對(duì)應(yīng)的Pareto最優(yōu)排序。Pareto優(yōu)化排序的特點(diǎn)是理論難度大而應(yīng)用性強(qiáng)。當(dāng)我們找到一個(gè)Pareto優(yōu)化排序問(wèn)題的所有Pareto最優(yōu)點(diǎn)之后,決策人員就可以據(jù)此并結(jié)合實(shí)際需求制定合理的生產(chǎn)計(jì)劃。因此,Pareto優(yōu)化排序的研究具有重要的理論意義和廣闊的應(yīng)用前景。本學(xué)位論文研究了若干Pareto優(yōu)化排序問(wèn)題。學(xué)位論文共分六章：·第一章簡(jiǎn)述了排序論的應(yīng)用背景、發(fā)展歷程、常用記號(hào)和術(shù)語(yǔ)等,重點(diǎn)介紹了Pareto優(yōu)化排序的基本理論與方法,并對(duì)與本文相關(guān)的一些研究結(jié)果進(jìn)行了綜述�！さ诙卵芯苛藷o(wú)界平行批Pareto優(yōu)化排序問(wèn)題1|p-batch,b≥n|#(Cmax,fmax),給出了一個(gè)O(n4)-時(shí)間算法,并通過(guò)構(gòu)造實(shí)例說(shuō)明,由He等人[29]建立的關(guān)于Pareto最優(yōu)點(diǎn)個(gè)數(shù)的上界n(n-1)/2+1是緊的。·第三章研究了帶分族工件的無(wú)界平行批排序問(wèn)題1|p-batch,family-job,b≥ n|#(Cmax,Lmax)對(duì)該問(wèn)題的一般情形給出了一個(gè)O(n2K|1)-時(shí)間算法。當(dāng)工件族個(gè)數(shù)K為固定常數(shù)時(shí),我們?cè)O(shè)計(jì)的算法是多項(xiàng)式時(shí)間算法。同時(shí),我們也證明了問(wèn)題1|p-batch,family-job,b≥n|#(Cmax,Lmax)至多有O(nK+1)個(gè)Pareto最優(yōu)點(diǎn)�！さ谒恼卵芯苛藥Х肿骞ぜ凸ぜ竭_(dá)時(shí)間的無(wú)界平行批Pareto優(yōu)化排序問(wèn)題1|p-batch,family-job,b≥n,rj|#(Cmax,Fmax)當(dāng)工件族個(gè)數(shù)K是任意整數(shù)時(shí),我們證明了單指標(biāo)問(wèn)題1|p-batch,family-job,b≥n,rj|Fmax是強(qiáng)NP-困難的；當(dāng)工件族個(gè)數(shù)K是固定常數(shù)時(shí),我們給出了問(wèn)題1|p-batch,family-job,b≥ n,rj|#(Cmax,Fmax)的一個(gè)O(n3K+3)-時(shí)間算法�！さ谖逭卵芯苛巳缦挛鍌�(gè)相關(guān)聯(lián)的繼列批排序問(wèn)題：(Ⅰ)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).我們對(duì)問(wèn)題(Ⅰ)和(Ⅳ)分別給出了O(n4)-時(shí)間算法；對(duì)問(wèn)題(V)給出一個(gè)O(n2)-時(shí)間算法；同時(shí),也證明了問(wèn)題(Ⅱ)和(Ⅲ)都是強(qiáng)NP-困難的�！さ诹卵芯苛藘纱鞵areto優(yōu)化排序問(wèn)題1||#(∑CjA,fmax),其中,∑CjA表示代理A的工件的完工時(shí)間和,fmax表示所有工件的最大費(fèi)用,也被稱為全局目標(biāo)函數(shù)。對(duì)該問(wèn)題,我們給出一個(gè)O(n4)-時(shí)間算法。當(dāng)fmax=Lmax時(shí),算法的時(shí)間復(fù)雜性可以降至O(n3logn).同時(shí),我們也證明了問(wèn)題1||#(∑CjA,fmax)至多有O(n2)個(gè)Pareto最優(yōu)點(diǎn)。
[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 鈮，

本文編號(hào)：1485320