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

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

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

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

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

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

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

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

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

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