本文關(guān)鍵詞：若干代理排序問題的近似算法研究，由筆耕文化傳播整理發(fā)布。

【摘要】：代理排序問題是近十年來發(fā)展的一類新興排序問題,與傳統(tǒng)排序問題不同,代理排序問題中的工件分別屬于兩個或多個不同的代理人,所有代理人有各自的目標(biāo),但共享加工資源。這類排序問題有許多實(shí)際應(yīng)用,所以受到越來越多研究者的關(guān)注。本文主要考慮一些代理排序問題的復(fù)雜性,近似算法以及在線算法,并分析算法的近似比或競爭比。 第一章主要介紹了組合優(yōu)化問題和排序問題的一些概念,以及代理排序問題的研究現(xiàn)狀。 第二章中,考慮同速機(jī)上兩代理排序問題的兩個模型。在這兩個模型中,其目標(biāo)分別為極小化代理A的時間表長和總完工時間和,同時代理B的時間表長不超過一個目標(biāo)值。證明了這兩個問題是NP-難的,并且可以在擬多項式時間內(nèi)解決。進(jìn)一步,分別對這兩個問題設(shè)計了完全多項式時間近似方案。 在第三章中,進(jìn)一步研究了第二章中的第一個模型,即極小化代理A的時間表長同時代理B的時間表長不超過一個目標(biāo)值,并且設(shè)計了兩個近似算法。當(dāng)機(jī)器臺數(shù)m任意時,設(shè)計了一個O(n)的算法,其性能比為2-1/m,即由該算法給出的代理A的時間表長不超過最優(yōu)值的2-1/m倍,同時代理B的時間表長不超過閥值的2-1/m倍,并且證明了這個比值證明是緊的。進(jìn)一步,當(dāng)m=2時,設(shè)計了一個O(n log n)算法,其性能比為(1+√17)/4≈1.28,小于3/2,并且該比值是弱緊的。 第四章研究了一個兩臺同速機(jī)上的多代理排序問題,每個代理的目標(biāo)為極小化時間表長。對于該問題,設(shè)計了一個(1+1/6,2+1/6,…,g+1/6)-近似算法。該算法可以得到一個時間表,它的第i個完成的代理的時間表長與其最小時間表長的比不超過i+1/6,并且證明了這個性能比向量是緊的。 第五章考慮了一個單機(jī)在線兩代理排序問題,兩個代理的工件適時到達(dá),其目標(biāo)為極小化兩代理的時間表長的線性組合,即CmaxA+θCmaxB,其中θ≥1。對于該問題,設(shè)計了一個競爭比為1+(2θ+θ2)/(2+2θ+θ2)在線算法。對于θ≤(1+√5)/2乎的特殊情形,設(shè)計了一個最好可能的在線算法。 最后,在第六章對本文做了總結(jié)和展望。
【關(guān)鍵詞】：代理排序 近似算法 性能比 在線算法 競爭比
【學(xué)位授予單位】：華東理工大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：O223
【目錄】：

• 摘要5-6
• Abstract6-10
• 第1章 緒論10-24
• 1.1 組合最優(yōu)化10
• 1.2 算法和計算復(fù)雜性10-14
• 1.3 排序問題簡介14-17
• 1.4 文獻(xiàn)綜述17-22
• 1.4.1 單機(jī)兩代理排序問題18-21
• 1.4.2 平行機(jī)與車間作業(yè)兩代理排序問題21-22
• 1.4.3 多代理排序問題22
• 1.5 論文概述22
• 1.6 文獻(xiàn)注記22-24
• 第2章 平行機(jī)上兩代理排序問題的近似方案24-34
• 2.1 引言24
• 2.2 兩代理的目標(biāo)都為極小化時間表長的模型24-29
• 2.2.1 動態(tài)規(guī)劃25-26
• 2.2.2 完全多項式時間近似方案26-29
• 2.3 兩代理的目標(biāo)分別為極小化總完工時間和時間表長的模型29-33
• 2.3.1 動態(tài)規(guī)劃30-31
• 2.3.2 完全多項式時間近似方案31-33
• 2.4 結(jié)論與討論33-34
• 第3章 極小化時間表長的平行機(jī)上兩代理排序問題的近似算法34-50
• 3.1 引言34
• 3.2 準(zhǔn)備工作34-35
• 3.3 一般情形的近似算法35-36
• 3.4 m=2情形下的近似算法36-49
• 3.5 結(jié)論與討論49-50
• 第4章 兩臺機(jī)上的多代理排序問題的近似算法50-62
• 4.1 引言50
• 4.2 近似算法50-53
• 4.3 性能分析53-61
• 4.4 結(jié)論與討論61-62
• 第5章 帶到達(dá)時間的單機(jī)兩代理排序問題的在線算法62-92
• 5.1 引言62
• 5.2 一般情形的在線算法62-76
• 5.3 θ≤((?)+1)/2情形下最好可能的在線算法76-92
• 第6章 總結(jié)與展望92-94
• 參考文獻(xiàn)94-102
• 致謝102-104
• 博士期間完成論文104

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 周泓,張惠民;求解多目標(biāo)作業(yè)排序問題的遺傳算法[J];系統(tǒng)工程理論與實(shí)踐;2001年08期

2 周泓,姬彬;求解作業(yè)排序問題的通用混合遺傳算法研究[J];系統(tǒng)工程理論與實(shí)踐;2001年12期

3 陳德伍,張 峰;一類新的可控排序問題(英文)[J];運(yùn)籌學(xué)學(xué)報;2001年04期

4 張瑞,劉國珍;單機(jī)排序問題最優(yōu)解方法[J];聊城師院學(xué)報(自然科學(xué)版);2001年02期

5 黎群;單臺機(jī)器多目標(biāo)作業(yè)排序問題的探討[J];系統(tǒng)工程理論方法應(yīng)用;2001年02期

6 方保昒,徐漢忠;用單親遺傳算法解具有窗口式交貨期的多機(jī)加工排序問題[J];系統(tǒng)工程理論方法應(yīng)用;2001年04期

7 宋政芳,孫世杰,吳春燕;一個超前有獎遲后受罰的排序問題(英文)[J];運(yùn)籌學(xué)學(xué)報;2002年04期

8 趙傳立,唐恒永;具有相關(guān)調(diào)整時間的排序問題[J];沈陽師范學(xué)院學(xué)報(自然科學(xué)版);2002年01期

9 鄭自途;關(guān)于"三臺以上機(jī)床作業(yè)排序問題"的算法[J];天津理工學(xué)院學(xué)報;2002年04期

10 張玉忠,苗翠霞;復(fù)制法及其在分批排序問題中的應(yīng)用[J];曲阜師范大學(xué)學(xué)報(自然科學(xué)版);2004年02期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 柏孟卓;唐國春;;加工時間可控的同時加工排序問題[A];2006年中國運(yùn)籌學(xué)會數(shù)學(xué)規(guī)劃分會代表會議暨第六屆學(xué)術(shù)會議論文集[C];2006年

2 張蓮珠;;關(guān)于六角鏈的極值和排序問題的一些結(jié)果[A];中國運(yùn)籌學(xué)會第六屆學(xué)術(shù)交流會論文集（上卷）[C];2000年

3 周支立;李懷祖;;有重疊區(qū)域的兩抓鉤周期性排序問題的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孫世杰;陳躍;;參數(shù)可控的排序問題[A];2001年全國數(shù)學(xué)規(guī)劃及運(yùn)籌研討會論文集[C];2001年

5 張玉忠;;分批排序問題研究[A];中國運(yùn)籌學(xué)會第七屆學(xué)術(shù)交流會論文集（上卷）[C];2004年

6 張玉忠;;分批排序問題研究[A];中國運(yùn)籌學(xué)會第七屆學(xué)術(shù)交流會論文集（中卷）[C];2004年

7 譚萬達(dá);;二元對比排序中的最少逆序原理[A];中國系統(tǒng)工程學(xué)會模糊數(shù)學(xué)與模糊系統(tǒng)委員會第五屆年會論文選集[C];1990年

8 呂緒華;楊漢興;;求解裝配式排序問題的歸并算法及其性能比研究[A];中國運(yùn)籌學(xué)會第六屆學(xué)術(shù)交流會論文集（下卷）[C];2000年

9 樊保強(qiáng);;帶倉儲約束的準(zhǔn)時排序問題[A];中國運(yùn)籌學(xué)會第九屆學(xué)術(shù)交流會論文集[C];2008年

10 陳榮軍;唐國春;;自由作業(yè)環(huán)境下的供應(yīng)鏈排序問題[A];中國運(yùn)籌學(xué)會第九屆學(xué)術(shù)交流會論文集[C];2008年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 山東 趙玉勇;數(shù)組，你的規(guī)律機(jī)器[N];電腦報;2004年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 仲維亞;供應(yīng)鏈管理中的若干排序問題研究[D];浙江大學(xué);2008年

2 尹曉;基因組重組排序問題的算法研究[D];山東大學(xué);2010年

3 余煒;若干網(wǎng)絡(luò)排序問題的算法和復(fù)雜性研究[D];華東理工大學(xué);2010年

4 張安;帶服務(wù)等級的在線排序問題及相關(guān)問題研究[D];浙江大學(xué);2009年

5 鄭睿;鋼鐵生產(chǎn)中的批處理機(jī)作業(yè)排序問題算法研究[D];復(fù)旦大學(xué);2009年

6 季敏;當(dāng)代工業(yè)中的若干排序問題研究[D];浙江大學(xué);2006年

7 李好好;若干排序問題研究[D];浙江大學(xué);2014年

8 丁國生;多代理競爭排序問題的研究[D];上海大學(xué);2009年

9 葉德仕;通訊網(wǎng)絡(luò)中排序問題的若干在線和高性能算法[D];浙江大學(xué);2005年

10 王成飛;幾類新型在線分批排序問題[D];曲阜師范大學(xué);2011年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 董柳毅;與誤工有關(guān)的多目標(biāo)排序問題[D];重慶師范大學(xué);2009年

2 王迅娣;成組加工排序和供應(yīng)鏈在線排序問題[D];曲阜師范大學(xué);2010年

3 王潔明;有關(guān)代理競爭排序問題的研究[D];華東理工大學(xué);2011年

4 劉麗麗;分批排序問題[D];曲阜師范大學(xué);2000年

5 鄢楚楠;2，4-逆序變換的置換排序問題[D];浙江大學(xué);2006年

6 張兵權(quán);單位加工時間的公共時間窗單機(jī)分組排序問題[D];浙江大學(xué);2006年

7 姜冠成;分批排序問題和資源約束排序問題[D];蘇州大學(xué);2005年

8 胡榮;一類分裝式排序問題的計算方法和計算復(fù)雜性研究[D];武漢科技大學(xué);2006年

9 馬蕾;帶傳遞時間的通信模型中的樹約束排序問題[D];蘭州大學(xué);2007年

10 王小明;不允許等待的混合流水兩車間排序問題[D];清華大學(xué);2002年

  本文關(guān)鍵詞：若干代理排序問題的近似算法研究，，由筆耕文化傳播整理發(fā)布。

本文編號：311208