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

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

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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 潘銳;設施選址與K-中間點問題的復雜性與近似算法[D];山東大學;2007年

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

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

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

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

1 陳崇琛;多色點集直線劃分的復雜性及其近似算法[D];復旦大學;2014年

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

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

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

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

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

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

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

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

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

，

本文編號：897916