本文關(guān)鍵詞：考慮機(jī)器隨機(jī)中斷且具有時間相關(guān)惡化效應(yīng)的平行機(jī)調(diào)度問題

  更多相關(guān)文章： 調(diào)度 隨機(jī)干擾 維護(hù) 惡化效應(yīng) 偽多項式時間算法 完全多項式時間近似方案

【摘要】：在一些經(jīng)典調(diào)度問題中,通常假設(shè)工件的加工時間為常數(shù),并且在加工過程中機(jī)器可以持續(xù)加工工件。但在許多實際生產(chǎn)過程中,由于機(jī)器的老化或其他原因會導(dǎo)致機(jī)器的加工效率下降,從而使得工件所需的實際加工時間隨其開始加工時間的推遲而增大,這種現(xiàn)象稱為機(jī)器具有惡化效應(yīng)。同時,由于一些內(nèi)部或外部原因,會使機(jī)器在加工過程中發(fā)生中斷,往往不能持續(xù)工作。因此,需要對機(jī)器進(jìn)行維護(hù)以提高機(jī)器的加工效率或防止機(jī)器發(fā)生中斷。本文主要研究考慮機(jī)器可隨機(jī)中斷且具有時間相關(guān)惡化效應(yīng)的平行機(jī)調(diào)度問題。在該問題中,由于機(jī)器惡化效應(yīng)的影響,工件的實際加工時間定義為其開始加工時間的非減函數(shù)。此外,由于一些內(nèi)部或外部原因,部分機(jī)器會發(fā)生隨機(jī)干擾,其中中斷的開始時刻是已知的,但中斷是否發(fā)生具有一定的隨機(jī)性且中斷時長服從一定的概率分布。機(jī)器中斷發(fā)生后,有兩類決策可以考慮。一類是在機(jī)器中斷發(fā)生后立即對機(jī)器進(jìn)行維護(hù),維護(hù)后的機(jī)器將恢復(fù)初始狀態(tài)。另一類是不進(jìn)行維護(hù)。目標(biāo)是確定一個最優(yōu)調(diào)度以最小化工件完工時間和的數(shù)學(xué)期望。本文的主要研究內(nèi)容和創(chuàng)新點如下：(1)對于工件不可中斷的情形,證明了當(dāng)機(jī)器數(shù)為輸入變量時相應(yīng)問題是強(qiáng)NP-難的,當(dāng)機(jī)器數(shù)為固定量時則是NP-難的。在機(jī)器數(shù)固定的條件下,針對中斷發(fā)生后是否對機(jī)器進(jìn)行維護(hù)兩種情形,分別設(shè)計了偽多項式時間動態(tài)規(guī)劃算法,進(jìn)而說明了相應(yīng)問題是一般NP-難的,進(jìn)一步證明了當(dāng)中斷僅發(fā)生在其中一臺機(jī)器上時,相應(yīng)問題存在完全多項式時間近似方案。(2)對于工件可中斷的情形,證明了當(dāng)機(jī)器數(shù)為輸入變量時相應(yīng)問題是強(qiáng)NP-難的,當(dāng)機(jī)器數(shù)為固定量且中斷發(fā)生在其中至少兩臺機(jī)器上時相應(yīng)問題是NP-難的。在機(jī)器數(shù)固定的條件下,針對中斷發(fā)生后是否對機(jī)器進(jìn)行維護(hù)兩種情形,分別設(shè)計了偽多項式時間動態(tài)規(guī)劃算法,進(jìn)而說明當(dāng)中斷發(fā)生在其中至少兩臺機(jī)器上時相應(yīng)問題是一般NP-難的。然而,當(dāng)機(jī)器數(shù)為固定量且中斷僅發(fā)生在其中一臺機(jī)器上,相應(yīng)問題是否是NP-難的仍是未知的。
【關(guān)鍵詞】：調(diào)度 隨機(jī)干擾 維護(hù) 惡化效應(yīng) 偽多項式時間算法 完全多項式時間近似方案
【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O223
【目錄】：

• 摘要6-7
• Abstract7-11
• 第一章 引言11-19
• 1.1 調(diào)度的基本概念與符號說明11-13
• 1.2 研究概況13-18
• 1.2.1 機(jī)器具有不可用時間區(qū)間的調(diào)度問題14-15
• 1.2.2 具有惡化效應(yīng)的調(diào)度問題15-16
• 1.2.3 研究現(xiàn)狀分析16-18
• 1.3 本文的結(jié)構(gòu)安排18-19
• 第二章 問題與分析19-22
• 2.1 問題描述19-20
• 2.2 結(jié)構(gòu)性質(zhì)20-22
• 第三章 工件不可中斷的模型22-40
• 3.1 偽多項式時間算法22-33
• 3.1.1 模型Pm,l|nr-a,M,DE,PDR|E(∑_(j=1)~nC_j)22-29
• 3.1.2 模型Pm,l|nr-a,M,DE,PDR|E(∑_(j=1)~nC_j)29-33
• 3.2 當(dāng)l=1、s_0=0時的完全多項式時間近似方案(FPTAS)33-40
• 第四章 工件可中斷的模型40-45
• 4.1 模型Pm,l|nr-a,M,DE,PDR|E(∑_(j=1)~nC_j)41-43
• 4.2 模型Pm,l|nr-a,M,DE,PDR|E(∑_(j=1)~nC_j)43-45
• 第五章 總結(jié)與展望45-48
• 5.1 總結(jié)45-46
• 5.2 展望46-48
• 參考文獻(xiàn)48-51
• 致謝51-52
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄52

【相似文獻(xiàn)】

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

1 郭艷東;黃敏;王慶;;鎖定初始調(diào)度的緊急工作單機(jī)重調(diào)度問題[J];東北大學(xué)學(xué)報(自然科學(xué)版);2013年05期

2 席裕庚,王長軍;控制、規(guī)劃和調(diào)度問題中的博弈論應(yīng)用[J];中國計量學(xué)院學(xué)報;2005年01期

3 胡揚(yáng);桂衛(wèi)華;;人工代謝算法在多對象調(diào)度中的應(yīng)用[J];系統(tǒng)工程學(xué)報;2011年01期

4 劉鵬;周曉曄;衣娜;;帶有減少線性惡化效應(yīng)的雙代理調(diào)度問題[J];系統(tǒng)工程學(xué)報;2011年03期

5 董平;機(jī)器調(diào)度問題及求解方法[J];物流技術(shù)與應(yīng)用;1997年01期

6 張仁忠;一類串行生產(chǎn)線的最優(yōu)調(diào)度問題的注記[J];黃淮學(xué)刊(自然科學(xué)版);1998年S3期

7 劉紅,張強(qiáng),杜瑜;全國大學(xué)生數(shù)學(xué)建模競賽中公交車調(diào)度問題的求解[J];成都航空職業(yè)技術(shù)學(xué)院學(xué)報;2002年02期

8 黎鶴;孫廣中;許胤龍;;未知網(wǎng)絡(luò)中可分負(fù)載的分布式調(diào)度[J];中國科學(xué)技術(shù)大學(xué)學(xué)報;2009年08期

9 王冰;動態(tài)單機(jī)調(diào)度的一種滾動時域策略及全局性能分析[J];系統(tǒng)工程理論與實踐;2004年09期

10 左燕;薛安克;王建中;;單機(jī)調(diào)度問題對偶集結(jié)迭代算法[J];控制理論與應(yīng)用;2010年12期

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

1 李建更;涂凍生;馬海濤;;單機(jī)拖后時間總和問題交付期擾動時最優(yōu)調(diào)度不變范圍的一種求法[A];第十九屆中國控制會議論文集（一）[C];2000年

2 劉海龍;黃小原;;總的未完工費(fèi)用最小的多機(jī)調(diào)度問題[A];1995中國控制與決策學(xué)術(shù)年會論文集[C];1995年

3 沈吟東;曾西洋;;公共交通駕駛員調(diào)度的復(fù)雜性及解決方法[A];’2004計算機(jī)應(yīng)用技術(shù)交流會議論文集[C];2004年

4 李兵;蔣慰孫;;Job shop問題的建模及調(diào)度[A];1996中國控制與決策學(xué)術(shù)年會論文集[C];1996年

5 王海星;申金升;;智能蟻群算法解決公交區(qū)域調(diào)度問題研究[A];2006年首屆ICT大會信息、知識、智能及其轉(zhuǎn)換理論第一次高峰論壇會議論文集[C];2006年

6 王成堯;汪定偉;;模糊加工時間的單機(jī)調(diào)度問題[A];1996中國控制與決策學(xué)術(shù)年會論文集[C];1996年

7 齊向彤;涂奉生;;雙交付期E／T調(diào)度問題[A];1997年中國控制會議論文集[C];1997年

8 吳斌;方葉祥;崔志勇;;基于人工蜂群算法的越庫調(diào)度問題研究[A];第25屆中國控制與決策會議論文集[C];2013年

9 方濤;吳受章;;FMS的自適應(yīng)調(diào)度:結(jié)構(gòu)與算法研究[A];1992年中國控制與決策學(xué)術(shù)年會論文集[C];1992年

10 劉興初;趙千川;鄭大鐘;;具有不同準(zhǔn)備時間和交付期的單機(jī)E／T調(diào)度問題研究[A];1998年中國控制會議論文集[C];1998年

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

1 本報記者 賈科華;火電機(jī)組叫苦調(diào)度不合理[N];中國能源報;2012年

2 本報記者 高芳;牽住“牛鼻子” 巧解“推進(jìn)難”[N];湖南經(jīng)濟(jì)報;2008年

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

1 郭鵬;具有分段惡化效應(yīng)生產(chǎn)過程的智能優(yōu)化調(diào)度研究[D];西南交通大學(xué);2014年

2 元野;基于圖著色模型的零擔(dān)物流調(diào)度優(yōu)化問題研究[D];哈爾濱工業(yè)大學(xué);2015年

3 李雪松;模糊環(huán)境下若干單機(jī)批加工調(diào)度問題的模型及其算法研究[D];哈爾濱工業(yè)大學(xué);2015年

4 湯雅連;關(guān)聯(lián)物流運(yùn)輸調(diào)度問題研究[D];廣東工業(yè)大學(xué);2015年

5 周理;高效可重構(gòu)陣列計算：體系結(jié)構(gòu)，設(shè)計方法與程序映射技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2014年

6 馮大光;一類批處理機(jī)調(diào)度的理論和方法研究[D];東北大學(xué);2011年

7 孟盈;鋼鐵企業(yè)并行批生產(chǎn)決策與調(diào)度問題研究[D];東北大學(xué);2011年

8 楊磊;內(nèi)容網(wǎng)絡(luò)中內(nèi)容調(diào)度技術(shù)研究[D];重慶大學(xué);2015年

9 李亞志;流水制造單元調(diào)度智能優(yōu)化方法[D];東南大學(xué);2015年

10 丁寧;若干調(diào)度問題的算法研究[D];大連理工大學(xué);2016年

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

1 張亮;云計算環(huán)境下的資源調(diào)度技術(shù)的研究[D];江南大學(xué);2015年

2 馮卓鵬;重載運(yùn)輸卸車組織優(yōu)化研究[D];西南交通大學(xué);2015年

3 閆志超;基于人工蜂群算法的拖輪調(diào)度優(yōu)化[D];大連海事大學(xué);2015年

4 石雪飛;維護(hù)時長隨機(jī)器負(fù)載線性遞增的單機(jī)調(diào)度問題[D];東華理工大學(xué);2014年

5 蘇瑋;含風(fēng)電場電力系統(tǒng)的風(fēng)險調(diào)度[D];東南大學(xué);2015年

6 李曉浩;蟻群優(yōu)化算法在平行機(jī)批調(diào)度問題中的應(yīng)用與研究[D];安徽大學(xué);2016年

7 陳琳;基于衰老機(jī)制的群智能算法及其在跨單元調(diào)度問題中的應(yīng)用[D];北京理工大學(xué);2016年

8 趙海丹;有模具限制的并行機(jī)臺調(diào)度問題研究[D];吉林大學(xué);2016年

9 王如雪;項目多目標(biāo)模糊調(diào)度優(yōu)化模型及算法研究[D];吉林大學(xué);2016年

10 沈睿;基于實時需求的夜間柔性公交調(diào)度研究[D];西南交通大學(xué);2016年

，

本文編號：821334