本文關(guān)鍵詞：具有不同釋放時間的單機(jī)重新排序問題的近似算法

  更多相關(guān)文章： 重新排序 釋放時間 時間錯位 加權(quán)時間總和 近似算法

【摘要】：近年來,重新排序問題研究開始引起廣泛的關(guān)注.本文以工廠機(jī)器加工工件(工件與任務(wù)表示相同的概念)作為實(shí)際背景,主要考慮有一批工件已經(jīng)按照某種規(guī)則進(jìn)行了排序并使得目標(biāo)函數(shù)達(dá)到了最優(yōu),其中有一些工件由于各種各樣的原因要推遲到某個時間點(diǎn)后才可以開始加工,此時,決策者需要對原來的排序進(jìn)行調(diào)整,即在原來最優(yōu)排序的基礎(chǔ)上,在工件的時間錯位不至于太大的限制下進(jìn)行重新排序,并使得原來的目標(biāo)函數(shù)達(dá)到最優(yōu)的單機(jī)問題.本文研究的問題的目標(biāo)函數(shù)是經(jīng)典的加權(quán)完工時間總和.對于這個問題Nicholas G.Hall不Chris N.Potts已經(jīng)提供了一種復(fù)雜度是偽多項(xiàng)式時間的動態(tài)規(guī)劃最優(yōu)算法TWCOA,并給出了其時間復(fù)雜度的分析,隨后給出了GAA近似算法,其最壞情況誤差比為2.本文對該近似算法進(jìn)行改善,得到了更好的SR近似算法并給出了其最壞情況誤差比比GAA近似算法小的證明.同時對該問題進(jìn)行了拓展,將條件中的重排工件共有的一個釋放時間變成兩個不同的釋放時間,使問題變得更一般化,然后進(jìn)行討論從而得到該問題的一個近似算法SRT.
【關(guān)鍵詞】：重新排序 釋放時間 時間錯位 加權(quán)時間總和 近似算法
【學(xué)位授予單位】：蘭州大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O223
【目錄】：

• 中文摘要3-4
• 英文摘要4-6
• 第一章 引言6-8
• 1.1 研究背景6
• 1.2 研究現(xiàn)狀6-7
• 1.3 研究內(nèi)容及結(jié)構(gòu)7-8
• 第二章 TWCOA算法8-13
• 2.1 基本概念及相關(guān)結(jié)論8-11
• 2.1.1 問題概述8-9
• 2.1.2 相關(guān)結(jié)論9-11
• 2.2 TWCOA算法11-12
• 2.3 GAA近似算法12-13
• 第三章 SR算法13-18
• 3.1 SR算法的思路13-14
• 3.2 SR算法14-16
• 3.2.1 SR算法及其算法復(fù)雜度14-15
• 3.2.2 SR算法的最壞情況誤差比15-16
• 3.3 實(shí)例16-18
• 第四章 具有兩個不同釋放時間的單機(jī)重排問題18-27
• 4.1 問題概述及相關(guān)結(jié)論18-21
• 4.2 SRT算法及其算法復(fù)雜度21-25
• 4.3 實(shí)例25-27
• 第五章 總結(jié)和展望27-28
• 參考文獻(xiàn)28-30
• 致謝30

【相似文獻(xiàn)】

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

1 魏麒;蔣義偉;;一類兩階段雜交流水作業(yè)的近似算法(英文)[J];軟件學(xué)報;2012年05期

2 劉振宏;組合最優(yōu)化問題的近似算法[J];數(shù)學(xué)的實(shí)踐與認(rèn)識;1983年03期

3 馬紹漢;一類限制樹問題的復(fù)雜性及其近似算法[J];山東大學(xué)學(xué)報(自然科學(xué)版);1984年01期

4 楊延齡,戚文發(fā);關(guān)于最優(yōu)備件問題的近似算法的研究[J];工程數(shù)學(xué)學(xué)報;1989年01期

5 杜林古;;帶風(fēng)向投遞員問題的一個多項(xiàng)式1—近似算法[J];山東紡織工學(xué)院學(xué)報;1992年01期

6 蘇純潔;帶服務(wù)器的三臺平行機(jī)排序問題的復(fù)雜性和近似算法[J];應(yīng)用數(shù)學(xué)學(xué)報;2003年03期

7 劉光聰;朱大銘;姜海濤;;有向基因組反轉(zhuǎn)和轉(zhuǎn)位排序最小權(quán)重問題的1.5k近似算法[J];小型微型計(jì)算機(jī)系統(tǒng);2010年07期

8 何勇;帶核集分劃問題的一個線性(1/7)-近似算法[J];高校應(yīng)用數(shù)學(xué)學(xué)報A輯(中文版);1997年04期

9 季敏,何勇;帶核集分劃問題的一個改進(jìn)近似算法[J];系統(tǒng)工程理論與實(shí)踐;2003年12期

10 何曉瓊;陳沖;李榮珩;;工廠地址集中的k-種產(chǎn)品選址問題的近似算法[J];計(jì)算機(jī)工程與應(yīng)用;2010年08期

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

1 劉聲田;朱大銘;;基因序列翻轉(zhuǎn)排序的一種近似算法[A];山東省計(jì)算機(jī)學(xué)會2005年信息技術(shù)與信息化研討會論文集（一）[C];2005年

2 梅生偉;洪奕光;秦化淑;翁紹鵬;;非線性H_∞控制的粘性解及其近似算法[A];1996年中國控制會議論文集[C];1996年

3 田世俊;李建;朱洪;;多需求目標(biāo)的UFL問題及其近似算法[A];2005年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會論文集[C];2005年

4 梁國宏;郭云霞;鄭明發(fā);;最大化下模函數(shù)的近似算法及其性能保證[A];第十屆中國不確定系統(tǒng)年會、第十四屆中國青年信息與管理學(xué)者大會論文集[C];2012年

5 保利勇;趙東風(fēng);丁洪偉;;雙服務(wù)器異步控制策略輪詢系統(tǒng)性能的近似算法分析[A];2009年中國高校通信類院系學(xué)術(shù)研討會論文集[C];2009年

6 任建峰;張玉忠;孫國;;一種新的柔性車間排序問題[A];中國企業(yè)運(yùn)籌學(xué)學(xué)術(shù)交流大會論文集[C];2005年

7 李灝;張春路;丁國良;;對多層墻體反應(yīng)系數(shù)的一種近似算法的討論[A];上海市制冷學(xué)會一九九七年學(xué)術(shù)年會論文集[C];1997年

8 李灝;張春路;丁國良;;對多層墻體反應(yīng)系數(shù)的一種近似算法的討論[A];全國暖通空調(diào)制冷1998年學(xué)術(shù)年會論文集（2）[C];1998年

9 周露;吳瑤華;黃文虎;聞新;;一種推廣卡爾曼濾波的近似算法[A];1995中國控制與決策學(xué)術(shù)年會論文集[C];1995年

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

1 PALADIN;近似算法[N];電腦報;2003年

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

1 楊朝霞;超圖嵌入圈問題的近似算法[D];山東大學(xué);2010年

2 潘銳;設(shè)施選址與K-中間點(diǎn)問題的復(fù)雜性與近似算法[D];山東大學(xué);2007年

3 陳仕平;若干組合優(yōu)化問題的近似算法設(shè)計(jì)與分析[D];浙江大學(xué);2002年

4 柳楠;基因組片段填充問題的算法研究[D];山東大學(xué);2013年

5 姜海濤;基因組比較算法研究[D];山東大學(xué);2011年

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

1 陳崇琛;多色點(diǎn)集直線劃分的復(fù)雜性及其近似算法[D];復(fù)旦大學(xué);2014年

2 王敏;基于圖特征的介度中心近似算法研究[D];曲阜師范大學(xué);2015年

3 張亞平;最小賦權(quán)連通k-子圖覆蓋問題的近似算法[D];新疆大學(xué);2015年

4 張永俊;廣義非線性分式規(guī)劃問題的近似算法[D];河南師范大學(xué);2015年

5 朱婷婷;具有不同釋放時間的單機(jī)重新排序問題的近似算法[D];蘭州大學(xué);2016年

6 王克紅;均勻限制NP-完備間題及其近似算法設(shè)計(jì)[D];云南大學(xué);2016年

7 李彥杰;連通控制吸收集的近似算法[D];新疆大學(xué);2013年

8 張峰;漫射光化通量的二流四流混合近似算法求解[D];中國氣象科學(xué)研究院;2010年

9 劉海;非光滑問題的三次近似算法[D];北京工業(yè)大學(xué);2014年

10 張諸俊;異構(gòu)車輛路徑問題近似算法的研究[D];華東師范大學(xué);2014年

，

本文編號：897916