本文關鍵詞：兩種有維護要求的單機和平行機調度問題研究

  更多相關文章： 維護時長 啟發(fā)式算法 最壞情況界 數(shù)學規(guī)劃模型 數(shù)值實驗

【摘要】：調度問題一直以來是組合優(yōu)化問題領域里最具有前景的方向之一,在過去的幾十年里帶有維護的調度問題更是吸引了大量研究者的目光。在這篇論文里,我們主要研究了兩種帶有維護的調度問題。第一個問題是一個維護時長隨負載量可變的單機調度問題,即機器的維護時長是由一個隨維護之前的負載量單調不減的函數(shù)f(x)所決定的,維護的開始時刻在時間窗[u,v]內,這里的0?u?v。本文所研究問題的目標是在機器上加工完所有工件并決定維護的開始時刻使得最大延遲maxL最小化。本文證明了此調度問題是NP-難的,基于經(jīng)典的EDD算法提出了近似算法EDDMW并分析了它的最壞情況界。第二個問題是一個帶有工具更換和固定周期維護的混合環(huán)境下的平行機最小化時間表長調度問題,其中需要工具更換的機器有1m臺,需要固定周期維護的機器有1m?m臺。工件均不可中斷。為了解決這個調度問題,本文給出了該問題的一個數(shù)學規(guī)劃模型和兩個分別基于經(jīng)典的LPT算法和LS算法的啟發(fā)式算法LPTP和LSP。此數(shù)學規(guī)劃模型的建立背后所隱含的思想是通過將多臺平行機改變成一臺機器。大量數(shù)值實驗顯示這個模型求解工件數(shù)在10以內的實例的求解時間是合理的。同時,為了方便分析這些算法的性能,本文因此還給出了最優(yōu)時間表長的一個下界。本文通過設計一系列計算機數(shù)值實驗,發(fā)現(xiàn)所給出的啟發(fā)式算法能夠在1s內求解具有2000個工件的實例且平均誤差不超過10%,由此證明了本文設計的啟發(fā)式算法十分適合求解大規(guī)模本文所研究的實例。
【關鍵詞】：維護時長 啟發(fā)式算法 最壞情況界 數(shù)學規(guī)劃模型 數(shù)值實驗
【學位授予單位】：東華理工大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O221
【目錄】：

• 摘要4-5
• ABSTRACT5-8
• 第1章 引言8-14
• 1.1 調度的發(fā)展歷史和任務8-9
• 1.2 調度問題的基本概念及符號說明9-10
• 1.3 國內外帶有維護的調度問題的研究現(xiàn)狀10-12
• 1.4 本文的結構安排12-14
• 第2章 維護時長隨負載量可變的單機調度問題14-22
• 2.1 問題引出14
• 2.2 計算復雜性14-15
• 2.3 近似算法15
• 2.4 算法EDDMW最壞情況界分析15-21
• 2.5 小結21-22
• 第3章 帶有工具更換和固定周期維護的平行機調度問題22-36
• 3.1 問題引入22-23
• 3.2 數(shù)學規(guī)劃模型23-26
• 3.2.1 調度問題P_mM_(1-m_1)TC,M((m_1+1)-m)PM||C(max)?特殊情況下的數(shù)學規(guī)劃模型24-25
• 3.2.2 調度問題P_mM_(1-m_1)TC,M((m_1+1)-m)PM||C(max)?的數(shù)學規(guī)劃模型25-26
• 3.3 下界26-27
• 3.4 啟發(fā)式算法27-28
• 3.5 數(shù)學實驗下的平均情況分析28-35
• 3.5.1 算法LPTP和算法LSP相對下界的平均誤差與n的關系29-30
• 3.5.2 算法LPTP和算法LSP相對下界的平均誤差與maxp的關系30-32
• 3.5.3 算法LPTP和算法LSP相對下界的最大誤差與n的關系32-33
• 3.5.4 算法LPTP和算法LSP相對下界的最大誤差與maxp的關系33-35
• 3.6 小結35-36
• 第4章 總結與展望36-38
• 4.1 總結36
• 4.2 問題與展望36-38
• 致謝38-40
• 參考文獻40-42
• 附錄A 程序42-51
• 附件B參加的項目和發(fā)表的論文51

【共引文獻】

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

1 齊學梅;;無等待流水調度問題迭代啟發(fā)式算法[J];安徽師范大學學報(自然科學版);2009年01期

2 卓奕君;成曄;;面向大型產(chǎn)品裝配的兩維勢能調度算法研究[J];北京信息科技大學學報(自然科學版);2009年04期

3 崔建雙,李鐵克,張文新;混合流水車間調度模型及其遺傳算法[J];北京科技大學學報;2005年05期

4 李裕梅;谷云東;李洪興;;調度問題Pm|p_j=1,intree|∑C_j的兩個啟發(fā)式算法[J];北京師范大學學報(自然科學版);2006年02期

5 袁芬;谷云東;塵非;;關于模糊工期平行機調度問題的若干結果[J];北京師范大學學報(自然科學版);2006年03期

6 孫秀平;谷云東;李洪興;;任務無準備時間最小化加權最大延誤單機調度問題的若干結果[J];北京師范大學學報(自然科學版);2006年05期

7 程貞敏;李洪興;;允許中斷的同速機調度問題的一個最優(yōu)算法[J];北京師范大學學報(自然科學版);2008年05期

8 程貞敏;李洪興;谷敏強;;最小化時間表長的平行機調度近似算法研究[J];北京師范大學學報(自然科學版);2012年01期

9 李曉峰;趙海;杜洪軍;劉小勇;;柔性流水作業(yè)排序問題的貪心算法求解[J];吉林大學學報(信息科學版);2009年06期

10 賈春玉;一類3×n流水型排序問題新近似最優(yōu)解法的探討[J];長春大學學報;2004年06期

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

1 聞振衛(wèi);;一類平行機上的任務指派問題及其動態(tài)規(guī)劃算法[A];中國運籌學會第九屆學術交流會論文集[C];2008年

2 劉廣軍;李瑞芹;;2×n排序模型在裝備戰(zhàn)場搶修決策中的應用[A];系統(tǒng)仿真技術及其應用（第16卷）[C];2015年

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

1 馬英;考慮維護時間的機器調度問題研究[D];合肥工業(yè)大學;2010年

2 鐘雪靈;帶強制工期非正則目標函數(shù)的排序問題研究[D];暨南大學;2010年

3 柳春鋒;工程項目中技能型員工調度問題研究[D];合肥工業(yè)大學;2011年

4 許瑞;基于蟻群優(yōu)化算法的批調度問題研究[D];中國科學技術大學;2011年

5 王磊;面向訂單生產(chǎn)的供應鏈排序問題研究[D];暨南大學;2011年

6 丁國生;多代理競爭排序問題的研究[D];上海大學;2009年

7 白芳;民航發(fā)動機機群調度優(yōu)化與視情維修決策方法研究[D];南京航空航天大學;2009年

8 楊名;若干流水作業(yè)排序問題的算法研究[D];華東理工大學;2011年

9 宮華;鋼鐵企業(yè)一類考慮惡化和運輸?shù)男滦蜕a(chǎn)調度問題的理論研究[D];東北大學;2009年

10 李士生;工件具有不相容性質的機器排序問題[D];鄭州大學;2012年

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

1 張瑋虹;生產(chǎn)管理中的若干排序問題[D];浙江理工大學;2010年

2 王悅;存在批處理設備的復雜產(chǎn)品調度研究[D];哈爾濱理工大學;2010年

3 蘇勝龍;帶一個服務器的兩臺平行機半在線排序問題[D];華東理工大學;2011年

4 牟啟燕;帶一個服務器的兩臺機器自由作業(yè)排序問題的近似算法[D];華東理工大學;2011年

5 史媛媛;兩類雙目標排序問題研究[D];武漢科技大學;2010年

6 何少龍;具有安裝時間和變量加工時間的單機排序問題[D];沈陽師范大學;2011年

7 劉洋;具有學習效應和退化效應的單機排序問題[D];沈陽師范大學;2011年

8 曹文琴;帶有運輸時間的在線排序問題[D];蘭州大學;2011年

9 馮娜;帶有不可相容工件組的在線排序問題[D];蘭州大學;2011年

10 王潔明;有關代理競爭排序問題的研究[D];華東理工大學;2011年

，

本文編號：703306