本文關(guān)鍵詞：兩種有維護(hù)要求的單機(jī)和平行機(jī)調(diào)度問(wèn)題研究

  更多相關(guān)文章： 維護(hù)時(shí)長(zhǎng) 啟發(fā)式算法 最壞情況界 數(shù)學(xué)規(guī)劃模型 數(shù)值實(shí)驗(yàn)

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

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

【共引文獻(xiàn)】

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

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

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

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

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

5 袁芬;谷云東;塵非;;關(guān)于模糊工期平行機(jī)調(diào)度問(wèn)題的若干結(jié)果[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年03期

6 孫秀平;谷云東;李洪興;;任務(wù)無(wú)準(zhǔn)備時(shí)間最小化加權(quán)最大延誤單機(jī)調(diào)度問(wèn)題的若干結(jié)果[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年05期

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

8 程貞敏;李洪興;谷敏強(qiáng);;最小化時(shí)間表長(zhǎng)的平行機(jī)調(diào)度近似算法研究[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年01期

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

10 賈春玉;一類(lèi)3×n流水型排序問(wèn)題新近似最優(yōu)解法的探討[J];長(zhǎng)春大學(xué)學(xué)報(bào);2004年06期

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

1 聞?wù)裥l(wèi);;一類(lèi)平行機(jī)上的任務(wù)指派問(wèn)題及其動(dòng)態(tài)規(guī)劃算法[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

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

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

1 馬英;考慮維護(hù)時(shí)間的機(jī)器調(diào)度問(wèn)題研究[D];合肥工業(yè)大學(xué);2010年

2 鐘雪靈;帶強(qiáng)制工期非正則目標(biāo)函數(shù)的排序問(wèn)題研究[D];暨南大學(xué);2010年

3 柳春鋒;工程項(xiàng)目中技能型員工調(diào)度問(wèn)題研究[D];合肥工業(yè)大學(xué);2011年

4 許瑞;基于蟻群優(yōu)化算法的批調(diào)度問(wèn)題研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年

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

6 丁國(guó)生;多代理競(jìng)爭(zhēng)排序問(wèn)題的研究[D];上海大學(xué);2009年

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

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

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

10 李士生;工件具有不相容性質(zhì)的機(jī)器排序問(wèn)題[D];鄭州大學(xué);2012年

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

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

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

3 蘇勝龍;帶一個(gè)服務(wù)器的兩臺(tái)平行機(jī)半在線排序問(wèn)題[D];華東理工大學(xué);2011年

4 牟啟燕;帶一個(gè)服務(wù)器的兩臺(tái)機(jī)器自由作業(yè)排序問(wèn)題的近似算法[D];華東理工大學(xué);2011年

5 史媛媛;兩類(lèi)雙目標(biāo)排序問(wèn)題研究[D];武漢科技大學(xué);2010年

6 何少龍;具有安裝時(shí)間和變量加工時(shí)間的單機(jī)排序問(wèn)題[D];沈陽(yáng)師范大學(xué);2011年

7 劉洋;具有學(xué)習(xí)效應(yīng)和退化效應(yīng)的單機(jī)排序問(wèn)題[D];沈陽(yáng)師范大學(xué);2011年

8 曹文琴;帶有運(yùn)輸時(shí)間的在線排序問(wèn)題[D];蘭州大學(xué);2011年

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

10 王潔明;有關(guān)代理競(jìng)爭(zhēng)排序問(wèn)題的研究[D];華東理工大學(xué);2011年

，

本文編號(hào)：703306