改進布谷鳥算法求解雙資源約束柔性車間調度問題

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

關鍵詞：柔性車間調度；雙資源約束；布谷鳥算法；改進解碼方法

中圖分類號：TP301.6文獻標志碼：A

文章編號：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引言

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

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

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

1雙資源約束柔性車間調度模型

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

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

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

決策變量如下：

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

0否則

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

0否則

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

0否則

以最小化最大完工時間為優化目標建立數學模型，其目標函數為

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）表示每個工序只能在一臺機器上由一個工人進行加工；式（2）表示每個工序的最早完工時間等于該工序最早開始加工時間與所需加工時間之和；式（3）表示最晚完工時間等于最晚開始加工時間與所需加工時間之和；式（4）表示同一工件上工序加工的先后順序約束；式（5）表示每個機器任一時刻最多只能加工一道工序；式（6）表示每個工人任一時刻最多只能加工一道工序；式（7）表示所有機器不能提前進行工作，從0時刻開始可用；式（8）工件在機器上進行加工時機器必須是空閑的；式（9）機器必須在加工結束后才能停止，中途不能停止；式（10）計算工序最早開始加工時間；式（11）計算工序最晚完工時間。

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

2改進布谷鳥算法求解DRCFJSP

2.1布谷鳥算法

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

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

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

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

為方便運算，文獻[12]使用式（13）產生Lévy隨機數：

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

其中：μ和υ均服從標準正態分布，β=1.5。

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

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

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

按發現概率Pa丟棄部分解后，采用偏好隨機游走重新生成相同數量的新解，公式為

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

其中：γ是服從均勻分布的縮放因子；Xtg、Xtk表示第t代的兩個隨機數。

2.2算法編碼

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

2.3改進解碼算法

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

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

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

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

綜合解碼時可能出現的所有情況，本文給出了解碼算法的偽代碼，如算法1所示。

算法1改進解碼方法

輸入： 總工序數TP；機器和工人可加工信息。

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

for tp=1 to TP

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

獲取Oij可選的加工機器和工人s，加工所需時間Tijks；

機器k和工人s的加工時間[SMk，EMk]、[SWs，EWs]和對應空閑時間[ASMk，AEMk]、[ASWs，AEWs]；

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

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

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

end if

else

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

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]～= //機器無空閑時間，工人有空閑時間

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]～=//機器和工人均有空閑時間

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 //機器和工人均無空閑時間

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的最早完工時間ETij以及機器k和工人s的加工時間和空閑時間；

end for

2.4算法更新

2.4.1改進Lévy飛行

在標準布谷鳥搜索算法中，Lévy飛行的步長越長搜索精度越低，適用于全局探索，步長越短搜索精度越高，局部搜索能力越強。由于標準Lévy飛行的步長因子是一個固定值，缺乏自適應性，可能導致算法在搜索時搜索速度慢且容易陷入局部最優。針對這種情況，本文采用兩種方法對步長因子進行改進，通過將布谷鳥種群隨機劃分為三個子群，三個子群分別采用固定步長因子的Lévy飛行方式與兩種改進自適應步長因子的Lévy飛行方式進行獨立的更新操作。根據不同搜索階段種群的搜索情況，自動調整步長因子的大小，以達到平衡全局尋優速率和搜索精度的關系的目的。

其中，第一種改進方法如式（18）所示，根據當前鳥巢與當前最優鳥巢的位置關系，對步長因子α進行自適應調整，使得Lévy飛行在當前最優鳥巢附近進行較為細致的搜索，有利于鎖定全局最優解。

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

其中：α0通常取值為0.01；Xti表示第t代的第i個鳥巢位置；Xbest表示當前最優鳥巢位置。

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

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

其中：ti表示當前迭代次數；tmax表示迭代總次數；取αmax=0.9；αγ為[-0.05，0.05]上隨機步長因子。

2.4.2信息交流

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

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

其中：Xbest，g表示當前全局最優個體；Xr1，g、Xr2，g表示子群中較差的兩個個體。

改進后的布谷鳥算法如算法2所示。

算法2改進布谷鳥算法更新

輸入：迭代次數iter；子群inest。

輸出：當前最優鳥巢信息Xbest，g。

for i=1 to iter

for inest=1 to 3

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

對鳥巢進行評價并按照概率Pa舍棄較差的鳥巢，采用式（17）

生成相同數量的新鳥巢；

end for

對這一代鳥巢進行評價，更新當前最優鳥巢信息Xbest，g；

if i/k==0

按照式（20）對子群進行差分；

end if

end for

2.5算法流程

a）初始化參數，布谷鳥種群數目n，最大迭代次數iter，發現概率Pa。

b）初始化種群，根據映射規則，將鳥巢信息轉換為包含調度信息的可行序列，采用改進解碼算法對其進行解碼得到完工時間，保留當前最優鳥巢，并隨機將種群分為三個子群。

c）分別采用標準Lévy飛行公式和兩種改進Lévy飛行公式更新子群鳥巢位置，解碼得到完工時間，更新當前最優鳥巢。按照式（17）進行偏好隨機游走，淘汰部分差的解并生成相同數量的新解。

d）每迭代k次，引入差分算子來實現三個子群之間的信息交流，用改進解碼算法對其進行解碼得到完工時間，更新當前最優鳥巢。

e）當達到最大迭代次數則輸出全局最優解，否則轉到步驟c）繼續進行迭代。

3實例仿真與分析

3.1實驗環境和測試實例

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

3.2結果和分析

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

為測試本文算法的有效性，將其與不同的算法進行了比較，每個算例連續充分實驗20次，記錄多次實驗的結果并進行分析，仿真實驗結果如表4所示。其中，VNS、KGFOA和MBSA分別為文獻[10，11，21]求解DRCFJSP所得的最優值；ICS為普通解碼方式的改進布谷鳥算法求解所得的最優值；CSND為具有改進解碼方式的標準布谷鳥算法求解所得的最優值；ICSND為本文采用的具有改進解碼方式的改進布谷鳥算法求解所得的最優值。

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

圖6、7為采用本文ICSND算法求解算例MK1和MK2所得的甘特圖，其中，橫坐標為加工時長，縱坐標為機器，方框里的第一個數字表示工件，第二個數字表示對應的工人。

為了更好地衡量本文所使用的算法性能，引入文獻[10]所使用的相對百分比偏差最優值MRPD和相對百分比偏差平均值ARPD這兩個指標來評估算法能力，計算公式為

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

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

其中：Cmax為各個算法求出的最優解；Clowmax為本文求出的最優解。

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

4結束語

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

參考文獻：

［1］陳可嘉，段瑞明，劉碧玉，等.模糊置換流水車間調度的多目標模型[J].運籌與管理，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]軒華，王晶，李冰，等.阻塞混合流水車間調度優化研究[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]軒華，王晶，張慧賢，等.混合遺傳算法求解含機器可利用約束的HFSP[J].計算機應用與軟件，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]張洪亮，丁仁曼，徐公杰.考慮區間工時的多目標柔性作業車間節能調度[J/OL].系統仿真學報.（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].運籌與管理，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]羅函明，羅天洪，吳曉東，等.求解混合流水車間調度問題的離散布谷鳥算法[J].計算機工程與應用，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]施文章，韓偉，戴睿聞.模擬退火下布谷鳥算法求解車間作業調度問題[J].計算機工程與應用，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]王文艷，徐震浩，顧幸生.離散水波優化算法求解帶批處理的混合流水車間批量流調度問題[J].華東理工大學學報：自然科學版，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基金項目：國家自然科學基金資助項目（11871059）；四川省教育廳自然科學基金資助項目（18ZA0469）；西華師范大學英才科研基金資助項目（17YC385）；西華師范大學校級大學生創新創業訓練計劃項目（cxcy2021312）

作者簡介：羅浩嘉（1997-），女，四川遂寧人，碩士，主要研究方向為智能算法、數學建模；潘大志（1974-），男（通信作者），四川三臺人，教授，碩導，博士，主要研究方向為智能計算、算法設計等（pdzzj@126.com）．