Job-shop調(diào)度問題的離散布谷鳥搜索算法求解

儲澤楠，王慶喜

(安陽工學院 計算機科學與信息工程學院, 河南 安陽 455000)

0 引言

作業(yè)車間調(diào)度問題(Job-shop scheduling problem, JSP)是一類滿足任務配置和順序約束要求的資源分配的調(diào)度問題，具有廣泛的應用背景，譬如生產(chǎn)制造、交通規(guī)劃、郵電通信、大規(guī)模集成電路設計等問題.JSP已被證明是一個典型的NP-hard問題[1]，它的求解難度遠大于流水線調(diào)度問題，針對其算法的研究一直是學術界和工程界共同關注的重要課題.

目前，制造業(yè)的競爭日益激烈，制造企業(yè)正朝著有不同完工時間和產(chǎn)品要求的多類型、小批量的生產(chǎn)模式發(fā)展.如何利用現(xiàn)有的資源，滿足加工任務所需的各種約束，使所有的任務能盡量按時完成，即如何有效地解決JSP問題，就成為一個十分現(xiàn)實和迫切的問題[2].

1 Job-shop調(diào)度問題描述

Job-shop調(diào)度問題描述為：n個工件在m臺機器上加工，Oij表示第i個工件在第j臺機器上的操作，相應的操作時間Tij為已知，事先給定各工件在各機器上的加工次序，要求確定與技術約束條件相容的各機器上所有工件的加工次序，使加工性能指標達到最優(yōu).在Job-shop問題中，通常假定每一時刻每臺機器只能加工一個工件，且每個工件只能被一臺機器所加工，同時加工過程為不間斷，機器間緩沖區(qū)容量為無限.Job-shop調(diào)度問題是一類典型的加工調(diào)度問題，是許多實際問題的簡化模型[2].

關于JSP的求解往往要考慮生產(chǎn)調(diào)度實際期望達到的優(yōu)化指標，問題的目標函數(shù)是這些優(yōu)化指標的抽象表示，JSP模型的目標函數(shù)隨著企業(yè)所重點考慮因素的不同而改變.通常JSP所考慮的優(yōu)化目標有3種[3]：任務的最大完工時間最短、任務的總的拖期最短和任務的提前/拖期懲罰代價最小.本文所考慮的優(yōu)化目標是任務的最大完工時間最短，即完成所有任務所需的時間最短，對該指標的優(yōu)化有利于提高單位時間內(nèi)設備的利用率，從而提高生產(chǎn)的實際效率.

常見的作業(yè)車間調(diào)度問題基本數(shù)學模型有3種：整數(shù)規(guī)劃模型、線性規(guī)劃模型和析取圖模型.本文采用Bake[4]給出的JSP整數(shù)規(guī)劃模型，其調(diào)度問題可描述為：

(1)

Subject to:

Cik-pik+M(1-aihk)≥Cih,

(2)

Cjk-Cik+M(1-xijk)≥pjk,

(3)

Cik≥0,

(4)

xijk=0或1.

(5)

其中：i,j=1,2,…,n;h,k=1,2,…,m.

式(1)表示目標函數(shù)，式(2)表示工藝約束條件決定的每個工件的操作先后順序，式(3)表示加工每個工件的每臺機器的先后順序.式(3)和式(4)中的Cik和pik分別為工件i在機器k上的完成時間和加工時間，M是一個足夠大的正數(shù)，aihk和xijk分別為指示系數(shù)和指示變量，其含義為：

(6)

(7)

2 布谷鳥搜索算法

2.1 算法仿生原理

在自然界中，布谷鳥通過巢寄生的行為方式進行繁育，巢寄生是指鳥類將卵產(chǎn)在其他鳥的鳥巢中，由其他鳥代為孵化和育雛的一種特殊的繁殖行為[5].在宿主的選擇上，布谷鳥在繁殖期尋找與孵化期和育雛期相似、雛鳥食性基本相同、卵形與顏色易仿的宿主，多為雀形目鳥類.而且它每飛到一個巢窩里只產(chǎn)一個卵，布谷鳥在產(chǎn)卵前常把宿主一枚卵移走，或全部推出巢外，迫使宿主重新產(chǎn)卵，來增加其卵被孵化的概率.為了繁衍宿主鳥也進化出一套反寄生行為，宿主一旦識別出寄生卵，就將其扔出或棄巢，在其他地方另建新巢.巢寄生的協(xié)同進化表現(xiàn)在長期的適應選擇中，寄生卵的大小、顏色、卵斑等特征都與其特定的宿主相似，這有利于降低其卵被拋棄的可能性并因此增加其繁殖率.

研究表明，很多動物和昆蟲的飛行行為表現(xiàn)出萊維飛行的典型特征[6].萊維飛行屬于隨機行走的一種，在萊維飛行中步長分布滿足一個重尾的穩(wěn)定分布，在這種形式的行走中，短距離的探索與偶爾較長距離的行走相間.目前萊維飛行行為已被用于優(yōu)化和最優(yōu)搜索領域，具有擴大搜索范圍、增加種群多樣性、易跳出局部最優(yōu)點等特征[7].

2.2 算法的數(shù)學描述與分析

為了便于描述布谷鳥算法，本算法基于以下三個理想化的規(guī)則[8]：

1)每只布谷鳥一次產(chǎn)一個卵，并把它的卵產(chǎn)在隨機選擇的巢中進行孵化；

2)帶有優(yōu)質(zhì)卵(或解決方案)的最優(yōu)鳥巢將會保留到下一代；

3)宿主鳥巢數(shù)量固定，宿主發(fā)現(xiàn)外來卵的概率為pa，在宿主識別出寄生卵的情況下，宿主可能將其扔出或棄巢，并在其他地方另建新巢.為了簡單起見，假定pa為一個固定值.

用CS算法在多維空間尋找最優(yōu)解，對于最大化問題，解決方案的質(zhì)量或適應值可以簡單地與目標函數(shù)值成比例，在本算法中其他形式的適應值可以使用類似于遺傳算法中適應函數(shù)的方式進行定義.為了簡單起見，我們可以使用下面的簡單陳述即一個巢里的每個蛋代表一種解決方案，以及一個布谷鳥蛋代表了一種新的解決方案，目的是利用新的以及潛在更好的解決方案(布谷鳥)取代巢里一個不那么好的解決方案[9].

(8)

其中，α>0為步長大小，與所研究問題的范圍有關.在大多數(shù)情況下，取α=1.式(8)本質(zhì)上是隨機行走的一個隨機方程，一般情況下，一個隨機行走是一個馬爾科夫鏈，其下一個狀態(tài)或位置只取決于當前的位置(上述方程的第一項)和轉(zhuǎn)移概率(第二項).⊕為點對點乘法，這與PSO算法相似.但是本算法中通過萊維飛行的隨機行走能夠更有效地探索搜索空間，因為從長遠來看它的步長更長.

萊維飛行本質(zhì)上提供了一個隨機行走，而隨機步長來自Levy分布：

L=t-λ(1<λ≤3).

(9)

該分布有一個無窮方差和無窮均值.其步長本質(zhì)上構成一個隨機行走過程.其中一些新解應該由萊維行走在目前所獲得最優(yōu)解附近產(chǎn)生，這將加快局部搜索速度.然而相當部分的最優(yōu)解應該由遠場隨機搜索產(chǎn)生，其位置應離當前最優(yōu)解足夠遠，這將確保系統(tǒng)不會陷入局部最優(yōu).

2.3 算法流程

綜上所述，布谷鳥算法流程如下：

1)設置算法參數(shù)；

2)目標函數(shù)f(x),x=(x1,x2,…,xd)T，隨機產(chǎn)生n個鳥窩的初始位置xi(i=1,2,…,n)，進行初始化；

3)計算每個鳥窩的目標函數(shù)值，并記錄當前最優(yōu)鳥窩位置(解決方案)；

4)保留上代最優(yōu)鳥窩位置，并按位置更新公式(1)對其他鳥窩位置進行更新；

5)對每一鳥窩按條件更新位置：用一個隨機數(shù)pa作為鳥窩主人發(fā)現(xiàn)外來鳥蛋的可能性并與p0進行比較，若pa>p0，則隨機改變鳥窩位置.否則，保持原來位置，得到一組新的鳥窩位置；

6)將現(xiàn)有鳥窩位置與上一代鳥窩位置進行對比，若較好，則將其作為當前的最好位置；

7)如若未滿足結束條件，則返回3；

8)輸出全局最優(yōu)位置.

3 離散布谷鳥搜索算法

3.1 算法思想

原始布谷鳥算法只能解決連續(xù)性問題，對于JSP這類離散型的組合優(yōu)化問題無能為力，因為布谷鳥初始化位置以及更新后的位置數(shù)據(jù)都是一個范圍內(nèi)的實數(shù)，而JSP問題的數(shù)據(jù)是表示加工順序的序列值以及加工時間.因此本文為了處理離散型問題，求解JSP，把鳥窩位置的數(shù)據(jù)進行編碼，編碼成JSP問題中的加工順序.

3.2 編碼方式

Job-shop調(diào)度問題最常用的編碼方式是直接采用工件的排序.由于CS算法中鳥窩位置為連續(xù)值矢量，標準CS算法無法實現(xiàn)工件排序的更新，因此構造從鳥窩位置到工件排序的恰當映射是應用CS算法解決JSP的首要和關鍵問題.利用編碼完善后的布谷鳥搜索算法(CS)本文稱為離散布谷鳥搜索算法(DCS).

雖然鳥窩位置矢量xi=[xi,1,xi,2,…,xi,n]本身無法表示加工工件的排序，但基于升序排列(Ranked Order Value, ROV)規(guī)則可以利用各個位置分量值的大小次序關系，結合隨機鍵進行編碼，將鳥窩的連續(xù)位置xi=[xi,1,xi,2,…,xi,n]轉(zhuǎn)換為機器上各工件的離散的加工工序π=[j1,j2,…,jn]，從而計算出鳥窩所對應調(diào)度方案的目標值.通過這種轉(zhuǎn)化，無須修改CS算法的進化操作，并能夠保證調(diào)度方案的可行性.

ROV規(guī)則的具體描述如下：對于一個鳥窩位置矢量，首先將值最小的分量位置賦予ROV值1，其次將值第二小的分量位置賦予ROV值2，依此類推，最終所有分量位置都會被賦予唯一的一個ROV值，繼而根據(jù)ROV值就可產(chǎn)生一個工件排序.在表1中用一個簡單的例子來說明ROV規(guī)則的工作原理和過程.

表1 鳥窩位置及其對應的ROV值

例如考慮5個工件的置換流水線調(diào)度問題，鳥窩位置為5維矢量，假設位置矢量為xi=[0.06,2.99,1.86,3.73,0.67]，則首先賦予最小分量位置xi,1的ROV值為1，接下來賦予xi,5對應的分量位置ROV值為2，然后分別賦予xi,3,xi,2和xi,4對應的分量位置ROV值為3、4、5，從而得到工件的加工次序，即π=[1,4,3,5,2].

3.3 求解JSP步驟

DCS算法的實施過程與步驟如下:

4 仿真實驗

鑒于JSP的重要性和代表性，許多研究工作者設計了若干典型問題(benchmarks)，用以測試和比較不同方法的優(yōu)化性能，典型的Job-shop調(diào)度問題有FT類、LA類、ABZ類、ORB類、SWV類、YN類、TD類和DMU類等，其中以FT類、LA類和TD類調(diào)度問題的研究居多.LA類問題由Lawrence(1984)給出，包括40個典型問題，命名為LA1-LA40，對應8個不同規(guī)模(每一規(guī)模包含5個問題)，分別為10×5、15×5、20×5、10×10、15×10、20×10、30×10、15×15.為了便于比較并驗證布谷鳥搜索算法(CS)求解JSP的性能，本研究選取LA1～LA20基準問題作為算例進行仿真測試，并與基本粒子群算法(Basic particle swarm optimization, BPSO)和螢火蟲算法(Firefly Algorithm, FA)所得結果進行比較.

實驗仿真環(huán)境為：操作系統(tǒng)Windows XP，CPU Intel G630 2.7 GH和內(nèi)存2 G，采用仿真軟件matlab7.8實現(xiàn)算法編程.算法參數(shù)設置如下：布谷鳥搜索算法中，鳥巢個數(shù)n=30，宿主鳥發(fā)現(xiàn)外來鳥蛋的概率pa=0.25；螢火蟲算法中，螢火蟲數(shù)n=30，光強吸引系數(shù)γ=1.0，最大吸引度β0=1.0，步長因子α=0.2；基本n粒子群算法中，粒子數(shù)n=30，學習因子c1=0.8,c2=1.2，慣性權重w=0.5.最大迭代次數(shù)均為1000，每種算法均獨立運行50次，測試結果如表2所示.

5 結語

本文對布谷鳥搜索算法的優(yōu)化機理進行了分析，并使用離散編碼方式完善原始布谷鳥算法，提出離散布谷鳥算法，使布谷鳥搜索算法能夠解決離散型問題.該算法是基于自然界中布谷鳥種類的巢寄生行為，并結合萊維飛行提高算法的全局搜索效率，可用于解決各種復雜優(yōu)化問題.該算法具有算法參數(shù)少，以及很好把握了局部搜索和全局搜索之間的平衡等優(yōu)點.通過將離散布谷鳥搜索算法用于置換流水車間調(diào)度問題的研究，并與FA和PSO算法進行比較研究，顯示出了DCS算法的有效性、快速收斂性和較強魯棒性，表明了DCS算法在解決離散空間優(yōu)化問題的可行性和有效性，具有良好的應用前景.

表2 PSO、FA和CS算法比較結果

注： c為問題已知最優(yōu)值；min為算法50次仿真得到的最小完工時間；max為最大完工時間；avg平均完工時間；std完工時間標準方差(其中avg、std為四舍五入后所得結果).