求解置換流水車間調度問題的混合鳥群算法

閆紅超，湯偉*，姚斌

（1.陜西科技大學電氣與控制工程學院，西安 710021；2.陜西科技大學電子信息與人工智能學院，西安 710021）

0 引言

生產調度是實現先進制造的基礎和關鍵，高質量的調度方案能夠降低生產成本、提高資源利用率和生產效率，從而增強企業的競爭力。置換流水車間調度問題（Permutation Flowshop Scheduling Problem，PFSP）主要研究n個工件在m臺機器上的加工過程，目的是找到一個工件排序使得調度目標最優。基于PFSP 的生產模式在制造業中存在廣泛的應用場景；然而，3 臺機器以上的PFSP 屬于NP-hard 問題［1］，求解困難，因此，研究和開發高效的求解算法具有重要的理論價值和現實意義。

解決PFSP 的有效方法包括最優求解法和近似求解法。最優求解法是基于模型的方法，主要有分支定界、整數規劃、動態規劃以及拉格朗日松弛法等。由于計算復雜度高，最優求解法通常僅適用于求解小規模的PFSP［2］。近似求解法主要包括啟發式算法和元啟發式算法。啟發式算法主要有NEH（Nawaz-Enscore-Ham）算法［3］、Johnson 規則［4］等，這些算法雖然能在短時間內構造出解，但難以保證質量。近年來元啟發式算法在車間調度中得到了廣泛的應用，主要有基于變鄰域搜索的粒子群優化（Particle Swarm Optimization based on Variable Neighborhood Search，PSOVNS）算法［5］、分布估計算法（Estimation of Distribution Algorithm，EDA）［6］、Liu 等［7］提出的混合差分進化（Hybrid Differential Evolution algorithm proposed by Liu et al，L-HDE）算法、雙種群協同學習（Double Population Co-Learning，DPCL）算法［8］、混合共生生物搜索（Hybrid Symbiotic Organisms Search，HSOS）算法［9］等。

鳥群算法（Bird Swarm Algorithm，BSA）是由Meng 等［10］提出的一種基于鳥群行為的群智能優化算法，主要思想來源于對鳥群覓食、警戒和飛行等群體行為的模擬以及對鳥群覓食過程中共享信息的研究。相比差分進化算法、粒子群優化算法等常見的傳統優化算法，該算法獨有的多路徑搜索機制使其更好地平衡了高效性與準確性［11］。BSA 已經在動態能耗管理［11］、微電網優化配置［12］、離散智能車間調度［13］和柔性作業車間調度［14］等方面得到了應用。

目前還查閱不到基于鳥群算法對置換流水車間調度問題（PFSP）的研究。本文針對以最大完工時間最小化為目標的PFSP，提出了一種混合鳥群算法（Hybrid Bird Swarm Algorithm，HBSA）進行求解。首先，結合一種基于NEH 的啟發式算法和混沌映射提出了一種新的種群初始化方法，以改善初始種群的質量和多樣性；其次，采用最大排序值（Largest Ranked Value，LRV）規則［7］將連續的位置值轉換為離散的工件排序，從而使算法能夠處理離散的調度問題；最后，借鑒變鄰域搜索（Variable Neighborhood Search，VNS）和迭代貪婪（Iterated Greedy，IG）算法的思想針對個體最佳工件排序和種群最佳工件排序分別提出了局部搜索方法，以強化算法對解空間的探索能力。針對廣泛使用的Rec標準測試集［15］進行仿真測試，并將結果與多種算法的結果進行比較，以驗證算法的性能。

1 置換流水車間調度問題

置換流水車間調度問題的描述為：已知各個工件在各臺機器上的加工時間，要求找到各工件在機器上的加工順序使得某個調度目標最優。相關的約束條件有：一臺機器在同一時刻只能加工一個工件；一個工件在同一時刻只能被一臺機器加工；每臺機器上的工件加工順序相同；工件一旦在機器上開始加工就不能中斷；不考慮所有工件的準備時間；開始時間為零。

生產調度的最終目的是在滿足約束條件的前提下，合理安排現有資源、提高生產效率，使成本最小化或效益最大化，因此最小化最大完工時間是主要的調度目標。

假 設J={J1，J2，…，Jn} 為n個工件的集合；M={M1，M2，…，Mm} 為m臺機器的集合 ；π=[π(1)，π(2)，…，π(n)]為所有工件的一個排序，表示加工順序為從π(1)到π(n)；P(i，j)為工件π(i)在機器Mj上的加工時長；C(i，j)為工件π(i)在機器Mj上的完工時間。各個工件在各臺機器上的完工時間可按照如下方法進行計算：

工件排序π對應的最大完工時間Cmax為最后一個工件在最后一臺機器上的完工時間，即

求解以最大完工時間最小化為調度目標的PFSP，目的是找到一個工件排序π*，使得：

式中Π為所有工件排序的集合。

PFSP 是一種典型的組合優化問題，且有研究表明3 臺機器以上的PFSP 屬于NP-hard 問題，具有指數爆炸、工序相關等復雜性，求解非常困難。針對該問題，本文提出一種混合鳥群算法（HBSA），用于更加有效地最小化最大完工時間。

2 混合鳥群算法

2.1 基本鳥群算法（BSA）

如果rand(0，1) ＜P，則鳥兒進行覓食；否則進行警戒。rand(0，1)為(0，1)區間均勻分布的隨機數，P為(0，1)區間的一個固定值。

覓食行為的位置更新策略為：

式中：C為認知加速系數；S為社會加速系數；pi表示第i只鳥的歷史最優位置；g代表整個種群的歷史最優位置；t=1 時，每只鳥的歷史最優位置為其初始位置，種群的歷史最優位置為初始種群的最優位置。

警戒行為的位置更新策略為：

假設每隔FQ間隔，鳥群會飛到另一個地方，FQ是一個正整數。

生產者的位置更新策略為：

式中：randn(0，1)表示均值為0、標準差為1 服從高斯分布的隨機數。

乞食者的位置更新策略為：

式中：FL∈[0，2]表示乞食者跟隨生產者去尋找食物。

2.2 求解PFSP的混合鳥群算法

基本鳥群算法僅適用于求解連續性問題，對于離散的PFSP 不能直接使用；與其他群智能優化算法相似，基本鳥群算法在處理復雜問題時，存在易陷入局部最優、易過早收斂、收斂精度差等缺點。

為了彌補上述不足，采用LRV 規則將連續的位置值轉換為離散的工件排序，使得算法可用于求解PFSP；結合一種基于NEH 的啟發式算法和混沌映射來初始化種群，以改善初始種群的質量和多樣性、提升算法迭代的效率；借鑒變鄰域搜索和迭代貪婪算法的思想對個體最佳工件排序和種群最佳工件排序進行局部搜索，以強化算法對解空間的探索能力，從而提出了一種混合鳥群算法（HBSA）。HBSA 的流程如圖1 所示，其中，種群（個體）最佳工件排序是指種群（個體）歷史最優解對應的工件排序。

圖1 HBSA流程Fig.1 Flow chart of HBSA

2.2.1 編碼方式與LRV轉換

采用LRV 規則將表示位置的一組連續值映射成工件排序，使鳥群算法能用于解決離散的PFSP。具體方法是每次從代表位置的一組連續值中選擇最大值所屬的維度作為下個要加工的工件，直至遍歷所有的位置值。空間維度D取值為工件的數量n。如圖2 所示，根據LRV 將一個6 維空間中個 體i的位置xi=[1.25，-0.79，4.01，-0.52，-1.30，1.15］，轉換為一個工件排序πi=[2，5，1，4，6，3]。

圖2 LRV規則表示方法Fig.2 Representation of LRV rule

將工件排序πi對應的最大完工時間Cmax(πi)作為第i只鳥的適應度值f(i)，即

顯然，最大完工時間最小的個體為種群最優個體，種群最優個體對應的最大完工時間為種群最優解。

2.2.2 種群初始化

好的初始種群有助于提升算法迭代的效率、提高算法的性能。啟發式算法能夠在較短時間內獲得質量較高的解，保證初始種群中有質量較高的個體；混沌是非線性系統普遍存在的現象，具有有界性、隨機性、遍歷性等特點［16］，采用混沌映射初始化種群，可使個體離散地分布在解空間內，從而有效地提高種群的多樣性，因此，結合啟發式算法和混沌映射進行種群初始化以提高初始種群的質量和多樣性。

1）NEHLJP1 啟發式算法。

NEHLJP1 是Liu 等［17］提出的一種基于NEH 的改進算法，該算法較NEH 具有更強的尋優能力，且計算復雜度和NEH相同。NEHLJP1 算法的步驟如下：

步驟1 計算工件i(i=1，2，…，n)在所有機器上加工時長的平均值AVGi、標準偏差STDi和偏度SKEi，并根據AVGi+DEVi+abs(SKEi)的結果按照非增的順序排序，得到優先序列γ，其中abs()表示取絕對值。

步驟2 令工件排序π=[γ(1)]，j=2。

步驟3 將工件γ(j)插入到π中使最大完工時間最小的位置。如果存在多個位置，則根據Liu 等［17］提出的擇優（Tie Breaking，TBLJP1）機制決定最終的插入位置。

步驟4 令j=j+1，若j≤n，則繼續執行步驟3；否則，π即為最終的工件排序，算法結束。

2）Logistic 映射。

Logistic 映射是一種典型的混沌映射系統，對應的系統方程［18］為：

式中：Xk為混沌變量，μ是控制變量。通常取μ=4，此時系統處于完全混沌狀態，X遍歷整個［0，1］區間。

3）種群初始化。

按照下述方法產生規模為N的初始種群：首先使用NEHLJP1 產生的解初始化種群中約10%的個體，然后用Logistic 映射產生其余的個體。具體方法為：

步驟1 基于NEHLJP1 產生一個工件排序π。令InitNum=

步驟2 使用π生成InitNum個個體：

式 中 ：i∈{1，2，…，InitNum}，j∈{1，2，…，n}，xmax=5，xmin=-5。

步驟3 采用Logistic 映射生成剩余的個體：

式中：i∈{}InitNum+1，InitNum+2，…，N。特別地，xInitNum為隨機生成的n維混沌變量。

2.2.3 局部搜索與改進技術

變鄰域搜索（VNS）和迭代貪婪（IG）算法是簡單、有效的局部搜索技術。

VNS 通過多種鄰域操作強化算法對解空間的探索能力［5，7］，其中，插入和交換是最常用的操作。對于工件排序π中隨機的兩個位置j，k∈{1，2，…，n}∧j≠k，插入是將位置j上的工件取出并插入到位置k從而得到新的工件排序π'，如圖3 所示；交換則是將這兩個位置上的工件互換從而得到新的工件排序π'，如圖4 所示。

圖3 插入操作實例Fig.3 Example of insert operation

圖4 交換操作實例Fig.4 Example of swap operation

IG 基于插入鄰域通過不斷地解構（Destruction）、構造（Construction）和局部搜索（Local Search）以提升解的 質量［19-20］。解構即從工件排序π中隨機抽取d個工件（每次抽取1 個，抽取d次），其他工件的順序保持不變，從而得到d個被刪除工件的排列πR和剩余n-d個工件的排列πD；構造則是將πR中的工件按照被抽取的順序依次插入到πD中使最大完工時間最小的位置，從而得到完整的工件排序π'；局部搜索基于插入鄰域對π'進行局部搜索以提升π'的質量。

為了彌補基本鳥群算法易陷入局部最優、易過早收斂、收斂精度差等不足，借鑒VNS 和IG 算法的思想提升個體歷史最優解和種群歷史最優解的質量，主要思想為：

1）采用VNS 產生新解。基于插入鄰域產生新解并對其進行優劣評估，以充分利用其簡單、高效的優點；基于交換鄰域產生擾動，以進一步強化算法跳出局部最優的能力。

2）引入TBLJP1機制。工件插入過程中易產生大量具有最小最大完工時間而順序不同的工件排序，如何選擇對算法最終的優化結果有著顯著的影響，因此引入TBLJP1機制進一步擇優。

3）由于工件的插入會對離插入位置近的工件產生較大的影響［21］，因此在構造過程中，將插入位置前面及后面的工件去除并重新插入。為了節約計算開銷，此操作僅針對種群最佳工件排序實施。

4）基于Taillard 加速算法［22］計算最大完工時間，以節約計算開銷、提高算法的運行效率。

針對個體最佳工件排序（i=1，2，…，n）的局部搜索方法為：如果個體歷史最優解pi連續M次迭代沒有得到改善，則執行交換操作以產生擾動；然后進行解構、構造和局部搜索操作，如果新的工件排序更優，則更新。基于Matlab 的偽代碼如下：

輸入表示個體歷史最優解pi對應的工件排序；d表示在解構階段去除工件的個數；

輸出。

其中，第2）行計算個體最優解pi未得到改善的連續迭代次數；第3）～5）行為交換操作；第7）行為解構；第8）行為帶TBLJP1機制的構造；第9）～12）行為帶TBLJP1機制的局部搜索；第13）～15）行為新解的接受。

針對種群最佳工件排序π*的局部搜索方法為：如果種群歷史最優解g連續M次迭代沒有得到改善，則基于交換鄰域產生擾動，然后執行一輪（n次）d=1 的解構、構建操作，如果新的工件排序更優，則更新π*，并執行下一輪的解構、構建，綜合考慮優化效果及計算開銷，解構和構建操作最多執行K輪。具體步驟如下：

輸入π*表示種群歷史最優解g對應的工件排序；K表示解構和構建操作最多執行K輪；

輸出π*。

其中，第2）行計算種群最優解g未得到改善的連續迭代次數；第3）～5）行為交換操作；第8）～15）行為一輪解構、構建操作（帶TBLJP1機制），第17）行為新解的接受。

2.2.4 計算復雜度分析

算法主要的計算開銷是對個體適應度值的計算，主要集中在算法迭代階段，因此忽略種群初始化階段的計算開銷。算法每迭代一次，在更新鳥群的位置之后需要重新評估所有個體，計算復雜度為O(N×mn)；對個體的最佳工件排序進行局部搜索，計算復雜度為O(N×d×mn+N×mn2)；對種群最佳工件排序進行局部搜索，計算復雜度為O(3K×mn2)。因此，算法G次迭代的計算復雜度為：O(G× (N× (1 +D) ×mn+(3K+N) ×mn2))。可見，整個算法的計算復雜度并不算高。這主要得益于以下兩點：1）局部搜索基于Taillard 加速算法求解完工時間，能夠有效降低算法的計算復雜度；2）在對個體最佳工件排序的局部搜索中，僅基于交換鄰域產生擾動，并不對新產生的個體進行評估，可節省的計算復雜度為，即通過合理的算法設計降低了計算復雜度。此外，也可以看出，在問題規模確定的情況下，算法的計算復雜度主要取決于參數G、K、N。

3 實驗與分析

3.1 實驗環境及參數設置

實驗仿真環境為：Windows 10 操作系統、主頻3.6 GHz的CPU、8.0 GB 的內存，編程語言及版本為Matlab R2019b。參數設置為：N=100，G=1 000，C=S=1.5，a1=a2=1，P∈[0.8，1]，FL∈[0.5，0.9]，FQ=3，T0=100，Tf=1，β=0.9，M=5，K=n/5，d=3。

為了測試算法的有效性，基于廣泛使用的Rec 標準測試集進行驗證，表1 給出了Rec 標準測試集中各算例的已知最優解，具體的測試算例可通過OR-LIBRARY 獲取，每個算例均獨立運行20 次。以最佳相對誤差（Best Relative Error，BRE）和平均相對誤差（Average Relative Error，ARE）為指標進行比較，計算公式如下：

表1 Rec標準測試集的最優解Tab.1 The optimal results of Rec benchmark

3.2 算法比較

用HBSA1 表示BSA 和種群初始化方法的組合；用HBSA2 表示BSA、種群初始化方法及對個體最佳工件排序進行局部搜索的組合；HBSA3 表示BSA、種群初始化方法及對種群最佳工件排序進行局部搜索的組合。為了驗證改進工作的有效性，針對Rec 標準測試集，將HBSA 與BSA、HBSA1、HBSA2 和HBSA3 進行比較。表2 給出了比較結果。

表2 HBSA與BSA、HBSA1～HBSA3計算結果的比較Tab.2 Comparison of computational results among HBSA，BSA and HBSA1～HBSA3

圖5 給出了HBSA 和BSA 對Rec07、Rec17、Rec27 和Rec37 的收斂曲線。從圖5 可以看出，對于上述所有的算例，HBSA 的初始值、收斂的速度和精度都明顯優于BSA。這是因為在種群初始化階段，HBSA 結合NEHLJP1 啟發式算法產生10%的個體、使用混沌映射生成剩余的個體，使得初始種群擁有更好的初始值和較好的多樣性，算法迭代的效率更高；對個體最佳工件排序和種群最佳工件排序進行局部搜索則增強了算法對解空間的探索能力，并能在一定程度避免陷入局部最優，從而使算法具有更高的收斂速度和收斂精度。綜上所述，比較結果表明：提出的改進措施大幅度地提高了算法收斂的速度和精度，有效提高了算法的性能。

圖5 HBSA和BSA對Rec07、Rec17、Rec27及Rec37的收斂曲線Fig.5 Convergence curves of HBSA and BSA for Rec07，Rec17，Rec27 and Rec37

為了進一步驗證HBSA 的性能，將計算結果與以下4 種優化算法相比較：1）混合差分進化算法（L-HDE）［7］；2）混合共生生物搜索算法（HSOS）［9］；3）離散狼群算法（Discrete Wolf Pack Algorithm，DWPA）［23］；4）多班級教學優化（Multi-Class Teaching-Learning-Based Optimization，MCTLBO）算法［24］。

表3 給出了計算結果的比較。

表3 HBSA與四種優化算法計算結果的比較Tab.3 Comparison of computational results among HBSA and four optimization algorithms

圖6 給出了HBSA 與L-HDE、HSOS、MCTLBO 及DWPA取得的BRE的比較。

圖6 BRE的比較Fig.6 Comparison of BRE

從圖6 中可以看出，HBSA 取得了所有（共21 個）測試用例的BRE的最優值、排名第一；其次是MCTLBO，取得了12個最優值；然后是HSOS，取得了11 個最優值，最后是L-HDE和DWPA，均取得了10 個最優值，從而證明了HBSA 的尋優能力優于上述四種算法。

圖7 給出了HBSA 與L-HDE、HSOS、MCTLBO 及DWPA取得的ARE的比較，同樣地，HBSA 取得了所有測試用例ARE的最優值、排名第一；其次是HSOS，取得了7 個最優值；然后是L-HDE 和DWPA，均取得了5 個最優值；最后是MCTLBO，取得了2 個最優值，從而證明了HBSA 的穩定性強于上述四種算法。

圖7 ARE的比較Fig.7 Comparison of ARE

針對不同規模測試算例求得的BRE和ARE的平均值，HBSA 取得的結果分別為0.098 和0.173，相比L-HDE 的0.502 和0.757、HSOS 的0.583 和1.050、MCTLBO 的0.367 和0.747、DWPA 的0.427 和0.759，和至少下降了73.3%和76.8%，可見，HBSA 優化結果較其他算法提升很明顯。各算法針對不同規模測試算例求得的BRE和ARE的平均值的比較如圖8 所示。

圖8 和的比較

值得說明的是，針對Rec25 和Rec27，僅HBSA 的計算結果達到了目前已知最優解，從而進一步證明了HBSA 的優越性。HBSA 求得Rec27 的最佳工件排序為：π*=［17，11，28，10，4，30，16，29，19，9，25，3，23，21，18，20，24，6，1，12，2，22，27，8，5，26，14，13，7，15］；求得Rec25 的最佳工件排序并不唯一，其中一個工件排序為：π*=［21，29，2，18，4，24，5，16，26，22，28，30，11，20，19，1，9，10，7，14，27，6，23，15，13，12，3，25，17，8］。

4 結語

本文針對以最大完工時間最小化為目標的置換流水車間調度問題（PFSP），提出了一種混合鳥群算法（HBSA）進行求解。結合NEHLJP1 啟發式算法和混沌映射提出了一種新的種群初始化方法，以改善初始種群的質量和多樣性；采用LRV 規則將連續的位置值轉換為離散的工件排序，從而使算法能夠處理離散的調度問題；借鑒VNS 和IG 算法的思想針對個體最佳工件排序和種群最佳工件排序分別提出了局部搜索方法，以強化算法對解空間的探索能力。針對Rec 標準測試集進行了仿真測試，根據最佳相對誤差和平均相對誤差進行比較，結果顯示提出的改進措施大幅度地提高了BSA 收斂的速度和精度，有效地提升了BSA 的性能；此外，HBSA 的表現也明顯優于L-HDE、HSOS、MCTLBO 及DWPA 等算法，具有更強的全局尋優能力和更好的穩定性，尤其是針對Rec25 和Rec27 測試算例，僅HBSA 的計算結果達到了目前已知最優解，進一步證明了HBSA 的優越性，從而為解決置換流水車間調度問題提供了一種更加有效的方法。未來將在大規模地置換流水車間調度問題、其他調度目標的優化及多個調度目標的協同優化等方面做進一步的研究。