

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、傳統(tǒng)的機器調度問題通常假定在整個調度期內機器一直可用。然而,在實際生產過程中,為了減少因機器失效或機器故障而導致的產品質量下降、維護成本增加和生產效率降低等問題,企業(yè)一般都會在調度期之前預先安排機器維護,因此在調度問題中考慮這種預防維護時間更具現(xiàn)實意義。
本文首先較為詳盡的研究了考慮維護時間的單機調度問題,包括維護時段固定且加工時間恒定、維護時段固定且加工時間可變、維護時段可調且加工時間恒定以及維護時段可調且加工時間可變等
2、四類問題。對于多機調度問題,重點研究了維護時段固定且加工時間恒定的問題,以此說明了把單機調度問題的求解方法拓展到相應多機調度問題的思路,其他三類問題均可按照這種思路進行求解。受維護時段的影響,工件在加工過程中可能會被中斷,基于實際生產過程中的不同情況,本文分別考慮了被中斷工件可續(xù)、不可續(xù)和部分可續(xù)三種情形。
上述問題的目標函數(shù)假定為與生產效率有關的最大完工時間及(加權)完工時間和。根據(jù)問題的復雜性不同,本文給出了不同的求解
3、方法:對于NP-難問題,本文一方面致力于設計能求解盡可能大規(guī)模問題的精確算法,另一方面,鑒于精確算法在時間和空間性能上的不足,本文也致力于構造高效的啟發(fā)式算法,從而能夠在合理的時間內求得大規(guī)模問題高質量的滿意解;另外,在某些特殊情形下,有些問題是多項式可解的,對于這些問題,本文通過證明某種多項式時間算法能夠為其提供最優(yōu)解來說明其多項式可解性。
具體而言,本文的主要研究內容和創(chuàng)新點如下:
(1)對于維護時段固定
4、且加工時間恒定的單機調度問題,研究了部分可續(xù)情形下的兩種目標函數(shù)。對于最大完工時間最小化問題,簡單說明了此問題的NP-難性,給出了最大加工時間優(yōu)先(Longest processing time first,LPT)規(guī)則的最壞情況相對誤差界,進而提出了兩個基于LPT 規(guī)則的啟發(fā)式算法:LPT-PI和MLPT,其中LPT-PI以LPT 規(guī)則作為初始解,并結合基于成對交換技術的鄰域搜索對解進行改進,而MLPT 通過改進LPT 算法執(zhí)行過程中
5、的某一類特殊情況來得到更優(yōu)的啟發(fā)式解。另外,還證明了MLPT的最壞情況相對誤差界,并通過大規(guī)模實驗對算法性能進行了對比分析。對于加權完工時間和最小化問題,簡單說明了問題的NP-難性,提出了最優(yōu)解的性質,并在此基礎上構造了動態(tài)規(guī)劃和分枝定界兩種精確算法。
大量隨機數(shù)據(jù)的實驗結果表明這兩種算法都是有效的,且不論從能解問題規(guī)模,還是從尋得最優(yōu)解所需時間方面,分枝定界算法都要優(yōu)于動態(tài)規(guī)劃算法。
(2)對于維護時段固定
6、且加工時間可變的單機調度問題,研究了最大完工時間及完工時間和兩種目標函數(shù)。證明了這兩種目標函數(shù)下加工時間線性增加和線性減少時的幾種可續(xù)情形是多項式可解的。對于不可續(xù)情形,重點研究了加工時間線性增加時的完工時間和問題。
對于該問題,簡單說明了其NP-難性,證明了最優(yōu)解的性質,在此基礎上構造了一種動態(tài)規(guī)劃算法,鑒于此算法應用上的局限性,給出了SNPT(Shortest normal processing time)規(guī)則的最壞情
7、況相對誤差界,進而提出了一種基于SNPT 規(guī)則和交換技術的啟發(fā)式算法。大量算例的實驗結果顯示不僅算法的運行時間很少,相對誤差也很?。ㄆ骄鄬φ`差和最大相對誤差分別為0.082%和3.448%),并且將近有一半的算例能得到最優(yōu)解,因此該啟發(fā)式算法能夠很高效的解決此類問題。而對于其他目標函數(shù)和加工時間函數(shù)下的不可續(xù)情形,通過分析與上述問題求解方法上的相似性,給出了其求解思路。
(3)對于維護時段可調的單機調度問題,重點研究了加
8、工時間恒定的問題,考慮了完工時間和這個目標函數(shù)。對于可續(xù)情形,給出了最優(yōu)解的幾個性質,提出了一種SPT 算法,并證明了其最優(yōu)性;對于不可續(xù)情形,簡單說明了其NP-難性,提出了幾個與可續(xù)情形類似的最優(yōu)解的性質和SPT 算法,給出了該算法最優(yōu)的條件,并證明了其最壞情況相對誤差界。在最優(yōu)解性質的基礎上,構造了一種動態(tài)規(guī)劃算法和一種分枝定界算法,其中分枝定界算法的初始解是在SPT 算法的基礎上利用兩條性質對維護時段之前的末工件和維護時段之后的工
9、件進行交換所得,而提出的幾個下界是基于維護時段固定的相應問題。實驗證明了動態(tài)規(guī)劃和分枝定界這兩種算法的有效性及互補性。對于加工時間可變的調度問題,首先證明了其可續(xù)情形是多項式可解的,并對此問題與相應加工時間恒定問題在求解方法上的相似性進行了總結,進而給出了不可續(xù)情形的求解思路。
(4)對于多機調度問題,重點研究了維護時段固定且加工時間恒定的問題,考慮了部分可續(xù)情形下的兩種目標函數(shù)。對于最大完工時間最小化問題,說明了問題的N
10、P-難性,建立了整數(shù)規(guī)劃模型,并提出了兩臺機器上工件互換的四條性質,進而提出了一種啟發(fā)式算法,該算法首先把所有工件按LPT 算法進行分配,得到一個可行解,然后再重復把最大完工時間最大和最小兩臺機器上的工件進行互換以提高解的質量。該啟發(fā)式算法和LPT 算法的對比實驗結果驗證了此算法的有效性;對于加權完工時間和最小化問題,說明了問題的NP-難性,給出了最優(yōu)解的性質,進而提出了一種動態(tài)規(guī)劃算法來求得中小規(guī)模問題的最優(yōu)解,另外還提出了一種基于W
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 5891.考慮作業(yè)釋放時間的在線機器調度問題研究
- 考慮機器故障特征的作業(yè)車間調度問題研究.pdf
- 考慮節(jié)能降耗的關鍵機器調度問題研究.pdf
- 考慮維護限制的置換流水車間調度問題研究.pdf
- 考慮機器使用成本的同類機調度問題.pdf
- 考慮機器使用成本的同類機調度問題
- 考慮調整時間的復雜產品綜合調度研究.pdf
- 帶機器維護的兩階段供應鏈調度問題的研究.pdf
- 考慮時間公平約束的機會調度算法研究
- 考慮維護和可中斷工件的混合型平行機調度問題研究.pdf
- 考慮時間公平約束的機會調度算法研究.pdf
- 云制造環(huán)境下考慮機器單位租用成本的同類機調度問題研究.pdf
- 維護時長隨機器負載線性遞增的單機調度問題.pdf
- 云制造環(huán)境下考慮機器單位租用成本的同類機調度問題研究
- 考慮釋放時間的可分任務調度模型與算法研究.pdf
- 考慮模具約束的生產調度問題研究.pdf
- 考慮退化的醫(yī)療設備調度問題研究.pdf
- 考慮待命位策略平面作業(yè)模式倉儲機器人調度問題研究.pdf
- 考慮能耗的混聯(lián)生產系統(tǒng)智能維護調度方法研究.pdf
- 考慮配合工序約束的生產調度問題研究.pdf
評論
0/150
提交評論