混沌優(yōu)化神經(jīng)網(wǎng)絡(luò)求解job-shop調(diào)度問(wèn)題研究

趙　莉， 齊耀武

(1.長(zhǎng)春大學(xué) 機(jī)械與車(chē)輛工程學(xué)院，長(zhǎng)春 130022；2.中東長(zhǎng)春軌道客車(chē)股份有限公司 轉(zhuǎn)向架制造中心，長(zhǎng)春 130062)

?

混沌優(yōu)化神經(jīng)網(wǎng)絡(luò)求解job-shop調(diào)度問(wèn)題研究

趙莉1， 齊耀武2

(1.長(zhǎng)春大學(xué) 機(jī)械與車(chē)輛工程學(xué)院，長(zhǎng)春 130022；2.中東長(zhǎng)春軌道客車(chē)股份有限公司 轉(zhuǎn)向架制造中心，長(zhǎng)春 130062)

摘要：針對(duì)Job Shop調(diào)度問(wèn)題，建立了離散非線性回饋神經(jīng)網(wǎng)絡(luò)優(yōu)化模型，給出了一種包含暫態(tài)混沌過(guò)程的神經(jīng)網(wǎng)絡(luò)優(yōu)化方法。通過(guò)在優(yōu)化神經(jīng)網(wǎng)絡(luò)中引入一個(gè)暫態(tài)的混沌過(guò)程，使得網(wǎng)絡(luò)的演化具備更為靈活的動(dòng)力學(xué)特征。網(wǎng)絡(luò)狀態(tài)軌跡隨著自反饋系數(shù)的衰減，表現(xiàn)為一個(gè)典型的倍周期逆分叉過(guò)程，逐漸趨向于確定性的非線性回饋神經(jīng)網(wǎng)絡(luò)，并為其提供了一個(gè)接近全局最優(yōu)點(diǎn)的初值。其實(shí)質(zhì)是利用混沌搜索過(guò)程的隨機(jī)性和狀態(tài)遍歷性，加強(qiáng)神經(jīng)網(wǎng)絡(luò)的全局優(yōu)化能力，避免陷入局部極小點(diǎn)。仿真結(jié)果說(shuō)明本文所建模型和優(yōu)化方法比傳統(tǒng)的非線性神經(jīng)網(wǎng)絡(luò)優(yōu)化方法具有更好的收斂性和更高優(yōu)化能力。

關(guān)鍵詞：Job Shop調(diào)度；神經(jīng)網(wǎng)絡(luò)優(yōu)化；混沌優(yōu)化

0引言

Job-shop(JSP)調(diào)度問(wèn)題是按照一定的時(shí)間順序要求分配資源完成加工任務(wù)的生產(chǎn)調(diào)度問(wèn)題，是生產(chǎn)過(guò)程中經(jīng)常遇見(jiàn)的問(wèn)題。研究已證明它是NP困難問(wèn)題[1，2]。顯然對(duì)于此類(lèi)問(wèn)題的研究和解決，既具有理論意義，也具有實(shí)用價(jià)值。在當(dāng)今研究中，解決此類(lèi)調(diào)度問(wèn)題的主要方法可分為四類(lèi)：仿真技術(shù)法[3]、組合優(yōu)化方法[4]、人工智能方法[5]和智能優(yōu)化方法[6，8]?；仞伾窠?jīng)網(wǎng)絡(luò)優(yōu)化是智能優(yōu)化方法中應(yīng)用較為廣泛的方法之一，主要包括Hopfild線性回饋神經(jīng)網(wǎng)絡(luò)方法和非線性回饋神經(jīng)網(wǎng)絡(luò)方法[9]。

FooS.Y.P.和Y.Takefuji最早提出將神經(jīng)網(wǎng)絡(luò)用于求解JSP問(wèn)題，并給出基于Hopfield神經(jīng)網(wǎng)絡(luò)的JSP優(yōu)化方法。他們通過(guò)建立工序交換矩陣和決策成本樹(shù)將JSP問(wèn)題轉(zhuǎn)換為T(mén)SP類(lèi)型的組合優(yōu)化問(wèn)題，并利用玻爾茲曼機(jī)和模擬退火方法進(jìn)行優(yōu)化求解。在此基礎(chǔ)之上，又有許多學(xué)者對(duì)其進(jìn)行研究并擴(kuò)展和完善了該方法[10-13]。然而此類(lèi)方法在建模時(shí)采用了過(guò)多數(shù)量的神經(jīng)元節(jié)點(diǎn)，以nxm規(guī)模的JSP問(wèn)題為例其需要建立nm×mn+nm個(gè)神經(jīng)元節(jié)點(diǎn)，這使得其難以應(yīng)用于大規(guī)模問(wèn)題優(yōu)化。鑒于此，Zhou D.N.等人提出了求解此類(lèi)問(wèn)題的非線性回饋神經(jīng)網(wǎng)絡(luò)優(yōu)化方法[6]。該方法針對(duì)任務(wù)時(shí)間狀態(tài)變量建模，對(duì)于nxm規(guī)模的問(wèn)題只需建立n×m個(gè)神經(jīng)元節(jié)點(diǎn)；并采用梯度搜索進(jìn)行優(yōu)化求解。顯然該方法建模復(fù)雜度低，更適于進(jìn)行大規(guī)模問(wèn)題的優(yōu)化求解。然而該方法在求解過(guò)程中，搜索難以保證狀態(tài)軌跡的全局遍歷性，簡(jiǎn)單的梯度搜索使其非常容易陷入局部極小，甚至導(dǎo)致結(jié)果收斂于不可行解，最終影響該方法的優(yōu)化性能。

為此，本文提出基于混沌神經(jīng)網(wǎng)絡(luò)的JSP優(yōu)化調(diào)度方法。該方法利用非線性回饋神經(jīng)網(wǎng)絡(luò)建立JSP調(diào)度問(wèn)題模型，通過(guò)對(duì)模型中的神經(jīng)元增加自反饋，使神經(jīng)元網(wǎng)絡(luò)中形成一暫態(tài)時(shí)變的倍周期逆分叉過(guò)程，并利用混沌動(dòng)力系統(tǒng)的全局遍歷性避免神經(jīng)元網(wǎng)絡(luò)陷入局部最優(yōu)點(diǎn)，達(dá)到增強(qiáng)算法的全局優(yōu)化能力的目的。仿真實(shí)驗(yàn)表明，該方法在計(jì)算時(shí)間和收斂性都有效地提高了原有的非線性回饋神經(jīng)網(wǎng)絡(luò)方法。

1暫態(tài)混沌神經(jīng)網(wǎng)絡(luò)JSP調(diào)度問(wèn)題建模

1.1JSP問(wèn)題描述

JSP調(diào)度問(wèn)題是服從分配和隊(duì)列限制的資源分配問(wèn)題，需要在設(shè)備資源上進(jìn)行加工的工件叫做任務(wù)；工件在某臺(tái)設(shè)備上的加工叫做一道工序或是一個(gè)子任務(wù)，每個(gè)工作是由多道工序或多個(gè)子任務(wù)組成的，這些工序之間具有先后次序的限制和要求。假設(shè)用I={1,2,…,n}代表工作集，用Ki={1,2,…ki}表示工作i的任務(wù)集或工序集，Sik表示工作i的第k道工序的開(kāi)工時(shí)間，m(i,k)表示工作i的第k道工序在設(shè)備m(i,k)上進(jìn)行加工，加工時(shí)間為ti,k。則JSP調(diào)度問(wèn)題就是滿足下列約束條件的某種準(zhǔn)則的優(yōu)化問(wèn)題：

(1)

Si1≥0, 1in;

(2)

(3)

其中式(1)表示任何工作的后一工序的加工起始時(shí)間一定要大于或等于前一工序的加工結(jié)束時(shí)間，式(2)表示每一工作的首工序加工起始時(shí)間要大于或等于零；式(3)表示在同一設(shè)備上加工的兩個(gè)工序m(i,k)=m(j,p)，或者工序(i,k)在工序(j,p)前面加工，或者工序(j,p)在工序(i,k)前面加工。在上述約束條件下，根據(jù)不同的優(yōu)化準(zhǔn)則可以得到不同JSP調(diào)度問(wèn)題。本文將以所有工作最后一道工序開(kāi)始時(shí)間總和最小為準(zhǔn)備，即JSP問(wèn)題的目標(biāo)函數(shù)為：

(4)

1.2暫態(tài)混沌神經(jīng)網(wǎng)絡(luò)JSP調(diào)度問(wèn)題建模

對(duì)一n個(gè)工作m臺(tái)設(shè)備的JSP調(diào)度問(wèn)題，可建立一包含n×m個(gè)神經(jīng)元的優(yōu)化系統(tǒng)，神經(jīng)元的輸出為工序(i,k)的起始加工時(shí)間Si,k，系統(tǒng)輸出狀態(tài)集為S=(s11,s12,...,snkn)。與Hopfield神經(jīng)網(wǎng)絡(luò)類(lèi)似，非線性回饋網(wǎng)絡(luò)神經(jīng)元(i,k)的動(dòng)態(tài)方程和網(wǎng)絡(luò)的能量函數(shù)可分別描述為：

(5)

(6)

其中，uik是神經(jīng)元(i,k)的內(nèi)部狀態(tài)，且sik=g(uik)，g(u)是u的單調(diào)遞增函數(shù)，fik(s)是神經(jīng)元(i,k)的輸入量，是關(guān)于系統(tǒng)輸出狀態(tài)集S的非線性函數(shù)，C,R分別為容抗和阻抗參數(shù)。

根據(jù)神經(jīng)網(wǎng)絡(luò)優(yōu)化的罰函數(shù)方法，可將JSP調(diào)度問(wèn)題的目標(biāo)函數(shù)描述為：

其中，A，B，C和D均為系統(tǒng)參數(shù)。當(dāng)x>0時(shí)令F1(x)=ebx-bx，F(xiàn)2(x)=ebx-1，否則令F1(x)=F2(x)=0。

令E=I，并對(duì)等式兩邊對(duì)sik微分可得，

(7)

其中

建立非線性回饋神經(jīng)網(wǎng)絡(luò)，并令神經(jīng)元的輸入fik(s)如(7)式所示，則當(dāng)所建立的非線性神經(jīng)網(wǎng)絡(luò)能量達(dá)到平衡時(shí)，系統(tǒng)輸出即為調(diào)度問(wèn)題的優(yōu)化結(jié)果。

前文已指出由(7)式所建立的神經(jīng)網(wǎng)絡(luò)在搜索過(guò)程中容易陷入局部極小，甚至導(dǎo)致結(jié)果收斂于不可行解。為此，在同步更新模式下，對(duì)上述神經(jīng)網(wǎng)絡(luò)進(jìn)行Eular離散化，

uik_new=α·uik(t)-β·(1+η·zik(t))·fik(s)-zik·(η·sik-s0)

(8)

uik=uik_new

(9)

(10)

(11)

zik_new=H1·γ1·zik(t)+(1-H1)·γ2·zik(t)

(12)

zik=zik_new

(13)

其中，

α是阻尼因子，β是輸入增益系數(shù)，0<γ2<γ1<1為衰減系數(shù)，z<λ為自反饋控制參數(shù)，s0為自反饋偏置參量，ω為輸出比例系數(shù)，H1為自適應(yīng)控制參數(shù)，其余皆為系統(tǒng)常數(shù)。(8)式為在每一神經(jīng)元新增一較大反饋后的動(dòng)態(tài)方程，(11)式是(7)式的延伸，是為了保證在同一加工任務(wù)的前后工序發(fā)生時(shí)序沖突時(shí)約束傳播的雙向性。

在上述神經(jīng)網(wǎng)絡(luò)模型中，該神經(jīng)網(wǎng)絡(luò)實(shí)質(zhì)上是由能在狀態(tài)空間表現(xiàn)出混沌行為的神經(jīng)元耦合而成的，其基本動(dòng)力學(xué)方程可以描述為：

uik(t+1)=α·uik(t)-zik(t)·(sik(t)-s0)

其中zik(t)·(sik(t)-s0)是神經(jīng)元的自抑制反饋?lái)?xiàng)，當(dāng)自反饋系數(shù)z增加到一定階段時(shí)，系統(tǒng)的動(dòng)力學(xué)過(guò)程即呈現(xiàn)出混沌現(xiàn)象。其動(dòng)態(tài)過(guò)程如圖1所示。

這種混沌現(xiàn)象具體表現(xiàn)為狀態(tài)值動(dòng)態(tài)遞推過(guò)程的隨機(jī)性和混沌遍歷性。利用狀態(tài)軌跡的隨機(jī)性可以保證大范圍的搜索能力，利用狀態(tài)軌跡的混沌遍歷性則可以保證系統(tǒng)安動(dòng)力學(xué)方程不重復(fù)的遍歷所有可能狀態(tài)，同時(shí)與梯度搜索過(guò)程結(jié)合，使得神經(jīng)網(wǎng)絡(luò)可以有效的避免局部最小點(diǎn)，收斂至全局最優(yōu)解。

考察神經(jīng)元?jiǎng)討B(tài)方程：

為避免初始反饋增益過(guò)大，導(dǎo)致?tīng)顟B(tài)收斂至混沌過(guò)程的固有不動(dòng)點(diǎn)，對(duì)影響梯度搜索的輸入增益系數(shù)β采用自適應(yīng)控制，令β′=β·(1+η·z)，即在混沌狀態(tài)采用高增益系數(shù)，隨者z不斷衰減，系統(tǒng)脫離混沌，β也變化為正常設(shè)定值，轉(zhuǎn)入梯度搜索。

2仿真實(shí)驗(yàn)

為分析混沌神經(jīng)網(wǎng)絡(luò)優(yōu)化過(guò)程中的非線性動(dòng)力學(xué)特性，對(duì)n=4,m=3的JSP調(diào)度問(wèn)題進(jìn)行仿真，系統(tǒng)參數(shù)如表1、表2所示。

表1　工序分配表m(i,k)

表2工序時(shí)間表

任務(wù)i工序k123158227393171044117

適當(dāng)調(diào)整系統(tǒng)初始狀態(tài)值U(0)，當(dāng)系統(tǒng)收斂時(shí)，可以得到經(jīng)優(yōu)化的各工序起始加工時(shí)間sik如表3所示，系統(tǒng)甘特圖如圖3所示。

表3　工序起始加工時(shí)間sik

由系統(tǒng)運(yùn)行軌跡圖可看出，在搜索開(kāi)始階段控制參數(shù)z較大，自抑制反饋很強(qiáng)，系統(tǒng)進(jìn)入混沌搜索過(guò)程，輸出狀態(tài)與系統(tǒng)內(nèi)部狀態(tài)軌跡呈現(xiàn)出隨機(jī)性與狀態(tài)遍歷性。此后控制參數(shù)z轉(zhuǎn)而進(jìn)入時(shí)變衰減，混沌軌跡表現(xiàn)為一個(gè)倍周期逆分叉的收斂軌跡，混沌現(xiàn)象逐漸消失，系統(tǒng)恢復(fù)為梯度搜索，直至得到最后結(jié)果。

圖1(a)系統(tǒng)的動(dòng)力學(xué)過(guò)程樣力1圖

圖1(b)系統(tǒng)的動(dòng)力學(xué)過(guò)程樣力2圖

圖2(a) uik動(dòng)力學(xué)軌跡圖

圖2(b) uik動(dòng)力學(xué)軌跡圖

圖2(c)目標(biāo)函數(shù)Siki的動(dòng)力學(xué)軌跡圖

圖2(d)自反饋控制參數(shù)z的動(dòng)態(tài)軌跡圖

圖3　系統(tǒng)甘特圖

在區(qū)間[0,5]上選取兩初始狀態(tài)值U′(0)和U″(0)，在相同條件下對(duì)暫態(tài)混沌神經(jīng)網(wǎng)絡(luò)和非線性回饋神經(jīng)網(wǎng)絡(luò)分別進(jìn)行優(yōu)化，定義滿意解為與最優(yōu)解相差小于5%，其輸出優(yōu)化結(jié)果分別如圖4(a)，(b)，(c)和(d)所示。

圖4(a)初始狀態(tài)值U′(0)非線性回饋神經(jīng)網(wǎng)絡(luò)優(yōu)化結(jié)果輸出圖

圖4(b)初始狀態(tài)值U′(0) 暫態(tài)混沌神經(jīng)網(wǎng)絡(luò)優(yōu)化結(jié)果輸出圖

圖4(c)初始狀態(tài)值U″(0) 非線性回饋神經(jīng)網(wǎng)絡(luò)優(yōu)化結(jié)果輸出圖

圖4(d)初始狀態(tài)值U″(0)暫態(tài)混沌神經(jīng)網(wǎng)絡(luò)優(yōu)化結(jié)果輸出圖

通過(guò)上述結(jié)果可以看出，在初始狀態(tài)條件下，一般非線性回饋神經(jīng)網(wǎng)絡(luò)一次收斂于一般有效解，一次收斂于非法解，而暫態(tài)混沌神經(jīng)網(wǎng)絡(luò)則均收斂于滿意解，優(yōu)化效果明顯好于前者。此外，再分別對(duì)普通非線性回饋網(wǎng)絡(luò)與混沌神經(jīng)網(wǎng)絡(luò)進(jìn)行200次優(yōu)化仿真，其優(yōu)化結(jié)果如下。

表4　優(yōu)化性能比較

由上述仿真結(jié)果可以看出，增加了暫態(tài)混沌過(guò)程的神經(jīng)網(wǎng)絡(luò)，由于混沌過(guò)程的隨機(jī)性和混沌遍歷性，使得神經(jīng)網(wǎng)絡(luò)系統(tǒng)一方面具備大范圍的搜索能力，系統(tǒng)狀態(tài)可以安動(dòng)力學(xué)方程不重復(fù)的遍歷多種可能狀態(tài)，有效避免能量函數(shù)的局部最小點(diǎn)，另一方面可以也減弱系統(tǒng)的初值敏感性，減少系統(tǒng)由于狀態(tài)初值選擇不恰當(dāng)而收斂至不可行解的可能性。上述仿真實(shí)驗(yàn)結(jié)果對(duì)此給出了很好的驗(yàn)證。

3結(jié)論

本文針對(duì)JSP調(diào)度問(wèn)題，給出了一種包含暫態(tài)混沌過(guò)程的非線性回饋神經(jīng)網(wǎng)絡(luò)優(yōu)化方法。通過(guò)引入一個(gè)暫態(tài)的混沌過(guò)程，使得神經(jīng)網(wǎng)絡(luò)的演化具備更為靈活的動(dòng)力學(xué)特征。隨著自反饋系數(shù)的不斷衰減，網(wǎng)絡(luò)狀態(tài)軌跡表現(xiàn)為一個(gè)倍周期逆分叉過(guò)程，并逐漸趨向于確定性的非線性回饋神經(jīng)網(wǎng)絡(luò)，并為其提供了一個(gè)接近全局最優(yōu)點(diǎn)的初值。其實(shí)質(zhì)是利用混沌搜索過(guò)程的隨機(jī)性和狀態(tài)遍歷性，加強(qiáng)神經(jīng)網(wǎng)絡(luò)的全局優(yōu)化能力，避免陷入局部極小點(diǎn)。仿真結(jié)果說(shuō)明了本文所建模型和優(yōu)化方法的有效性。

參考文獻(xiàn)：

[1]Foosy Takefujuy.Stochastic neural networks for solving job-shop scheduling: Parts I problem representation [C].Proceeding of the IEEE International Conference on Neural Networks,1988,275-282.

[2]Foosy Takefujuy. Stochastic neural networks for solving job-shop scheduling:Parts II .Architecture and simulations [C].Proceeding of the IEEE International Conference on Neural Networks,1988.283-290.

[3]Kiran Allen,Simth,Williamas.Job-Shop調(diào)度中的仿真研究[C].鄭彥譯，計(jì)算機(jī)集成制造系統(tǒng)譯文集，北京：中國(guó)科學(xué)院自動(dòng)化研究所，1988.

[4]Alan Smith Manne, On the Job-Shop Scheduling Problem [J]. Operations Research,1959,7(2):123-132.

[5]Eseale.Benaana,Gucci.Bel and David.Dubois.OPAL:A multi knowledge-based system for industrial job-shop scheduling [J].International Journal Production Research,1988,26(5):795-819.

[6]劉民，孫元?jiǎng)P，吳澄.TS+BS混合算法及其在job-shop調(diào)度問(wèn)題上的應(yīng)用[J].清華大學(xué)學(xué)報(bào)，2002,42(3):424-426.

[7]潘全科，王文宏，朱劍英.基于粒子群優(yōu)化和模擬退火的混合調(diào)度算法[J].中國(guó)機(jī)械工程，2006(10):953-957.

[8]韓世芬.基于模擬退火算法的Job Shop問(wèn)題研究[J].電腦與電信，2007(7):612-615.

[9]朱顥.基于智能優(yōu)化算法的Job Shop調(diào)度問(wèn)題的研究[D].天津：天津大學(xué)，2004.

[10]Zhou Deming,Charkassky Vladimir,Baldwin Tred.et al.Scaling neural network for job-shop scheduling [A].Proceedings IEEE International Joint Conference on Neural Networks[C].1989.889-894.

[11]Willems Thomas, Brandts Lem. Implementing heuristics as an optimization criterion in neural net works for job shop scheduling[J]. Journal of Intelligent Manufacturing, 1995; 6(2): 377-387.

[12]Chang Shui Zhang, Ping Fan Yan, Chang Tong. Solving job-shop scheduling problem with priority using neural net work [C]. Proceedings IEEE International Joint Conference on Neural Networks，1991，1361-1366.

[13]張長(zhǎng)水,閻平凡.解Job-shop調(diào)度問(wèn)題的神經(jīng)網(wǎng)絡(luò)方法[J].自動(dòng)化學(xué)報(bào), 1995, 21(6 ):706-712.

責(zé)任編輯：程艷艷

Research on a Solution to Job-shop Schedule Problems by Neural Network with Chaotic Optimization

ZHAO Li， QI Yaowu2

(1.College of Machinery and Vehicle Engineering, Changchun University, Changchun 130022, China；2.Bogie Manufacture Center,CRRC Changchun Railway Vehicles Co., Ltd., Changchun 130062, China)

Abstract：In view of Job-shop schedule problems, an optimized model of disperse nonlinear feedback neural network is established, and a neural network optimization method with transient chaos is given, which introduces a process of transient chaos to an optimized neural network, making its evolution have flexible dynamics features. With the reduction of self-feedback coefficient, the state trajectory is shown as a typical inverse bifurcation process, converging to a definite nonlinear feedback neural network and providing a globally near-optimal solution. The essence is to improve the global optimization ability by the randomness and ergodicity of chaos searching, so as to avoid sticking into the local minima. Simulation results indicate that the established model and optimized method have better convergence and higher optimization ability than the traditional nonlinear neural network optimization method.

Keywords：Job-shop schedule; neural network optimization; chaos optimization

收稿日期：2016-04

基金項(xiàng)目：吉林省計(jì)算與軟件科學(xué)創(chuàng)新平臺(tái)基金資助(60374061)

作者簡(jiǎn)介：趙莉(1972-)，女，吉林長(zhǎng)春人，副教授，碩士，主要從事工業(yè)工程及計(jì)算機(jī)應(yīng)用方面研究。

中圖分類(lèi)號(hào)：TP18TP301

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1009-3907(2016)06-0006-07