發(fā)布時間：2020-07-21 10:28

【摘要】：排序問題是一類重要的組合優(yōu)化問題,隨著實際應用和理論研究的不斷深入,產(chǎn)生了各種不同的排序問題模型.本文主要研究經(jīng)典平行機在線、半在線排序問題和單臺機上的批排序問題,側(cè)重于不同模型下近似算法的設計以及最壞情況分析.本文共分為五章.第一章是緒論,主要介紹了組合優(yōu)化問題、排序問題、算法及計算復雜性、在線問題的基本概念,列舉了本文的主要成果.第二章和第三章研究經(jīng)典的同型機以極小化工件的最大完工時間為目標的在線排序問題.由目前在線算法證明過程中對最優(yōu)解最大完工時間的估計方式的局限性,引入了偽下界的概念.對于任意的機器數(shù)m,給出了該問題的偽下界和一個新的算法.機器臺數(shù)在4至11之間時,算法是偽最優(yōu)的,即其競爭比等于偽下界.其中機器臺數(shù)在7至11之間的偽最優(yōu)算法為首次得到.第四章研究已知工件總加工時間的兩臺同型機以極小化工件的最大完工時間為目標的半在線排序問題.給出了一個隨機算法,并且證明了它的競爭比不超過5/4.該值小于該問題的確定性下界4/3.第五章研究工件大小不同,但加工時間相同,以極小化工件總完工時間為目標的批排序問題.證明了FFD算法的最壞情況比無界,FFI算法的最壞情況比在109/82和3/2之間.此外,還引入了兩個啟發(fā)式算法,并進行了數(shù)值試驗和分析.
【學位授予單位】：浙江大學
【學位級別】：博士
【學位授予年份】：2018
【分類號】：O223
【圖文】：

由于對于某些實例，通過不同算法給出的排序可能相等，這些百分比的和可能大逡逑于１．逡逑由表５．３和圖５．１，圖５．２，我們發(fā)現(xiàn)算法的優(yōu)劣和工件大小所在的區(qū)間密切相逡逑關．５７？的表現(xiàn)要比ＦＦ域ＦＦＤ的差．很少有實例使得５７？的表現(xiàn)能比ＦＦ１或ＦＦＤ更逡逑好．當工件的大小更接近的時候，ＣＯＭ會明顯的比其他算法更好．對于這三組同逡逑樣長度的區(qū)間而言，ｃｏｍ在區(qū)間的表現(xiàn)要比區(qū)間更好，區(qū)間比逡逑區(qū)間好，區(qū)間比區(qū)間ｈｉ］好．然而，我們對于平均情況界的估計基于逡逑最優(yōu)解的下界ｒＧ．我們并不知道這種現(xiàn)象是否是由ｒｃｉ和７Ｙ７＊之間的差異產(chǎn)生逡逑的．逡逑關于ＦＦＩ與ＦＦＤ之間的比較也十分有趣，這和最優(yōu)解下界的選取無關．注意逡逑到即使所有的工件都被限制在很小的情況下，ＦＦＤ仍是無界的，而ＦＨ的最壞情逡逑況比不超過１．５．就這七個區(qū)間而言，ＦＦＩ在區(qū)間［０，幻和［Ｏ，＾，也就是沒有工件逡逑大小超過！的區(qū)間中表現(xiàn)明顯要優(yōu)于ＦＦＤ．另一方面，ＦＦＤ在三個以ＬＳ邋＝邋｜作為逡逑左端點的區(qū)間

—＃－ＦＦＩ邋－？－ＦＦ0邋＇ＳＲ邋——ＣＯＭ逡逑圖５．１：不同ｎ的平均競爭比逡逑—個區(qū)間，ＦＦＩ的平均競爭比總是增加．ＦＦＤ的平均競爭比則是在［０，１］增加，其余逡逑的減少．在這兩個因素的影響下，區(qū)間［０，引的性質(zhì)更是十分有趣，ＦＦＩ在ｎ邋＝邋２０逡逑時優(yōu)于ＦＦＤ，而在其他情況下均不如ＦＦＤ邋．逡逑

【相似文獻】

相關期刊論文 前10條

1 韓飛;;高中數(shù)學一道數(shù)列典型題解法的探究[J];數(shù)學學習與研究;2016年23期

2 豆俊梅;孫彩賢;;單機排序問題的研究[J];數(shù)學學習與研究;2017年24期

3 胡覺亮;楊佳雯;蘇曉彤;董建明;;機器帶周期性維護時段的加工與運輸協(xié)同排序問題[J];浙江理工大學學報(自然科學版);2016年06期

4 仲維亞;馬曉茹;;帶有運輸且加工具有靈活性的無等待流水作業(yè)排序問題[J];運籌學學報;2016年04期

5 隋楠;羅成新;;具有維護活動及公共工期的加工時間依賴資源的單機排序問題[J];沈陽航空航天大學學報;2016年06期

6 林浩;何程;;關于工期分配與加權誤工數(shù)的雙指標排序問題（英文）[J];工程數(shù)學學報;2017年01期

7 趙傳立;張蕾;;帶有交貨期窗口和加工時間可控的排序問題[J];沈陽師范大學學報(自然科學版);2016年04期

8 王申重;杜海龍;;具有學習效應和遺忘效應的單機排序問題研究[J];棗莊學院學報;2017年02期

9 陳蕾;張安;陳永;陳光亭;;資源定時投放的單機排序問題[J];杭州電子科技大學學報(自然科學版);2017年02期

10 竇文卿;范靜;;一類資源費用可變的平行機排序問題[J];上海第二工業(yè)大學學報;2017年02期

相關會議論文 前10條

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

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 胡榮;呂緒華;;3TMF排序問題的計算復雜性及分支定界法[A];中國運籌學會第八屆學術交流會論文集[C];2006年

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

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

10 吳翠連;;有尺寸的單機分批排序問題的近似算法[A];中國企業(yè)運籌學[2011（1）][C];2011年

相關重要報紙文章 前3條

1 楊文波;淺談方位詞“東、西、南、北”的詞語排序問題[N];語言文字周報;2018年

2 山東 趙玉勇;小博士編程[N];電腦報;2004年

3 何靖;全國計算機應用技術證書考試（NIT）[N];中國電腦教育報;2003年

相關博士學位論文 前10條

1 李融奇;在線排序和批排序問題研究[D];浙江大學;2018年

2 沈佳煜;不確定情形下若干排序問題的研究[D];南京理工大學;2017年

3 高園;新型排序問題的計算復雜性研究[D];鄭州大學;2018年

4 殷娜;依賴于資源分配的排序問題研究[D];上海大學;2015年

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

6 王吉波;工件加工時間可變的現(xiàn)代排序問題[D];大連理工大學;2005年

7 羅潤梓;平行機半在線排序問題[D];上海大學;2005年

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

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

10 李文華;關于分批排序問題的研究[D];鄭州大學;2006年

相關碩士學位論文 前10條

1 潘婷婷;帶資源、學習效應、惡化效應、維護活動和工期窗口的排序問題的研究[D];蘇州大學;2018年

2 張潔;按外包工件個數(shù)不同折扣率的單機排序問題[D];鄭州大學;2018年

3 周松濤;帶約束的單機雙代理排序問題[D];鄭州大學;2018年

4 朱月娟;限選機器上的在線排序問題[D];鄭州大學;2018年

5 孫振霞;機器具有不可用區(qū)間且工件可拒絕的排序問題[D];鄭州大學;2018年

6 陳耀寧;與資源有關的多次維修和加工時間可變的排序問題研究[D];重慶師范大學;2018年

7 孟凡曉;基于退化效應的可拒絕分批排序問題[D];曲阜師范大學;2018年

8 王穆清;同類機上的在線分批排序問題[D];曲阜師范大學;2018年

9 王曉連;模糊數(shù)空間上的排序問題[D];杭州電子科技大學;2018年

10 李丹;兩類資源受限的排序問題研究[D];杭州電子科技大學;2018年

本文編號：2764290