本文選題：調度　切入點：隨機干擾　出處：《昆明理工大學》2017年碩士論文

【摘要】：調度是運籌學與控制論學科的重要研究方方向,關于它的論文有很多。在這些經典的調度問題中,通常假設工件的加工時間通常為常數,并且在工件加工過程中機器可以持續(xù)加工工件。在這錯綜復雜的現實生活中,調度問題是不拘一格的,有時工件的實際加工時間隨其開始加工時間的推遲而增大,工作效率越來越低;有時工件的實際加工時間隨其開始加工時間的推遲而減小,工作效率越來越高;而有些情況下,工件的實際加工時間是與其所排位置相關的。與此同時,由于一些內部的原因和外部環(huán)境的限制,會使機器在加工過程中發(fā)生中斷,使機器不能持續(xù)工作。基于此,本文研究帶機器隨機故障和加工時間與位置相關的平行機調度問題。該問題中,工件的實際加工時間是與其所排位置相關的一般函數。在機器運行過程中,某些隨機事件的發(fā)生會導致部分機器不能正常工作。本文假設這些隨機事件的開始時間已知,且它們會以一定的概率持續(xù)一段時間。當隨機事件發(fā)生時,本文考慮工件可中斷和不可中斷兩種不同的情形下,目標是最小化工件總完成時間的期望。本文將對相應問題不同情形的復雜性進行分析并設計相應的偽多項式時間算法。具體研究內容如下:(1)工件不可中斷:在機器數量固定的情況下,證明了相應問題是NP難的,設計了偽多項式時間動態(tài)規(guī)劃算法,進而說明了相應問題是一般NP難的。具體地,本文僅詳細分析兩臺機器中有一臺機器發(fā)生中斷的情況,然后簡單討論如何將結論推廣到m臺機器中有K臺機器會發(fā)生中斷的情況。(2)工件可中斷:在機器的數量變化時,證明了相應的問題是強NP問題;在機器數量為固定值且發(fā)生中斷的機器大于等于兩臺的情況下,證明了該問題是NP難的,設計了偽多項式時間動態(tài)規(guī)劃算法,進而說明了相應問題是一般NP難的;然而,當中斷僅發(fā)生在一臺機器上時該問題是否為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.
【學位授予單位】：昆明理工大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O223

【相似文獻】

相關期刊論文 前10條

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

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

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

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

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

6 董平;機器調度問題及求解方法[J];物流技術與應用;1997年01期

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

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

9 黎鶴;孫廣中;許胤龍;;未知網絡中可分負載的分布式調度[J];中國科學技術大學學報;2009年08期

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

相關會議論文 前10條

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

2 劉海龍;黃小原;;總的未完工費用最小的多機調度問題[A];1995中國控制與決策學術年會論文集[C];1995年

3 沈吟東;曾西洋;;公共交通駕駛員調度的復雜性及解決方法[A];’2004計算機應用技術交流會議論文集[C];2004年

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

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

6 王成堯;汪定偉;;模糊加工時間的單機調度問題[A];1996中國控制與決策學術年會論文集[C];1996年

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

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

9 方濤;吳受章;;FMS的自適應調度:結構與算法研究[A];1992年中國控制與決策學術年會論文集[C];1992年

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

相關重要報紙文章 前2條

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

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

相關博士學位論文 前10條

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

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

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

4 湯雅連;關聯物流運輸調度問題研究[D];廣東工業(yè)大學;2015年

5 周理;高效可重構陣列計算：體系結構，設計方法與程序映射技術研究[D];國防科學技術大學;2014年

6 馮大光;一類批處理機調度的理論和方法研究[D];東北大學;2011年

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

8 楊磊;內容網絡中內容調度技術研究[D];重慶大學;2015年

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

10 丁寧;若干調度問題的算法研究[D];大連理工大學;2016年

相關碩士學位論文 前10條

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

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

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

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

5 張勇;帶拒絕和釋放時間的單機批調度問題[D];山東大學;2015年

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

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

8 吉佳紅;基于細菌覓食算法的改進及應用研究[D];江蘇科技大學;2015年

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

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

，

本文編號：1699248