本文選題：調(diào)度　切入點(diǎn)：隨機(jī)干擾　出處：《昆明理工大學(xué)》2017年碩士論文

【摘要】：調(diào)度是運(yùn)籌學(xué)與控制論學(xué)科的重要研究方方向,關(guān)于它的論文有很多。在這些經(jīng)典的調(diào)度問題中,通常假設(shè)工件的加工時(shí)間通常為常數(shù),并且在工件加工過程中機(jī)器可以持續(xù)加工工件。在這錯(cuò)綜復(fù)雜的現(xiàn)實(shí)生活中,調(diào)度問題是不拘一格的,有時(shí)工件的實(shí)際加工時(shí)間隨其開始加工時(shí)間的推遲而增大,工作效率越來越低;有時(shí)工件的實(shí)際加工時(shí)間隨其開始加工時(shí)間的推遲而減小,工作效率越來越高;而有些情況下,工件的實(shí)際加工時(shí)間是與其所排位置相關(guān)的。與此同時(shí),由于一些內(nèi)部的原因和外部環(huán)境的限制,會(huì)使機(jī)器在加工過程中發(fā)生中斷,使機(jī)器不能持續(xù)工作�；诖�,本文研究帶機(jī)器隨機(jī)故障和加工時(shí)間與位置相關(guān)的平行機(jī)調(diào)度問題。該問題中,工件的實(shí)際加工時(shí)間是與其所排位置相關(guān)的一般函數(shù)。在機(jī)器運(yùn)行過程中,某些隨機(jī)事件的發(fā)生會(huì)導(dǎo)致部分機(jī)器不能正常工作。本文假設(shè)這些隨機(jī)事件的開始時(shí)間已知,且它們會(huì)以一定的概率持續(xù)一段時(shí)間。當(dāng)隨機(jī)事件發(fā)生時(shí),本文考慮工件可中斷和不可中斷兩種不同的情形下,目標(biāo)是最小化工件總完成時(shí)間的期望。本文將對(duì)相應(yīng)問題不同情形的復(fù)雜性進(jìn)行分析并設(shè)計(jì)相應(yīng)的偽多項(xiàng)式時(shí)間算法。具體研究?jī)?nèi)容如下:(1)工件不可中斷:在機(jī)器數(shù)量固定的情況下,證明了相應(yīng)問題是NP難的,設(shè)計(jì)了偽多項(xiàng)式時(shí)間動(dòng)態(tài)規(guī)劃算法,進(jìn)而說明了相應(yīng)問題是一般NP難的。具體地,本文僅詳細(xì)分析兩臺(tái)機(jī)器中有一臺(tái)機(jī)器發(fā)生中斷的情況,然后簡(jiǎn)單討論如何將結(jié)論推廣到m臺(tái)機(jī)器中有K臺(tái)機(jī)器會(huì)發(fā)生中斷的情況。(2)工件可中斷:在機(jī)器的數(shù)量變化時(shí),證明了相應(yīng)的問題是強(qiáng)NP問題;在機(jī)器數(shù)量為固定值且發(fā)生中斷的機(jī)器大于等于兩臺(tái)的情況下,證明了該問題是NP難的,設(shè)計(jì)了偽多項(xiàng)式時(shí)間動(dòng)態(tài)規(guī)劃算法,進(jìn)而說明了相應(yīng)問題是一般NP難的;然而,當(dāng)中斷僅發(fā)生在一臺(tái)機(jī)器上時(shí)該問題是否為NP難的仍是未知的。
[Abstract]:Scheduling is an important research direction in operational research and cybernetics, and there are many papers on it.In these classical scheduling problems, the processing time of the workpiece is usually assumed to be constant, and the machine can continuously process the workpiece during the process of the workpiece processing.In this complicated real life, the scheduling problem is not restricted, sometimes the actual processing time of the workpiece increases with the delay of the starting processing time, and the working efficiency becomes lower and lower.Sometimes the actual processing time of the workpiece decreases with the delay of the starting time, and the working efficiency becomes higher and higher. In some cases, the actual processing time of the workpiece is related to the position of the workpiece.At the same time, due to some internal reasons and external environment constraints, the machine will be interrupted in the process of processing, so that the machine can not continue to work.Based on this, the parallel machine scheduling problem with machine random fault and processing time and position is studied.In this problem, the actual processing time of the workpiece is a general function related to the position of the workpiece.In the process of machine operation, some random events will cause some machines to fail to work properly.This paper assumes that the starting time of these random events is known and that they will last for a certain period of time with a certain probability.When random events occur, the goal of this paper is to minimize the expectation of the total completion time of the workpiece in the case of interruptible and uninterruptible workpiece.In this paper, the complexity of the corresponding problems in different cases is analyzed and the corresponding pseudo-polynomial time algorithm is designed.In the case of fixed number of machines, it is proved that the corresponding problem is NP-hard, and a pseudo-polynomial time dynamic programming algorithm is designed, which shows that the corresponding problem is general NP-hard.Specifically, this paper only analyzes the interruption of one of the two machines in detail.Then it is discussed how to generalize the conclusion to the case that K machines in m machines will be interrupted. The workpiece can be interrupted: when the number of machines changes, it is proved that the corresponding problem is a strong NP problem;It is proved that the problem is NP-hard when the number of machines is fixed and the number of machines interrupted is more than two. The pseudo-polynomial time dynamic programming algorithm is designed, and the corresponding problem is proved to be general NP-hard.Whether the problem is NP-hard is unknown when interrupts occur on only one machine.
【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O223

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 黃峰;丁亞武;;人機(jī)協(xié)同模式下的手工調(diào)度技術(shù)研究[J];黑龍江科技信息;2011年35期

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

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

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

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

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

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

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

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

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

相關(guān)會(huì)議論文 前10條

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

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

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

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

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

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

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

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

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

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

相關(guān)重要報(bào)紙文章 前2條

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

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

相關(guān)博士學(xué)位論文 前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)陣列計(jì)算：體系結(jié)構(gòu)，設(shè)計(jì)方法與程序映射技術(shù)研究[D];國(guó)防科學(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年

相關(guān)碩士學(xué)位論文 前10條

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

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

3 崔雪源;基于遺傳模擬退火算法的航班著陸調(diào)度問題[D];華中師范大學(xué);2015年

4 王翠;基于超圖模型和相繼干擾消除的鏈路調(diào)度問題的研究[D];曲阜師范大學(xué);2015年

5 張勇;帶拒絕和釋放時(shí)間的單機(jī)批調(diào)度問題[D];山東大學(xué);2015年

6 吳凡;基于粒子群優(yōu)化算法的風(fēng)電-火電機(jī)組組合調(diào)度研究[D];華北電力大學(xué);2015年

7 趙虎;MTO模式下的制造企業(yè)穩(wěn)健型調(diào)度問題研究[D];重慶理工大學(xué);2015年

8 吉佳紅;基于細(xì)菌覓食算法的改進(jìn)及應(yīng)用研究[D];江蘇科技大學(xué);2015年

9 周超;柔性作業(yè)車間批量問題研究[D];寧波大學(xué);2014年

10 趙興野;工序順序柔性作業(yè)車間描述與調(diào)度研究[D];大連理工大學(xué);2015年

，

本文編號(hào)：1699248