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

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

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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

2 張蓮珠;;關于六角鏈的極值和排序問題的一些結果[A];中國運籌學會第六屆學術交流會論文集（上卷）[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ù)學規(guī)劃及運籌研討會論文集[C];2001年

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

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

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

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

9 樊保強;;帶倉儲約束的準時排序問題[A];中國運籌學會第九屆學術交流會論文集[C];2008年

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

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

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

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

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

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

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

4 張安;帶服務等級的在線排序問題及相關問題研究[D];浙江大學;2009年

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

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

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

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

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

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

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

1 董柳毅;與誤工有關的多目標排序問題[D];重慶師范大學;2009年

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

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

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

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

6 張兵權;單位加工時間的公共時間窗單機分組排序問題[D];浙江大學;2006年

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

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

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

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

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

本文編號：311208