儲(chǔ)澤楠，王慶喜

(安陽(yáng)工學(xué)院 計(jì)算機(jī)科學(xué)與信息工程學(xué)院, 河南 安陽(yáng) 455000)

0 引言

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

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

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

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

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

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

(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)表示目標(biāo)函數(shù)，式(2)表示工藝約束條件決定的每個(gè)工件的操作先后順序，式(3)表示加工每個(gè)工件的每臺(tái)機(jī)器的先后順序.式(3)和式(4)中的Cik和pik分別為工件i在機(jī)器k上的完成時(shí)間和加工時(shí)間，M是一個(gè)足夠大的正數(shù)，aihk和xijk分別為指示系數(shù)和指示變量，其含義為：

(6)

(7)

2 布谷鳥(niǎo)搜索算法

2.1 算法仿生原理

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

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

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

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

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

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

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

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

(8)

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

萊維飛行本質(zhì)上提供了一個(gè)隨機(jī)行走，而隨機(jī)步長(zhǎng)來(lái)自L(fǎng)evy分布：

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

(9)

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

2.3 算法流程

綜上所述，布谷鳥(niǎo)算法流程如下：

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

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

3)計(jì)算每個(gè)鳥(niǎo)窩的目標(biāo)函數(shù)值，并記錄當(dāng)前最優(yōu)鳥(niǎo)窩位置(解決方案)；

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

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

6)將現(xiàn)有鳥(niǎo)窩位置與上一代鳥(niǎo)窩位置進(jìn)行對(duì)比，若較好，則將其作為當(dāng)前的最好位置；

7)如若未滿(mǎn)足結(jié)束條件，則返回3；

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

3 離散布谷鳥(niǎo)搜索算法

3.1 算法思想

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

3.2 編碼方式

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

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

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

表1 鳥(niǎo)窩位置及其對(duì)應(yīng)的ROV值

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

3.3 求解JSP步驟

DCS算法的實(shí)施過(guò)程與步驟如下:

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

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

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

5 結(jié)語(yǔ)

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

表2 PSO、FA和CS算法比較結(jié)果

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