本文關(guān)鍵詞：帶有時間窗口約束的排序及相關(guān)問題研究

  更多相關(guān)文章： 排序 時間窗口約束 近似算法 最壞情況分析

【摘要】：排序問題一直以來是經(jīng)典組合優(yōu)化問題之一,近幾十年來,正被越來越廣泛地應(yīng)用于生產(chǎn)與制造領(lǐng)域。本論文研究了帶有時間窗口約束的排序問題,可以被看作是一個新的資源約束模型,其在柔性制造系統(tǒng)和印刷電路板組件等方面具有潛在的應(yīng)用。論文分為四章,重點(diǎn)研究了近似算法的設(shè)計與分析。第一章主要簡要介紹了排序問題的一些相關(guān)知識和國內(nèi)外研究的現(xiàn)狀,提供了幾個經(jīng)典排序問題的復(fù)雜性及其算法,同時也對啟發(fā)式算法與近似算法進(jìn)行了一些簡單介紹。第二章研究了帶單位時間窗口約束的單機(jī)排序問題。要求任意單位時間內(nèi)最多只允許B個工件進(jìn)行加工,對B=2與B≥3兩種情況分別設(shè)計了近似算法,并證明當(dāng)B=2時,算法目標(biāo)值τ(T)≤τ(S)+(1/2)（其中τ(S)為最優(yōu)值);當(dāng)B=3,4時,τ(T)≤(B/(B-1))τ(S)+2,當(dāng)B≥5時,τ(T)≤(5/4)τ(S)+2。第三章在第二章的基礎(chǔ)上,討論了帶單位時間窗口約束的兩臺平行機(jī)排序問題。要求任意單位時間內(nèi)兩臺機(jī)器上最多允許B個工件進(jìn)行加工。分析了LPT與LS兩個經(jīng)典算法的近似性能,當(dāng)B=2時,對LS算法有τ(LS)≤(3/2)τ(OPT)+(1/2)以及τ(LS)≤2τ(OPT);對LPT算法有τ(LPT)≤(1+(1/n))τ(OPT)+(1/n)以及τ(LPT)≤(5/4)τ(OPT);而當(dāng)B≥3時,對LS算法有τ(LS)≤((5/2)-(2/B))τ(OPT)+(1/2)。第四章研究了一類帶外包選擇的單機(jī)排序問題。假設(shè)僅有一臺本地機(jī)器和一個外包承包商,每個工件既可以在本地機(jī)器上加工又可以外包商處加工。本地加工的費(fèi)用為總誤工工件數(shù),外包加工的費(fèi)用與外包工件有關(guān)。對于極小化總加工費(fèi)用這一NP難問題,給出偽多項(xiàng)式時間動態(tài)規(guī)劃算法。如果外包費(fèi)用正比于外包工件的加工時間,設(shè)計出近似算法并給出最壞情況分析。第五章,我們對本文進(jìn)行了歸納與總結(jié),并對未來的相關(guān)研究工作作了展望。
【學(xué)位授予單位】：杭州電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O223

【參考文獻(xiàn)】

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

1 陳榮軍;唐國春;;平行機(jī)的排序與轉(zhuǎn)包(英文)[J];數(shù)學(xué)季刊;2012年04期

2 仲維亞;劉曉蕾;霍志明;;工件可轉(zhuǎn)包加工的排序問題研究[J];運(yùn)籌學(xué)學(xué)報;2012年01期

3 ;TWO-STAGE PRODUCTION SCHEDULING WITH AN OPTION OF OUTSOURCING FROM A REMOTE SUPPLIER[J];Journal of Systems Science and Systems Engineering;2009年01期

4 王宇平,何文章;m×n排序問題在實(shí)際中的應(yīng)用[J];數(shù)學(xué)的實(shí)踐與認(rèn)識;1990年04期

5 張正鈾;;散列排序算法[J];廣西科學(xué)院學(xué)報;1982年01期

6 越民義,韓繼業(yè);同順序m×n排序問題的一個新方法[J];科學(xué)通報;1979年18期

7 秦裕瑗;;一個排序UO楲[J];武漢鋼鐵學(xué)院學(xué)報;1979年02期

8 常慶龍;以延誤時間為指標(biāo)的一臺設(shè)備上的排序問題[J];數(shù)學(xué)的實(shí)踐與認(rèn)識;1978年02期

9 越民義,韓繼業(yè);排序問題中的一些數(shù)學(xué)問題[J];數(shù)學(xué)的實(shí)踐與認(rèn)識;1976年03期

10 越民義,韓繼業(yè);n個零件在m臺機(jī)床上的加工順序問題(Ⅰ)[J];中國科學(xué);1975年05期

，

本文編號：1167688