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

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

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

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

2 豆俊梅;孫彩賢;;單機(jī)排序問(wèn)題的研究[J];數(shù)學(xué)學(xué)習(xí)與研究;2017年24期

3 胡覺(jué)亮;楊佳雯;蘇曉彤;董建明;;機(jī)器帶周期性維護(hù)時(shí)段的加工與運(yùn)輸協(xié)同排序問(wèn)題[J];浙江理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年06期

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

5 隋楠;羅成新;;具有維護(hù)活動(dòng)及公共工期的加工時(shí)間依賴(lài)資源的單機(jī)排序問(wèn)題[J];沈陽(yáng)航空航天大學(xué)學(xué)報(bào);2016年06期

6 林浩;何程;;關(guān)于工期分配與加權(quán)誤工數(shù)的雙指標(biāo)排序問(wèn)題（英文）[J];工程數(shù)學(xué)學(xué)報(bào);2017年01期

7 趙傳立;張蕾;;帶有交貨期窗口和加工時(shí)間可控的排序問(wèn)題[J];沈陽(yáng)師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年04期

8 王申重;杜海龍;;具有學(xué)習(xí)效應(yīng)和遺忘效應(yīng)的單機(jī)排序問(wèn)題研究[J];棗莊學(xué)院學(xué)報(bào);2017年02期

9 陳蕾;張安;陳永;陳光亭;;資源定時(shí)投放的單機(jī)排序問(wèn)題[J];杭州電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2017年02期

10 竇文卿;范靜;;一類(lèi)資源費(fèi)用可變的平行機(jī)排序問(wèn)題[J];上海第二工業(yè)大學(xué)學(xué)報(bào);2017年02期

相關(guān)會(huì)議論文 前10條

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

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

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

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

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

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

7 胡榮;呂緒華;;3TMF排序問(wèn)題的計(jì)算復(fù)雜性及分支定界法[A];中國(guó)運(yùn)籌學(xué)會(huì)第八屆學(xué)術(shù)交流會(huì)論文集[C];2006年

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

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

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

相關(guān)重要報(bào)紙文章 前3條

1 楊文波;淺談方位詞“東、西、南、北”的詞語(yǔ)排序問(wèn)題[N];語(yǔ)言文字周報(bào);2018年

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

3 何靖;全國(guó)計(jì)算機(jī)應(yīng)用技術(shù)證書(shū)考試（NIT）[N];中國(guó)電腦教育報(bào);2003年

相關(guān)博士學(xué)位論文 前10條

1 李融奇;在線排序和批排序問(wèn)題研究[D];浙江大學(xué);2018年

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

3 高園;新型排序問(wèn)題的計(jì)算復(fù)雜性研究[D];鄭州大學(xué);2018年

4 殷娜;依賴(lài)于資源分配的排序問(wèn)題研究[D];上海大學(xué);2015年

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

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

7 羅潤(rùn)梓;平行機(jī)半在線排序問(wèn)題[D];上海大學(xué);2005年

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

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

10 李文華;關(guān)于分批排序問(wèn)題的研究[D];鄭州大學(xué);2006年

相關(guān)碩士學(xué)位論文 前10條

1 潘婷婷;帶資源、學(xué)習(xí)效應(yīng)、惡化效應(yīng)、維護(hù)活動(dòng)和工期窗口的排序問(wèn)題的研究[D];蘇州大學(xué);2018年

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

3 周松濤;帶約束的單機(jī)雙代理排序問(wèn)題[D];鄭州大學(xué);2018年

4 朱月娟;限選機(jī)器上的在線排序問(wèn)題[D];鄭州大學(xué);2018年

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

6 陳耀寧;與資源有關(guān)的多次維修和加工時(shí)間可變的排序問(wèn)題研究[D];重慶師范大學(xué);2018年

7 孟凡曉;基于退化效應(yīng)的可拒絕分批排序問(wèn)題[D];曲阜師范大學(xué);2018年

8 王穆清;同類(lèi)機(jī)上的在線分批排序問(wèn)題[D];曲阜師范大學(xué);2018年

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

10 李丹;兩類(lèi)資源受限的排序問(wèn)題研究[D];杭州電子科技大學(xué);2018年

本文編號(hào)：2764290