約束滿足技術的研究及在生產(chǎn)調(diào)度中的應用.pdf

1、生產(chǎn)管理是提高現(xiàn)代生產(chǎn)企業(yè)生產(chǎn)效率和經(jīng)濟效益的重要手段。生產(chǎn)調(diào)度是生產(chǎn)管理系統(tǒng)關鍵的核心技術。單件車間調(diào)度問題是生產(chǎn)調(diào)度領域最為復雜的一類典型調(diào)度問題，由于其背景廣泛存在于工業(yè)生產(chǎn)、醫(yī)療、交通、運輸、通訊等領域中，同時也由于其調(diào)度模型可以看成是單機、并行機和流水車間調(diào)度等相對簡單模型的一般化推廣，因而對其建模和算法的研究，備受學術界和工業(yè)界的廣泛關注，是公認的難題。
　　 由于一般的單間車間調(diào)度問題屬于強NP-難問題，探討問題的

2、最優(yōu)解極為困難。如果再考慮到生產(chǎn)環(huán)境的實時性和動態(tài)性等方面的特點，則大量問題成為NP-完全問題，即使是可行解有時也難以獲得，因此探討該類問題的可行的近似算法具有實際意義。
　　 本文針對一般單件車間調(diào)度問題、復雜單件車間調(diào)度問題、實時單件車間調(diào)度問題、動態(tài)反應單件車間調(diào)度問題，基于約束滿足思想與理論，從增量構造式和重復修補式兩大類方法，約束傳播、搜索策略、啟發(fā)式的集成與嵌入、學習機制四個方向研究約束滿足技術，分別建立了相應問題的

3、約束滿足優(yōu)化模型及約束網(wǎng)絡結構模型，提出并設計了基于約束滿足技術的求解算法。具體研究內(nèi)容包括：
　　 1)基于增量構造式方法，通過分析傳統(tǒng)運籌學方法與約束滿足求解方法各自優(yōu)缺點，提出集成約束傳播技術和分支定界方法的混合求解策略，設計并構造帶有時間窗口的分支定界搜索樹，實現(xiàn)在每個樹節(jié)點處的瞬時約束傳播，并以最大完工時間最小化的單件車間調(diào)度問題為背景對提出的混合方法進行了應用研究。
　　 2)基于增量構造式方法，建立一種構造

4、式的約束滿足優(yōu)化模型，提出并實現(xiàn)該問題模型的弧一致約束傳播優(yōu)化算法，并在搜索過程中的每個節(jié)點處，設計并嵌入多種動態(tài)加強約束傳播技術，通過這些技術指導搜索節(jié)點的擴展方向的篩選，從而提高搜索效率。針對以最大完工時間最小化為目標的，帶有公共釋放期與交貨期的單件車間調(diào)度問題，對所建立的模型和提出的算法進行應用研究。
　　 3)基于重復修補式方法，建立一種針對大規(guī)模優(yōu)化問題的GENET網(wǎng)絡結構約束滿足優(yōu)化模型，在GENET網(wǎng)絡結構中，設計

5、并構建記入新約束的約束傳播框架，提出該模型的基于漸進式隨機搜索模式的求解方法，并針對單件車間約束滿足優(yōu)化問題，進行應用研究，實現(xiàn)問題映射、約束網(wǎng)構造及修補式優(yōu)化策略。
　　 4)基于重復修補式方法，針對問題中的研究對象，建立嵌入限定窗口約束的GENET網(wǎng)絡結構約束滿足優(yōu)化模型，提出具有漸進式隨機搜索模式、同時嵌入多種啟發(fā)式的求解算法。針對以拖拉工件數(shù)最小化為目標的，工件帶有不同釋放期和交貨期的單件車間調(diào)度問題，對提出的建模與優(yōu)化

6、方法進行應用研究。
　　 5)基于重復修補式方法，針對問題研究對象所需要的資源，建立嵌入多種形式不連續(xù)窗口約束的GENET網(wǎng)絡結構約束滿足優(yōu)化模型，提出該模型的具有漸進式隨機搜索模式、嵌入啟發(fā)式的求解算法，并針對以平均拖拉量百分比最小化為目標的，具有單一停工和多次停工等三種機器無效約束情況下的單件車間調(diào)度問題，進行了應用研究。
　　 6)基于重復修補式方法，建立嵌入強制限定窗口約束（硬約束）的GENET網(wǎng)絡結構約束滿足優(yōu)

7、化模型，提出在此類網(wǎng)絡模型中，實現(xiàn)多重優(yōu)化目標的重復修補式搜索策略，以及嵌入啟發(fā)式規(guī)則的學習方法。針對帶有滿足截止期和最大完工時間最小雙重準則的單件車間在線實時調(diào)度問題，對所提出的方法進行應用研究，通過嵌入一個由最早截止期優(yōu)先策略改良而來的啟發(fā)式和一個優(yōu)化機制，實現(xiàn)在滿足截止期約束的前提下的調(diào)度目標最優(yōu)化。
　　 7)基于重復修補式方法，建立具有對多重動態(tài)擾動調(diào)整與修復能力的GENET網(wǎng)絡結構約束滿足優(yōu)化模型，提出一種可重復修補

8、的局部搜索方法，實現(xiàn)使初始構造的原問題約束網(wǎng)絡保持對外界多重動態(tài)擾動的調(diào)整與修復，并針對單件車間發(fā)生機器損壞和緊急工件雙重擾動時，調(diào)度目標為在滿足新調(diào)度的可行性的情況下，使新調(diào)度與原調(diào)度間的差別最小化的動態(tài)反應調(diào)度問題，進行了應用研究。
　　 8)針對現(xiàn)實中非二元約束滿足問題的廣泛存在，以及E-GENET在處理非二元約束滿足問題上，既缺乏理論依據(jù)的支持，又缺少實際問題檢驗的情況，在對非二元約束滿足問題和E-GENET網(wǎng)絡模型能量

9、函數(shù)進行新的數(shù)學定義基礎上，將非二元約束滿足問題轉化為整數(shù)最小化問題，提出一類非二元變量約束關系的離散拉格朗日搜索模式與算法，建立E-GENET與離散拉格朗日乘子方法間的連接關系，對E-GENET進行重構與擴展，研究了E-GENET解決多元過約束問題求解原理，同時給出了相關的證明，并針對傳統(tǒng)單件車間調(diào)度問題，進行應用研究。
　　 9)在上述研究的基礎上，為了對提出的方法和進一步研究方法的有效性進行實驗驗證，探討在工業(yè)應用的可能性