趙　莉， 齊耀武

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

?

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

趙莉1， 齊耀武2

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

摘要：針對Job Shop調(diào)度問題，建立了離散非線性回饋神經(jīng)網(wǎng)絡(luò)優(yōu)化模型，給出了一種包含暫態(tài)混沌過程的神經(jīng)網(wǎng)絡(luò)優(yōu)化方法。通過在優(yōu)化神經(jīng)網(wǎng)絡(luò)中引入一個暫態(tài)的混沌過程，使得網(wǎng)絡(luò)的演化具備更為靈活的動力學特征。網(wǎng)絡(luò)狀態(tài)軌跡隨著自反饋系數(shù)的衰減，表現(xiàn)為一個典型的倍周期逆分叉過程，逐漸趨向于確定性的非線性回饋神經(jīng)網(wǎng)絡(luò)，并為其提供了一個接近全局最優(yōu)點的初值。其實質(zhì)是利用混沌搜索過程的隨機性和狀態(tài)遍歷性，加強神經(jīng)網(wǎng)絡(luò)的全局優(yōu)化能力，避免陷入局部極小點。仿真結(jié)果說明本文所建模型和優(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)度問題是按照一定的時間順序要求分配資源完成加工任務的生產(chǎn)調(diào)度問題，是生產(chǎn)過程中經(jīng)常遇見的問題。研究已證明它是NP困難問題[1，2]。顯然對于此類問題的研究和解決，既具有理論意義，也具有實用價值。在當今研究中，解決此類調(diào)度問題的主要方法可分為四類：仿真技術(shù)法[3]、組合優(yōu)化方法[4]、人工智能方法[5]和智能優(yōu)化方法[6，8]。回饋神經(jīng)網(wǎng)絡(luò)優(yōu)化是智能優(yōu)化方法中應用較為廣泛的方法之一，主要包括Hopfild線性回饋神經(jīng)網(wǎng)絡(luò)方法和非線性回饋神經(jīng)網(wǎng)絡(luò)方法[9]。

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

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

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

1.1JSP問題描述

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

(1)

Si1≥0, 1in;

(2)

(3)

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

(4)

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

對一n個工作m臺設(shè)備的JSP調(diào)度問題，可建立一包含n×m個神經(jīng)元的優(yōu)化系統(tǒng)，神經(jīng)元的輸出為工序(i,k)的起始加工時間Si,k，系統(tǒng)輸出狀態(tài)集為S=(s11,s12,...,snkn)。與Hopfield神經(jīng)網(wǎng)絡(luò)類似，非線性回饋網(wǎng)絡(luò)神經(jīng)元(i,k)的動態(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)度問題的目標函數(shù)描述為：

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

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

(7)

其中

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

前文已指出由(7)式所建立的神經(jīng)網(wǎng)絡(luò)在搜索過程中容易陷入局部極小，甚至導致結(jié)果收斂于不可行解。為此，在同步更新模式下，對上述神經(jīng)網(wǎng)絡(luò)進行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為自適應控制參數(shù)，其余皆為系統(tǒng)常數(shù)。(8)式為在每一神經(jīng)元新增一較大反饋后的動態(tài)方程，(11)式是(7)式的延伸，是為了保證在同一加工任務的前后工序發(fā)生時序沖突時約束傳播的雙向性。

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

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

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

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

考察神經(jīng)元動態(tài)方程：

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

2仿真實驗

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

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

表2工序時間表

任務i工序k123158227393171044117

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

表3　工序起始加工時間sik

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

圖1(a)系統(tǒng)的動力學過程樣力1圖

圖1(b)系統(tǒng)的動力學過程樣力2圖

圖2(a) uik動力學軌跡圖

圖2(b) uik動力學軌跡圖

圖2(c)目標函數(shù)Siki的動力學軌跡圖

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

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

在區(qū)間[0,5]上選取兩初始狀態(tài)值U′(0)和U″(0)，在相同條件下對暫態(tài)混沌神經(jīng)網(wǎng)絡(luò)和非線性回饋神經(jīng)網(wǎng)絡(luò)分別進行優(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é)果輸出圖

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

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

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

3結(jié)論

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

參考文獻：

[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].鄭彥譯，計算機集成制造系統(tǒ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]劉民，孫元凱，吳澄.TS+BS混合算法及其在job-shop調(diào)度問題上的應用[J].清華大學學報，2002,42(3):424-426.

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

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

[9]朱顥.基于智能優(yōu)化算法的Job Shop調(diào)度問題的研究[D].天津：天津大學，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]張長水,閻平凡.解Job-shop調(diào)度問題的神經(jīng)網(wǎng)絡(luò)方法[J].自動化學報, 1995, 21(6 ):706-712.

責任編輯：程艷艷

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

基金項目：吉林省計算與軟件科學創(chuàng)新平臺基金資助(60374061)

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

中圖分類號：TP18TP301

文獻標志碼：A

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