兩類(lèi)知識(shí)化制造單元的自進(jìn)化研究.pdf

1、對(duì)于自動(dòng)化生產(chǎn)程度很高的制造企業(yè)，實(shí)時(shí)調(diào)度以及再調(diào)度的存在要求系統(tǒng)在極短的時(shí)間內(nèi)能夠給出新的最優(yōu)調(diào)度方案，然而諸多調(diào)度問(wèn)題的NP難求解特性不但使這一任務(wù)變得幾乎難以實(shí)現(xiàn)（尤其當(dāng)問(wèn)題的規(guī)模變大時(shí)），而且迄今為止在理論上對(duì)于這類(lèi)問(wèn)題仍未給出其有效的求解算法。因此設(shè)計(jì)能夠逐步提高自身調(diào)度性能的算法成為一個(gè)合理而可行的選擇。Flow-shop問(wèn)題和Job-shop問(wèn)題是兩類(lèi)應(yīng)用比較廣泛的生產(chǎn)調(diào)度模型，作為NP難問(wèn)題關(guān)于它們的有效求解調(diào)度算法至今

2、也未被給出，本文以這兩類(lèi)問(wèn)題為基礎(chǔ)，對(duì)相應(yīng)的知識(shí)化制造單元調(diào)度算法的自進(jìn)化性能進(jìn)行了研究。
　　具體而言，主要在如下幾個(gè)方面進(jìn)行了研究:
　　1.針對(duì)以最大完工期為調(diào)度目標(biāo)的流水型知識(shí)化制造單元提出了一種能夠持續(xù)改善其求解性能的自進(jìn)化算法。算法在搜索最優(yōu)解的過(guò)程中對(duì)當(dāng)前解采取合適的動(dòng)作以得到新的解，理論上如果每次采取的動(dòng)作都是正確的，則最終得到最優(yōu)解，因此動(dòng)作的選擇是解決問(wèn)題的關(guān)鍵。為了提高動(dòng)作選擇的準(zhǔn)確度，提出以Q學(xué)習(xí)中q

3、因子的值選取動(dòng)作。針對(duì)系統(tǒng)狀態(tài)隨著問(wèn)題規(guī)模變大而急劇增加所導(dǎo)致的q因子難以求取的問(wèn)題，提出用支持向量機(jī)通過(guò)Q學(xué)習(xí)中基于值迭代的學(xué)習(xí)訓(xùn)練實(shí)現(xiàn)對(duì)q因子進(jìn)行擬合。為了提高支持向量機(jī)的擬合性能，提出了一種兼具高斯函數(shù)和多項(xiàng)式函數(shù)優(yōu)點(diǎn)的混合函數(shù)并證明該函數(shù)滿(mǎn)足核函數(shù)要求。設(shè)計(jì)了系統(tǒng)狀態(tài)特征指標(biāo)并將其與動(dòng)作值一起作為所提支持向量機(jī)的輸入。數(shù)值仿真表明所提支持向量機(jī)對(duì)于動(dòng)作的選取能力隨著學(xué)習(xí)過(guò)程的增加而逐步提高。
　　2.對(duì)Job-shop型知

4、識(shí)化制造單元自進(jìn)化策略進(jìn)行了研究并提出了一種以最大完工期為調(diào)度目標(biāo)的自進(jìn)化算法。首先對(duì)Job-shop型知識(shí)化制造單元結(jié)構(gòu)進(jìn)行了分析，然后定義了動(dòng)態(tài)開(kāi)工時(shí)間、動(dòng)態(tài)交貨期、動(dòng)態(tài)處理時(shí)間并構(gòu)建了其鏈約束模型。理論上如果每次能正確選擇要添加到該模型弧，則最終能夠得到最優(yōu)調(diào)度。為了正確地添加弧約束，給出了關(guān)于鏈路圖添加弧約束的性質(zhì)，并將操作對(duì)分為三類(lèi)，提出了可排操作對(duì)的判定方法并證明了該方法的有效性。為了準(zhǔn)確地選擇準(zhǔn)可排操作對(duì)，提出以訓(xùn)練過(guò)的q

5、因子的值進(jìn)行選取。由于系統(tǒng)狀態(tài)過(guò)多而導(dǎo)致q因子值不能通過(guò)標(biāo)準(zhǔn)Q學(xué)習(xí)而得到，為此提出以徑向基函數(shù)網(wǎng)絡(luò)通過(guò)訓(xùn)練實(shí)現(xiàn)對(duì)q因子的擬合，擬合過(guò)程遵循Q學(xué)習(xí)過(guò)程中值迭代思想。
　　3.對(duì)多目標(biāo)類(lèi)Job-shop結(jié)構(gòu)知識(shí)化制造單元調(diào)度自進(jìn)化策略進(jìn)行了研究并提出了一種以最大完工期、總加權(quán)完工期、任務(wù)的加權(quán)總拖期、拖期任務(wù)的加權(quán)總數(shù)、最大拖期為調(diào)度目標(biāo)的自進(jìn)化算法。建立了類(lèi)Job-shop結(jié)構(gòu)的知識(shí)化制造單元多目標(biāo)調(diào)度優(yōu)化模型，對(duì)多目標(biāo)間關(guān)系進(jìn)行了

6、分析并指出各目標(biāo)與各項(xiàng)任務(wù)完工期之間是非減函數(shù)關(guān)系。提出由關(guān)鍵弧所組成的各任務(wù)關(guān)鍵路徑的性質(zhì)并證明中間關(guān)鍵弧方向的改變不能優(yōu)化目標(biāo)函數(shù)值，以此為基礎(chǔ)提出一種縮減鄰域，采用該縮減鄰域能夠有效減少要搜索可行解的數(shù)目。為了準(zhǔn)確選取要改變方向的關(guān)鍵弧，結(jié)合所研究問(wèn)題提出一種自適應(yīng)啟發(fā)評(píng)價(jià)方法通過(guò)學(xué)習(xí)訓(xùn)練選取關(guān)鍵弧。設(shè)計(jì)了表示關(guān)鍵弧特征的向量作為聯(lián)想搜索單元和評(píng)價(jià)單元的輸入。聯(lián)想搜索模塊通過(guò)學(xué)習(xí)訓(xùn)練能夠逐步提高準(zhǔn)確選擇關(guān)鍵弧的能力。
　　4

7、.針對(duì)流水型知識(shí)化制造單元提出了一種以最大完工期為目標(biāo)且具進(jìn)化特性的調(diào)度算法，算法采用了深度優(yōu)先搜索的方法，能夠自動(dòng)變更搜索路徑以避免陷入局部最優(yōu)。為了減少鄰域內(nèi)要搜索可行解的數(shù)目，分別給出對(duì)關(guān)鍵任務(wù)實(shí)行插入和交換兩種操作所形成的新可行解的最大完工期的下界并且對(duì)所給下界進(jìn)行了證明。對(duì)于下界高于當(dāng)前解的最大完工期的操作不予實(shí)施，這樣極大減少了鄰域內(nèi)要搜索的可行解的數(shù)目并縮短了搜索時(shí)間。在此基礎(chǔ)上采用深度優(yōu)先搜索方法設(shè)計(jì)了一種帶回溯功能的可