改進(jìn)布谷鳥算法求解雙資源約束柔性車間調(diào)度問題

摘要：針對(duì)雙資源約束的柔性車間調(diào)度問題（DRCFJSP），以優(yōu)化最大完工時(shí)間為目標(biāo)，設(shè)計(jì)出一種具有改進(jìn)解碼方案的布谷鳥算法對(duì)其進(jìn)行求解。由于DRCFJSP除了需要考慮機(jī)器的分配，還需要兼顧工人的加工情況，所以改進(jìn)了傳統(tǒng)解碼方式以避免機(jī)器和工人在加工時(shí)間上的沖突，同時(shí)在解碼時(shí)盡可能利用機(jī)器和工人的空閑時(shí)間。在布谷鳥算法核心框架下，將布谷鳥種群隨機(jī)劃分為三個(gè)子群，每個(gè)子群采用不同Lévy飛行方式獨(dú)立進(jìn)行尋優(yōu)，并通過差分算子實(shí)現(xiàn)子群間信息交流，不僅增強(qiáng)了算法的全局搜索能力，也平衡了算法的局部搜索能力。最后通過基準(zhǔn)測(cè)試算例進(jìn)行實(shí)驗(yàn)仿真分析并與其他算法進(jìn)行對(duì)比，驗(yàn)證了改進(jìn)布谷鳥算法和改進(jìn)解碼方法的有效性和優(yōu)越性。

關(guān)鍵詞：柔性車間調(diào)度；雙資源約束；布谷鳥算法；改進(jìn)解碼方法

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）08-009-2295-06

doi：10.19734/j.issn.1001-3695.2022.01.0030

Improved cuckoo algorithm for flexible Job-Shop scheduling with dual resource constraints

Luo Haojiaa，Pan Dazhia，b

（a.School of Mathematics amp; Information，b.Institute of Computing Methods amp; Applications，China West Normal University，Nanchong Sichuan 637009，China）

Abstract：Aiming at the flexible Job-Shop scheduling problem with dual resource constraints（DRCFJSP），this paper designed a cuckoo algorithm with an improved decoding scheme to solve it with the goal of optimizing the maximum completion time.Since DRCFJSP needs to consider the allocation of machines and the processing situation of workers，this paper improved the traditional decoding method to avoid the conflict of processing time between machines and workers，and made use of the idle time of machines and workers as much as possible during decoding.Under the core framework of the cuckoo algorithm，this paper divided the cuckoo population into three subpopulations randomly，and each subpopulation adopted different Lévy flight methods to search for the optimum independently，and realized the information exchange between subpopulations through the difference operator，which not only enhanced the global search ability of the algorithm，but also balanced the local search ability of the algorithm.Through the experimental simulation analysis of the benchmark test case，the results show the effectiveness and superiority of the improved cuckoo algorithm and the improved decoding method.

Key words：flexible Job-Shop scheduling；dual resource constraints；cuckoo algorithm；improved decoding method

0引言

調(diào)度在制造業(yè)和服務(wù)行業(yè)中起著至關(guān)重要的作用，作業(yè)車間調(diào)度問題作為調(diào)度中的典型問題，在制造系統(tǒng)領(lǐng)域得到了廣泛的關(guān)注。近些年也有很多基于作業(yè)車間調(diào)度的擴(kuò)展研究，如帶模糊加工時(shí)間的車間調(diào)度[1，2]、帶阻塞問題的車間調(diào)度[3～5]和多目標(biāo)車間調(diào)度[6，7]等，這些擴(kuò)展研究都是車間調(diào)度問題在實(shí)際情況中的應(yīng)用。雙資源約束柔性作業(yè)車間調(diào)度問題（dual resource constrained flexible Job-Shop scheduling problem，DRCFJSP）是柔性作業(yè)車間調(diào)度問題（flexible Job-Shop scheduling problem，F(xiàn)JSP）的一個(gè)擴(kuò)展，在FJSP的基礎(chǔ)上增加了工人這一約束條件，在進(jìn)行加工時(shí)需要兼顧工人和機(jī)器的加工情況，因此DRCFJSP比FJSP更接近實(shí)際生產(chǎn)情況。近些年來，也有一些元啟發(fā)式算法對(duì)DRCFJSP進(jìn)行研究，如Li等人[8]提出了一種分支種群遺傳算法，引入了基于扇區(qū)分割的輪盤選擇算子，利用精英進(jìn)化算子的優(yōu)化搜索能力，有效降低了算法復(fù)雜度，避免了算法早熟。Zhang等人[9]針對(duì)具有資源靈活性的雙資源約束作業(yè)車間調(diào)度問題，提出了一種新穎的混合離散粒子群優(yōu)化算法，引入了具有可變鄰域結(jié)構(gòu)的改進(jìn)模擬退火算法，提高了算法的局部搜索能力。Lei等人[10]提出了一種有效的變量鄰域搜索，通過兩個(gè)鄰域搜索程序依次執(zhí)行，分別為兩個(gè)子問題產(chǎn)生新的解決方案，從而增強(qiáng)算法的搜索能力。Zheng等人[11]提出了一種具有新編碼方案的知識(shí)引導(dǎo)果蠅優(yōu)化算法來求解最小化完工時(shí)間的DRCFJSP，將知識(shí)引導(dǎo)搜索和基于氣味搜索相結(jié)合，平衡了算法全局探索和局部開發(fā)能力。

布谷鳥搜索（cuckoo search，CS）算法[12]是由劍橋大學(xué)學(xué)者Yang和Deb于2009年通過模擬布谷鳥寄生育雛行為提出的一種新型元啟發(fā)式搜索算法。由于其所用參數(shù)少、全局搜索能力強(qiáng)等優(yōu)點(diǎn)，被普遍應(yīng)用于連續(xù)性優(yōu)化問題、調(diào)度問題、工程優(yōu)化問題等多個(gè)領(lǐng)域。Ouaarab等人[13]在不改變布谷鳥算法框架的情況下，將布谷鳥算法離散化，用于求解車間調(diào)度問題。Alaa等人[14]改進(jìn)CS算法中的Lévy飛行，加強(qiáng)對(duì)種群最優(yōu)個(gè)體領(lǐng)域的搜索，并將改進(jìn)后的算法用于求解柔性車間調(diào)度問題。Majumdera等人[15]針對(duì)作業(yè)準(zhǔn)備時(shí)間不相等的并行批處理機(jī)調(diào)度問題，提出了一種混合離散布谷鳥搜索（HDCS）算法來求解其最小完工時(shí)間，通過將CS算法與變量鄰域搜索算法結(jié)合，構(gòu)造了該混合算法，并且對(duì)Lévy飛行方式進(jìn)行了改進(jìn)，對(duì)算法的搜索進(jìn)行了優(yōu)化。唐紅濤等人[16]在考慮到企業(yè)的實(shí)際生產(chǎn)情況下，建立了一個(gè)調(diào)度目標(biāo)為最大完工時(shí)間最小的分布式柔性車間調(diào)度模型，通過對(duì)布谷鳥算法的編碼和初始化策略進(jìn)行調(diào)整以提高初始解的質(zhì)量，同時(shí)對(duì)布谷鳥算法的搜索操作進(jìn)行了改進(jìn)，在加快算法收斂速度的同時(shí)保證解的質(zhì)量。羅函明等人[17]在求解混合流水車間調(diào)度問題時(shí)，將布谷鳥算法進(jìn)行離散化，并改進(jìn)其解碼方式，提高解的質(zhì)量。

目前，有關(guān)DRCFJSP的研究并不算多，但大部分工廠在進(jìn)行生產(chǎn)時(shí)，工人的配合卻是必不可少的，因此本文在FJSP的基礎(chǔ)上，考慮到工廠的實(shí)際加工情況，增加了工人約束，通過工人操控機(jī)器對(duì)工件進(jìn)行加工。針對(duì)以上問題，本文在編碼時(shí)增加了工人信息，同時(shí)將種群分為三個(gè)子群，對(duì)子群的步長因子進(jìn)行自適應(yīng)調(diào)整，提高種群多樣性。最后對(duì)算法解碼進(jìn)行了改進(jìn)，將工人信息考慮進(jìn)了算法解碼中，并且充分利用解碼時(shí)產(chǎn)生的空閑時(shí)間，以達(dá)到縮短算法最終完工時(shí)間的目的。通過標(biāo)準(zhǔn)測(cè)試集對(duì)改進(jìn)后的算法進(jìn)行了仿真實(shí)驗(yàn)，并與其他算法進(jìn)行了對(duì)比，證明了改進(jìn)CS算法求解DRCFJSP的有效性與穩(wěn)定性。

1雙資源約束柔性車間調(diào)度模型

雙資源約束的柔性車間調(diào)度問題描述如下：w個(gè)工人W={W1，W2，…，Ww}操作m臺(tái)機(jī)器M={M1，M2，…，Mm}對(duì)n個(gè)工件J={J1，J2，…，Jn}進(jìn)行加工，工件Ji（i=1，2，…，n）包含確定的ni道工序{Oi，1，Oi，2，…，Oi，ni}。每個(gè)操作的加工時(shí)間取決于機(jī)器和工人分配，不同的機(jī)器和工人可能會(huì)導(dǎo)致加工時(shí)間不同。調(diào)度的目標(biāo)是確定所有工件的加工順序以及每道工序選用的工人和機(jī)器，使得最大完工時(shí)間（makespan）最小。DRCFJSP中的符號(hào)定義如表1所示。

PW[v]工序v由同一工人加工的前一道工序，若v為該工人加工的第一道工序，則PW[v]=-1

SW[v]工序v由同一工人加工的后一道工序，若v為該工人加工的最后一道工序，則SW[v]=-1

決策變量如下：

xijkw=1如果工序Oij在機(jī)器k上由工人w加工

0否則

yghijk=1如果工序Og，h 與工序Oi，j 都在機(jī)器k上加工，且工序Og，h 先于工序Oi，j

0否則

zghijw=1如果工序Og，h 與工序Oi，j 都由工人w加工，且工序Og，h先于工序Oi，j

0否則

以最小化最大完工時(shí)間為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，其目標(biāo)函數(shù)為

min Cmax=max（CEi，j）

其約束條件如下：

i∈J，j∈Ji，∑k∈M∑w∈Wxijkw=1（1）

i∈J，j∈Ji，CEi，j=SEi，j+∑k∈M∑w∈W（Tijkwxijkw）（2）

i∈J，j∈Ji，CLi，j=SLi，j+∑k∈M∑w∈W（Tijkwxijkw）（3）

i∈J，j∈J{1，2，…，ni-1}，CEi，j≤SEi，j+1（4）

g，i∈J，h∈Jg，j∈Ji，k∈M，CEg，h≤SEi，j+L（1-yghijk）（5）

g，i∈J，h∈Jg，j∈Ji，w∈W，CEg，h≤SEi，j+L（1-zghijw）（6）

k∈M，Sk≥0（7）

k∈M，i∈J，j∈Ji，w∈W，Sk≤SEi，j+L（1-xijkw）（8）

k∈M，i∈J，j∈Ji，w∈W，CEi，j·xijkw≤Fk（9）

若PW[Oi，j]=-1，令CEPW[Oi，j]=0，則有i∈J，j∈Ji：

SEi，j=max（CEPM[Oi，j]，CEPJ[Oi，j]，∑k∈M∑w∈WSk·xijkw）（10）

若SW[Oi，j]=-1，令SLSW[Oi，j]=Cmax，則有i∈J，j∈Ji：

CLi，j=max（SLSM[Oi，j]，SLSJ[Oi，j]，SLSW[Oi，j]）（11）

式（1）表示每個(gè)工序只能在一臺(tái)機(jī)器上由一個(gè)工人進(jìn)行加工；式（2）表示每個(gè)工序的最早完工時(shí)間等于該工序最早開始加工時(shí)間與所需加工時(shí)間之和；式（3）表示最晚完工時(shí)間等于最晚開始加工時(shí)間與所需加工時(shí)間之和；式（4）表示同一工件上工序加工的先后順序約束；式（5）表示每個(gè)機(jī)器任一時(shí)刻最多只能加工一道工序；式（6）表示每個(gè)工人任一時(shí)刻最多只能加工一道工序；式（7）表示所有機(jī)器不能提前進(jìn)行工作，從0時(shí)刻開始可用；式（8）工件在機(jī)器上進(jìn)行加工時(shí)機(jī)器必須是空閑的；式（9）機(jī)器必須在加工結(jié)束后才能停止，中途不能停止；式（10）計(jì)算工序最早開始加工時(shí)間；式（11）計(jì)算工序最晚完工時(shí)間。

表2為一個(gè)DRCFJSP實(shí)例，該實(shí)例由三個(gè)工件三個(gè)機(jī)器和兩個(gè)工人構(gòu)成。表中給出了每道工序在某個(gè)機(jī)器上由某個(gè)工人加工所需的時(shí)間，其中“-”表示對(duì)應(yīng)工人無法操作對(duì)應(yīng)機(jī)器對(duì)該工序進(jìn)行加工。例如，O1，1無法由工人W1在機(jī)器M1上進(jìn)行加工，但O1，1可以由工人W1在M2上進(jìn)行加工且所需加工時(shí)間為1。

2改進(jìn)布谷鳥算法求解DRCFJSP

2.1布谷鳥算法

布谷鳥算法作為一種新型啟發(fā)式搜索算法，主要基于兩個(gè)更新策略：a）通過Lévy飛行機(jī)制尋找寄生巢穴；b）通過偏好隨機(jī)游走策略代替被發(fā)現(xiàn)的鳥巢。在布谷鳥算法中每一個(gè)鳥巢代表一個(gè)可行解。在理想狀態(tài)下，布谷鳥的位置更新公式如下：

Xt+1i=Xti+α⊕Lévy（β）（12）

其中：Xti表示第i（i=1，2，…，n）個(gè)鳥巢在第t代的位置；⊕為點(diǎn)對(duì)點(diǎn)乘法；α通常取值為α=1。Lévy（β）為隨機(jī)搜索路徑，服從Lévy分布：

Lévy（β）～μ=t-β1lt;β≤3（13）

為方便運(yùn)算，文獻(xiàn)[12]使用式（13）產(chǎn)生Lévy隨機(jī)數(shù)：

Lévy（β）=×μ|υ|1β（14）

其中：μ和υ均服從標(biāo)準(zhǔn)正態(tài)分布，β=1.5。

=（Γ（1+β）×sin（π×β2）Γ（（1+β2）×β×2β-12））1β（15）

綜合上述公式，布谷鳥的位置更新公式為

Xt+1i=Xti+α0×φ×μ|υ|1β（Xti-Xbest）（16）

按發(fā)現(xiàn)概率Pa丟棄部分解后，采用偏好隨機(jī)游走重新生成相同數(shù)量的新解，公式為

Xt+1i=Xti+γ（Xtg-Xtk）（17）

其中：γ是服從均勻分布的縮放因子；Xtg、Xtk表示第t代的兩個(gè)隨機(jī)數(shù)。

2.2算法編碼

由于標(biāo)準(zhǔn)布谷鳥算法適用于解決連續(xù)性優(yōu)化問題，無法直接將其用于解決車間調(diào)度問題，所以本文引入最小位置規(guī)則（smallest position value，SPV）來建立個(gè)體與實(shí)際調(diào)度的映射關(guān)系。如圖1所示，SPV規(guī)則是將原向量進(jìn)行升序排列得到新向量，新向量中各分量所對(duì)應(yīng)的原向量中的位置即為整數(shù)編碼序列。本文在算法編碼時(shí)先隨機(jī)生成工序加工序列，然后根據(jù)所生成的加工序列，對(duì)機(jī)器和工人進(jìn)行分配。整個(gè)算法包含了三層序列：第一層是工序加工序列（OS），第二層是機(jī)器分配序列（MA），第三層是工人分配序列（WA）。該編碼由表1的問題實(shí)例得出，表示三個(gè)工件由兩個(gè)工人在三臺(tái)機(jī)器上加工的調(diào)度，其中工件1包含兩道工序、工件2包含兩道工序，工件3包含三道工序，工件的加工順序?yàn)椋篛2，1→O2，2→O3，1→O1，1→O1，2→O3，2→O3，3。結(jié)合整個(gè)序列可知，工序O2，1由工人2在機(jī)器3上加工，工序O2，2由工人2在機(jī)器3上加工，工序O3，1由工人1在機(jī)器2上加工，其余工序依此類推。

2.3改進(jìn)解碼算法

相比于單資源約束的FJSP，DRCFJSP在加工時(shí)不僅受前一道工序的結(jié)束時(shí)間和機(jī)器最早可開始加工時(shí)間的約束，還受到工人最早可開始加工時(shí)間的約束。因此本文通過對(duì)插入式解碼方案進(jìn)行改進(jìn)，得到一種可以同時(shí)對(duì)機(jī)器和工人進(jìn)行主動(dòng)解碼的改進(jìn)解碼方案，改進(jìn)解碼方案的核心是有效利用機(jī)器和工人加工時(shí)產(chǎn)生的空閑時(shí)間，將機(jī)器和工人提前安排到合適的空閑時(shí)間段內(nèi)進(jìn)行加工，以達(dá)到縮短整個(gè)加工時(shí)間的目的。記工件i的第j道工序Oij的開始加工時(shí)間為STij，結(jié)束加工時(shí)間為ETij，該工序的緊前完工時(shí)間為ETi，j-1，工人s操作機(jī)器k對(duì)工序Oij加工所需時(shí)間為Tijks。在解碼時(shí)首先需要判斷所選機(jī)器和工人的加工情況，再根據(jù)加工情況判斷是否有空閑時(shí)間以及空閑時(shí)間是否滿足插入條件。當(dāng)機(jī)器和工人均有空閑時(shí)間時(shí)，有以下三種可能出現(xiàn)的情況：

情況1如圖2所示，機(jī)器和工人的空閑時(shí)間不重合，因此無法進(jìn)行插入操作。

情況2如圖3所示，機(jī)器和工人有重合的空閑時(shí)間段Ta，但Ta小于工序所需加工時(shí)間Tijks，即Talt;Tijks，因此無法進(jìn)行插入操作。

情況3如圖4所示，機(jī)器和工人有重合的空閑時(shí)間段Ta，且Ta大于等于工序所需加工時(shí)間Tijks，即Ta≥Tijks，因此可以進(jìn)行插入操作。

綜合解碼時(shí)可能出現(xiàn)的所有情況，本文給出了解碼算法的偽代碼，如算法1所示。

算法1改進(jìn)解碼方法

輸入： 總工序數(shù)TP；機(jī)器和工人可加工信息。

輸出： 工序開始時(shí)間STij和完工時(shí)間ETij；機(jī)器加工時(shí)間[SMk，EMk]；工人加工時(shí)間[SWs，EWs]。

for tp=1 to TP

Oij=OS（tp）；flag=0；//flag用于判斷是否插入空閑時(shí)間

獲取Oij可選的加工機(jī)器和工人s，加工所需時(shí)間Tijks；

機(jī)器k和工人s的加工時(shí)間[SMk，EMk]、[SWs，EWs]和對(duì)應(yīng)空閑時(shí)間[ASMk，AEMk]、[ASWs，AEWs]；

if j==1//工件第一道工序

if [SMk，EMk]==amp;amp;[SWs，EWs]== /*工人和機(jī)器都還未進(jìn)行加工*/

STij=0；ETij=STij+Tijksk；flag=1；

end if

else

if [ASMk，AEMk]～=amp;amp;[ASWs，AEWs]== /*機(jī)器有空閑時(shí)間，工人無空閑時(shí)間*/

if ASMkgt;=max{EWs}amp;amp;ASMkgt;=ETi，j-1amp;amp;ASMk+Tijkslt;=AEMk

STij=ASMk；ETij=STij+Tijks；flag=1；

end if

else if [ASMk，AEMk]==amp;amp;[ASWs，AEWs]～= //機(jī)器無空閑時(shí)間，工人有空閑時(shí)間

if ASWsgt;=max{EMk}amp;amp;ASWsgt;=ETi，j-1amp;amp;ASWs+Tijkslt;=AEWs

STij=ASWs；ETij=STij+Tijks；flag=1；

end if

else if [ASMk，AEMk]～=amp;amp;[ASWs，AEWs]～=//機(jī)器和工人均有空閑時(shí)間

if max（ASMk，ASWs）gt;=ETi，j-1amp;amp;max（ASMk，ASWs）+Tijkslt;=min（AEMk，AEWs）

STij=max{ASMk，ASWs}；ETij=STij+Tijks；flag=1；

end if

else //機(jī)器和工人均無空閑時(shí)間

STij=max{ETi，j-1，EMk，EWs}；ETij=STij+Tijks；flag=1；

end if

end if

if flag==0

STij=max{ETi，j-1，EMk，EWs}；ETij=STij+Tijks；flag=1；

end if

更新工序Oij的最早完工時(shí)間ETij以及機(jī)器k和工人s的加工時(shí)間和空閑時(shí)間；

end for

2.4算法更新

2.4.1改進(jìn)Lévy飛行

在標(biāo)準(zhǔn)布谷鳥搜索算法中，Lévy飛行的步長越長搜索精度越低，適用于全局探索，步長越短搜索精度越高，局部搜索能力越強(qiáng)。由于標(biāo)準(zhǔn)Lévy飛行的步長因子是一個(gè)固定值，缺乏自適應(yīng)性，可能導(dǎo)致算法在搜索時(shí)搜索速度慢且容易陷入局部最優(yōu)。針對(duì)這種情況，本文采用兩種方法對(duì)步長因子進(jìn)行改進(jìn)，通過將布谷鳥種群隨機(jī)劃分為三個(gè)子群，三個(gè)子群分別采用固定步長因子的Lévy飛行方式與兩種改進(jìn)自適應(yīng)步長因子的Lévy飛行方式進(jìn)行獨(dú)立的更新操作。根據(jù)不同搜索階段種群的搜索情況，自動(dòng)調(diào)整步長因子的大小，以達(dá)到平衡全局尋優(yōu)速率和搜索精度的關(guān)系的目的。

其中，第一種改進(jìn)方法如式（18）所示，根據(jù)當(dāng)前鳥巢與當(dāng)前最優(yōu)鳥巢的位置關(guān)系，對(duì)步長因子α進(jìn)行自適應(yīng)調(diào)整，使得Lévy飛行在當(dāng)前最優(yōu)鳥巢附近進(jìn)行較為細(xì)致的搜索，有利于鎖定全局最優(yōu)解。

α=α0×（Xti-Xbest）（18）

其中：α0通常取值為0.01；Xti表示第t代的第i個(gè)鳥巢位置；Xbest表示當(dāng)前最優(yōu)鳥巢位置。

第二種改進(jìn)方法如式（19）所示，采用了文獻(xiàn)[18]的改進(jìn)方式，主要通過算法的迭代次數(shù)對(duì)步長因子α進(jìn)行控制。在算法初期，步長因子α的值較大，搜索范圍也大，降低了算法陷入局部最優(yōu)的可能，到了算法后期，步長自適應(yīng)減小，搜索精度得到了提高，更利于找到最優(yōu)解：

α=（αmax+αγ）×cos（titmax）（19）

其中：ti表示當(dāng)前迭代次數(shù)；tmax表示迭代總次數(shù)；取αmax=0.9；αγ為[-0.05，0.05]上隨機(jī)步長因子。

2.4.2信息交流

由于三個(gè)子群是分別獨(dú)立地進(jìn)行尋優(yōu)操作，為了提高尋優(yōu)效率，每進(jìn)化k代后，各個(gè)種群之間通過一定的策略進(jìn)行種群間個(gè)體的信息交流，以交換種群信息，保持種群的多樣性。信息交流的原則是：將子群中的較差個(gè)體與最優(yōu)個(gè)體進(jìn)行信息交流，從而引導(dǎo)較差個(gè)體向全局最優(yōu)個(gè)體位置進(jìn)行搜索。本文引入差分進(jìn)化算法的DE/best/1變異策略對(duì)子群進(jìn)行差分，其計(jì)算公式為

Vi，g=Xbest，g+F（Xr1，g-Xr2，g）（20）

其中：Xbest，g表示當(dāng)前全局最優(yōu)個(gè)體；Xr1，g、Xr2，g表示子群中較差的兩個(gè)個(gè)體。

改進(jìn)后的布谷鳥算法如算法2所示。

算法2改進(jìn)布谷鳥算法更新

輸入：迭代次數(shù)iter；子群inest。

輸出：當(dāng)前最優(yōu)鳥巢信息Xbest，g。

for i=1 to iter

for inest=1 to 3

每個(gè)子群采用不同步長因子的Lévy飛行進(jìn)行更新，步長因子更新式（12）（18）（19）；

對(duì)鳥巢進(jìn)行評(píng)價(jià)并按照概率Pa舍棄較差的鳥巢，采用式（17）

生成相同數(shù)量的新鳥巢；

end for

對(duì)這一代鳥巢進(jìn)行評(píng)價(jià)，更新當(dāng)前最優(yōu)鳥巢信息Xbest，g；

if i/k==0

按照式（20）對(duì)子群進(jìn)行差分；

end if

end for

2.5算法流程

a）初始化參數(shù)，布谷鳥種群數(shù)目n，最大迭代次數(shù)iter，發(fā)現(xiàn)概率Pa。

b）初始化種群，根據(jù)映射規(guī)則，將鳥巢信息轉(zhuǎn)換為包含調(diào)度信息的可行序列，采用改進(jìn)解碼算法對(duì)其進(jìn)行解碼得到完工時(shí)間，保留當(dāng)前最優(yōu)鳥巢，并隨機(jī)將種群分為三個(gè)子群。

c）分別采用標(biāo)準(zhǔn)Lévy飛行公式和兩種改進(jìn)Lévy飛行公式更新子群鳥巢位置，解碼得到完工時(shí)間，更新當(dāng)前最優(yōu)鳥巢。按照式（17）進(jìn)行偏好隨機(jī)游走，淘汰部分差的解并生成相同數(shù)量的新解。

d）每迭代k次，引入差分算子來實(shí)現(xiàn)三個(gè)子群之間的信息交流，用改進(jìn)解碼算法對(duì)其進(jìn)行解碼得到完工時(shí)間，更新當(dāng)前最優(yōu)鳥巢。

e）當(dāng)達(dá)到最大迭代次數(shù)則輸出全局最優(yōu)解，否則轉(zhuǎn)到步驟c）繼續(xù)進(jìn)行迭代。

3實(shí)例仿真與分析

3.1實(shí)驗(yàn)環(huán)境和測(cè)試實(shí)例

本文采用MATLAB R2018a編程，運(yùn)行環(huán)境為Intel Xeon CPU E5- @3.30 GHz，RAM 8 GB。考慮到目前針對(duì)DCRFJSP的研究成果較少，且沒有標(biāo)準(zhǔn)算例可供參考比較，為了更好地通過比較實(shí)驗(yàn)結(jié)果來驗(yàn)證算法的性能，本文選擇Brandimarte[19]標(biāo)準(zhǔn)測(cè)試集中的MK1～MK10算例對(duì)算法進(jìn)行測(cè)試，同時(shí)根據(jù)文獻(xiàn)[11]的工人分配方式進(jìn)行仿真實(shí)驗(yàn)，具體工人機(jī)器分配情況如表3所示。

3.2結(jié)果和分析

由于算法的參數(shù)對(duì)算法的性能以及運(yùn)行時(shí)間有很大影響，為了保證算法以較優(yōu)的狀態(tài)運(yùn)行，本文引入文獻(xiàn)[20]所采用的正交實(shí)驗(yàn)法對(duì)參數(shù)進(jìn)行設(shè)置。圖5為不同參數(shù)情況下本文算法求解MK1算例，運(yùn)行10次的平均值變化趨勢(shì)。圖5（a）為最大迭代次數(shù)iter的影響曲線，可以看出，當(dāng)?shù)螖?shù)設(shè)置較小時(shí)，可能導(dǎo)致算法在尚未收斂的情況下被迫停止，從而影響算法的尋優(yōu)結(jié)果，隨著迭代次數(shù)的增加，獲得解的質(zhì)量也逐漸提高，但是當(dāng)?shù)螖?shù)到了某一值后，繼續(xù)增加迭代次數(shù)并不能明顯提高取得最優(yōu)解的次數(shù)，還會(huì)增加算法的復(fù)雜度，因此在保證運(yùn)行效率的基礎(chǔ)上，設(shè)置最大迭代次數(shù)iter=200。從圖5（b）可以看出，當(dāng)種群規(guī)模在50左右，能獲得比較優(yōu)秀的解，因此設(shè)置種群數(shù)量n=50。圖5（c）為發(fā)現(xiàn)概率pa的影響曲線，當(dāng)發(fā)現(xiàn)概率在0.25左右時(shí)，得到的解最優(yōu)，隨著發(fā)現(xiàn)概率逐漸增大，得到的解的質(zhì)量也逐漸降低，因此最終設(shè)置發(fā)現(xiàn)概率pa=0.25。

為測(cè)試本文算法的有效性，將其與不同的算法進(jìn)行了比較，每個(gè)算例連續(xù)充分實(shí)驗(yàn)20次，記錄多次實(shí)驗(yàn)的結(jié)果并進(jìn)行分析，仿真實(shí)驗(yàn)結(jié)果如表4所示。其中，VNS、KGFOA和MBSA分別為文獻(xiàn)[10，11，21]求解DRCFJSP所得的最優(yōu)值；ICS為普通解碼方式的改進(jìn)布谷鳥算法求解所得的最優(yōu)值；CSND為具有改進(jìn)解碼方式的標(biāo)準(zhǔn)布谷鳥算法求解所得的最優(yōu)值；ICSND為本文采用的具有改進(jìn)解碼方式的改進(jìn)布谷鳥算法求解所得的最優(yōu)值。

從表4可以看出，在僅對(duì)布谷鳥算法進(jìn)行改進(jìn)的情況下，當(dāng)問題規(guī)模較小時(shí)，容易得到比較優(yōu)秀的值；但是當(dāng)問題規(guī)模逐漸增大，機(jī)器和工人空閑時(shí)間也隨之增多，普通的解碼方式無法有效利用這些空閑時(shí)間，因此僅靠改進(jìn)布谷鳥算法已經(jīng)無法得到更好的解。對(duì)于CSND，由于布谷鳥算法本身具有一定的優(yōu)越性，能較好地兼顧全局和局部搜索，再加上改進(jìn)解碼方式有效地縮短了完工時(shí)間，求解的效率也得到了一定的提升。對(duì)于本文所使用的ICSND，不僅對(duì)布谷鳥算法進(jìn)行了改進(jìn)，增強(qiáng)了算法的搜索能力，還對(duì)解碼方式進(jìn)行了調(diào)整，有效利用了工人和機(jī)器的空閑時(shí)間，極大地縮短了完工時(shí)間，將ICSND與其他算法進(jìn)行對(duì)比可以發(fā)現(xiàn)，在大部分算例的求解上，ICSND都能得到更優(yōu)的解。

圖6、7為采用本文ICSND算法求解算例MK1和MK2所得的甘特圖，其中，橫坐標(biāo)為加工時(shí)長，縱坐標(biāo)為機(jī)器，方框里的第一個(gè)數(shù)字表示工件，第二個(gè)數(shù)字表示對(duì)應(yīng)的工人。

為了更好地衡量本文所使用的算法性能，引入文獻(xiàn)[10]所使用的相對(duì)百分比偏差最優(yōu)值MRPD和相對(duì)百分比偏差平均值A(chǔ)RPD這兩個(gè)指標(biāo)來評(píng)估算法能力，計(jì)算公式為

MRPD=min（Cmax-ClowmaxClowmax×100）（21）

ARPD=1s∑si=1（Cmax-ClowmaxClowmax×100）（22）

其中：Cmax為各個(gè)算法求出的最優(yōu)解；Clowmax為本文求出的最優(yōu)解。

從表5可以看出，采用了改進(jìn)解碼方式的算法MRPD和ARPD都優(yōu)于普通解碼方式的算法，而ICSND無論從解的質(zhì)量還是最優(yōu)解的獲取都優(yōu)于CSND，改進(jìn)后的布谷鳥算法性能整體優(yōu)于標(biāo)準(zhǔn)布谷鳥算法，具有更強(qiáng)的搜索能力。表6通過將ICSND與VNS、KGFOA和MBSA的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比可以看出，ICSND的最小百分比偏差都為0，并且平均百分比偏差也更小，得到的解更加穩(wěn)定，質(zhì)量也比較好。而其他三種算法，在大部分情況下的求解質(zhì)量都不如ICSND算法，平均百分比偏差的值也更大。因此相對(duì)于其他三種算法，ICSND算法具有更好的求解能力，在求解DRCFJSP問題時(shí)的穩(wěn)定性和解的質(zhì)量方面都更優(yōu)。

4結(jié)束語

本文在布谷鳥算法核心框架不變的基礎(chǔ)下對(duì)其進(jìn)行改進(jìn)，通過將布谷鳥種群劃分為三個(gè)子群，并分別采用不同Lévy飛行方式進(jìn)行尋優(yōu)，同時(shí)引入差分算子進(jìn)行子群間的信息交流，大大增加了算法的搜索能力。在解碼時(shí)設(shè)計(jì)了一種改進(jìn)解碼方式，在避免機(jī)器和工人的加工時(shí)間沖突的同時(shí)，主動(dòng)尋找可進(jìn)行插入的空閑時(shí)間，大大地縮短了整個(gè)加工的完工時(shí)間。最后通過基準(zhǔn)測(cè)試算例進(jìn)行實(shí)驗(yàn)驗(yàn)證和比較，證明了改進(jìn)布谷鳥算法和改進(jìn)解碼方式的有效性和穩(wěn)定性。在后續(xù)研究中，考慮將生產(chǎn)過程中常見的動(dòng)態(tài)因素考慮進(jìn)去，比如機(jī)器故障、機(jī)器維護(hù)、緊急插單以及緊急撤單等。

參考文獻(xiàn)：

［1］陳可嘉，段瑞明，劉碧玉，等.模糊置換流水車間調(diào)度的多目標(biāo)模型[J].運(yùn)籌與管理，2021，30（8）：28-36.（Chen Kejia，Duan Ruiming，Liu Biyu，et al.A multi-objective model for fuzzy replacement Flow-Shop scheduling[J].Operations Research and Ma-nagement，2021，30（8）：28-36.）

[2]Lin J.Backtracking search based hyper-heuristic for the flexible Job-Shop scheduling problem with fuzzy processing time[J].Engineering Applications of Artificial Intelligence，2019，77：186-196.

[3]軒華，王晶，李冰，等.阻塞混合流水車間調(diào)度優(yōu)化研究[J].控制工程，2020，27（8）：1346-1350.（Xuan Hua，Wang Jing，Li Bing，et al.Research on optimal scheduling of blocked mixed Flow-Shop[J].Control Engineering，2020，27（8）：1346-1350.）

[4]Shao Zhongshi，Shao Weishi，Pi Dechang.Effective constructive heuristic and iterated greedy algorithm for distributed mixed blocking permutation Flow-Shop scheduling problem[J].Knowledge-Based Systems，2021，221（5）：106959.

[5]軒華，王晶，張慧賢，等.混合遺傳算法求解含機(jī)器可利用約束的HFSP[J].計(jì)算機(jī)應(yīng)用與軟件，2021，38（6）：176-181.（Xuan Hua，Wang Jing，Zhang Huixian，et al.Hybrid genetic algorithm for HFSP with machine availability constraints[J].Computer Applications and Software，2021，38（6）：176-181.）

[6]張洪亮，丁仁曼，徐公杰.考慮區(qū)間工時(shí)的多目標(biāo)柔性作業(yè)車間節(jié)能調(diào)度[J/OL].系統(tǒng)仿真學(xué)報(bào).（2021-08-17）[2021-09-10].https：//doi.org/10.16182/j.issn1004731x.joss.21-0395.（Zhang Hongliang，Ding Renman，Xu Gongjie.Multi-objective flexible Job-Shop energy saving scheduling considering interval working hours[J/OL].Journal of System Simulation.（2021-08-17）[2021-09-10].https：//doi.org/10.16182/j.issn1004731x.joss.21-0395.）

[7]Wang Hui，Sheng Buyun，Lu Qibing，et al.A novel multi-objective optimization algorithm for the integrated scheduling of flexible Job-Shops considering preventive maintenance activities and transportation processes[J].Soft Computing，2021，25（4）：1-27.

[8]Li Jingyao，Huang Yuan.A hybrid genetic algorithm for dual-resource constrained Job-Shop scheduling problem[C]//Proc of International Conference on Intelligent Computing.Berlin：Springer，2016：463-475.

[9]Zhang Jing，Wang Wanliang，Xu Xinli.A hybrid discrete particle swarm optimization for dual-resource constrained Job-Shop scheduling with resource flexibility[J].Journal of Intelligent Manufacturing，2017，28（8）：1961-1972.

[10]Lei Deming，Guo Xiuping.Variable neighbourhood search for dual-resource constrained flexible Job-Shop scheduling[J].International Journal of Production Research，2014，52（9）：2519-2529.

[11]Zheng Xiaolong，Wang Ling.A knowledge-guided fruit fly optimization algorithm for dual resource constrained flexible Job-Shop scheduling problem[J].International Journal of Production Research，2016，54（18）：5554-5566.

[12]Yang Xinshe，Deb S.Cuckoo search via Lévy flight[C]//Proc of World Congress on Nature amp; Biologically Inspired Computing.2009：210-214.

[13]Ouaarab A，Ahiod B，Yang Xinshe.Discrete cuckoo search applied to Job-Shop scheduling problem[M]//Recent Advances in Swarm Intelligence and Evolutionary Computation.Cham：Springer，2015：121-137.

[14]Alaa S，Alobaidi A.Two improved cuckoo search algorithms for solving the flexible Job-Shop scheduling problem[J].International Journal on Perceptive and Cognitive Computing，2016，2（2）：25-31.

[15]Majumdera A，Lahaa D，Suganthan P N.A hybrid cuckoo search algorithm in parallel batch processing machines with unequal job ready times[J].Computers amp; Industrial Engineering，2018，124：65-76.

[16]唐紅濤，劉家毅.改進(jìn)的布谷鳥算法求解考慮運(yùn)輸時(shí)間的分布式柔性流水車間調(diào)度問題[J].運(yùn)籌與管理，2021，30（11）：76-83.（Tang Hongtao，Liu Jiayi.Improved cuckoo algorithm for distributed flexible flow shop scheduling problem considering transportation time[J].Operations Research and Management，2021，30（11）：76-83.）

[17]羅函明，羅天洪，吳曉東，等.求解混合流水車間調(diào)度問題的離散布谷鳥算法[J].計(jì)算機(jī)工程與應(yīng)用，2020，56（22）：264-271.（Luo Hanming，Luo Tianhong，Wu Xiaodong，et al.Discrete cuckoo algorithm for solving hybrid flow shop scheduling problem[J].Computer Engineering and Applications，2020，56（22）：264-271.）

[18]施文章，韓偉，戴睿聞.模擬退火下布谷鳥算法求解車間作業(yè)調(diào)度問題[J].計(jì)算機(jī)工程與應(yīng)用，2017，53（17）：249-253，259.（Shi Wenzhang，Han Wei，Dai Ruiwen.Cuckoo algorithm under simulated annealing to solve Job-Shop scheduling problems[J].Computer Engineering and Applications，2017，53（17）：249-253，259.）

[19]Brandimarte P.Routing and scheduling in a flexible Job-Shop by tabu search[J].Annals of Operations Research，1993，41（3）：157-183.

[20]王文艷，徐震浩，顧幸生.離散水波優(yōu)化算法求解帶批處理的混合流水車間批量流調(diào)度問題[J].華東理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2021，47（5）：598-608.（Wang Wenyan，Xu Zhenhao，Gu Xing-sheng.Discrete water wave optimization algorithm for batch flow scheduling problem in mixed flow workshop with batch processing[J].Journal of East China University of Science and Technology：Natural Science，2021，47（5）：598-608.）

[21]Gnanavelbabu A，Caldeira R H，Vaidyanathan T.A simulation-based modified backtracking search algorithm for multi-objective stochastic flexible Job-Shop scheduling problem with worker flexibility[J].Applied Soft Computing，2021，113：107960.

收稿日期：2022-01-29；修回日期：2022-03-18基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（11871059）；四川省教育廳自然科學(xué)基金資助項(xiàng)目（18ZA0469）；西華師范大學(xué)英才科研基金資助項(xiàng)目（17YC385）；西華師范大學(xué)校級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目（cxcy2021312）

作者簡介：羅浩嘉（1997-），女，四川遂寧人，碩士，主要研究方向?yàn)橹悄芩惴ā?shù)學(xué)建模；潘大志（1974-），男（通信作者），四川三臺(tái)人，教授，碩導(dǎo)，博士，主要研究方向?yàn)橹悄苡?jì)算、算法設(shè)計(jì)等（pdzzj@126.com）．