基于改進生物地理學優化算法的分布式裝配置換流水車間調度問題

黃佳琳， 張丫丫， 顧幸生

（華東理工大學化工過程先進控制和優化技術教育部重點實驗室，上海 200237）

置換流水車間調度問題(Permutation Flowshop Scheduling Problem, PFSP)是制造系統和工業過程中廣泛研究的組合優化問題[1]，通常假設所有的工件都在一個工廠中進行加工，即單一工廠生產模式。現如今，在全球化的背景下，分布式制造以低成本、低風險、高質量的優勢取代了單一工廠生產模式，成為工業生產過程中的主流形式。比起單一工廠調度問題，分布式制造的調度問題更為復雜。它不僅需要考慮工件在機器上的加工順序，還必須考慮如何將工件合理地分配到相應的工廠進行加工。不同工廠的不同工件分配會形成不同的調度方案，從而影響供應鏈的績效[2]。

裝配流水車間調度問題(Assembly Flowshop Scheduling Problem, AFSP)廣泛存在于生產制造系統中，用于生產由不同工件裝配而成的多種產品[3]。考慮到裝配系統在工業過程中的實際應用，裝配流水車間調度問題也是生產調度領域的重點問題。裝配流水車間是一個混合生產系統，其中各個生產操作都是獨立并且同時執行的，以便將工件運輸到裝配線，及時進行產品的組裝。在組裝過程中，可以由給定數量的不同工件根據裝配程序制造各種各樣的最終產品，裝配程序代表了由不同供應商提供的不同工件之間的組裝關系[4]。

分布式裝配置換流水車間調度問題(Distributed Assembly Permutation Flowshop Scheduling Problem,DAPFSP)是分布式置換流水車間調度問題和裝配流水車間調度問題的結合，最早由Hatami 等[5]提出。Hatami 等針對DAPFSP 問題，以最小化裝配工廠完工時間為目標，提出了基于不同結構的啟發式算法和可變鄰域下降(VND)算法等12 種方法。在此基礎上，越來越多的優化算法被應用于求解DAPFSP問題。2016 年，Wang 等[6]提出了基于分布估計算法的模因算法(EDAMA)來求解DAPFSP 問題，通過與文獻[5]的12 種啟發式與元啟發式算法比較，驗證了 EDAMA 算法的優越性。2017 年，Lin 等[7]采用回溯搜索超啟發式(BS-HH)算法，同樣與12 種方法以及EDAMA 等智能優化算法進行比較，突出了BSHH 算法的有效性。2019 年，Pan 等[8]針對新型 DAPFSP問題的不同的CPU 時間和解決方案質量的需求，提出了一個混合整數線性模型，還列出了3 種不同結構的啟發式算法、兩種可變鄰域搜索方法以及迭代貪婪算法，最后在算法性能和運算時間兩方面與其他16 個已有算法進行對比，結果表明所提算法能夠高效地解決新型DAPFSP 問題。

生物地理學優化(Biogeography-Based Optimization, BBO)[9]算法自提出以來，因對問題依賴度小、算法參數少、易于實現等優點備受青睞。Rahmati 等[10]采用BBO 算法求解包含3 個目標函數的柔性作業車間調度問題，并且對遺傳算法和BBO 算法進行比較，利用基準測試數據（Brandimart 數據）以及Barnes和Chamber 數據的運算，凸顯了BBO 算法的優勢。Lin 等[11]采用和聲搜索算法和基于對立的學習方法改進BBO 算法來求解專色印刷的專色匹配問題，通過與粒子群算法的比較，驗證了BBO 算法的有效性。然而，BBO 算法存在收斂速度緩慢、易陷入局部最優解以及在規定迭代次數中難以獲得最優解等缺點[12]。考慮到分布式裝配置換流水車間的加工特點，本文設計了3 種改進策略：首先，使用加工時間最短優先（Shortest Processing Time，SPT）規則和 NR2規則改善初始可行解的結構；其次，在變異過程中加入基于工廠完工時間的工件插入啟發式方法，優化工件的工廠分配策略及其在各工廠內的加工順序；最后結合模擬退火算法，跳出局部最優，提高算法尋優的質量。仿真結果證明了改進的BBO 算法求解分布式裝配置換流水車間調度問題的有效性。

1 分布式裝配置換流水車間調度問題

1.1 問題的描述

分布式裝配置換流水車間調度問題包括兩個階段：生產階段和裝配階段，并且可以概括為3 個子問題：工件調度、產品調度和工廠分配，如圖1 所示。

圖 1 分布式裝配置換流水車間調度問題Fig. 1 Distributed assembly permutation flowshop scheduling problem

1.2 模型的目標函數

2 生物地理學優化算法

BBO 算法是一類基于種群和生物啟發的群智能優化算法，其核心是棲息地間種群的遷移和變異過程，同時這兩個過程也是算法實現優化操作的主要步驟。

2.1 生物地理學優化算法的設計原理

生物種群分布于不同的棲息地，各棲息地都可用對應的適宜度指數(Habitat Suitability Index,HSI)來表示。與HSI 相關的特征包括棲息地的降雨量、植被的多樣性和氣候等因素，構成了一個描述棲息地適宜度的向量SIV(Suitable Index Vector)[15]。應用BBO 算法求解優化問題時，一個棲息地對應優化問題的一個可行解，通過計算各棲息地的適宜度值來評價這些解的優劣程度。根據不同棲息地之間物種的遷移操作和棲息地內物種的變異操作，使適應度值較差的棲息地獲得更多適應度值較好的棲息地的信息，實現棲息地的不斷進化[16]。

2.2 生物地理學優化算法的遷移操作

BBO 算法通過遷移算子實現棲息地之間的信息交互，從而達到進化的目的。棲息地的適宜度值越高，其所能容納的物種數量越多，反之則越少，這就需要建立一個表征物種數量與棲息地適宜度關系的映射函數[17]。BBO 算法根據各個棲息地的適宜度值，從大到小進行排序，設棲息地數量為P，最大物種數為 Nmax，則棲息地 n 的物種數量 N(n)=Nmax-n，n=1, 2, …, P（n 是各棲息地經過排序后的序號）。物種在棲息地之間的遷移操作根據遷出率μ(n)和遷入率λ(n)進行，各棲息地的μ(n)和λ(n)的計算公式如式(8)、式 (9)所示：

圖 2 遷入率、遷出率與物種數量的關系Fig. 2 Relationship between immigration rate, emigration rate and species quantity

2.3 生物地理學優化算法的變異操作

突發的災難性事件能夠完全改變一個棲息地的生態環境，導致棲息地的適宜度值產生巨變，生物地理學中通過變異來模擬這一情況[19]。BBO 算法根據變異概率隨機地修改棲息地的特征向量，變異概率主要取決于棲息地的物種數量概率，也可以說和棲息地的物種數量息息相關。物種數量為N(n)的棲息地發生變異的概率 mn如式(10)所示：

3 MBBO 算法求解 DAPFSP 問題

3.1 編碼與解碼

應用改進的生物地理學優化(MBBO)算法求解分布式裝配置換流水車間調度問題時，在初始化階段將采用兩種不同的編碼方式生成初始可行解，分別稱為規則解和隨機解。

規則解主要是根據SPT 規則生成。將每個產品中的工件按SPT 規則進行排列，確定每個產品的工件加工順序。在此基礎上，計算每個產品的裝配開始時間，并規定最早開始裝配的產品排在前面，由此產生產品序列。兩者結合即為一個完整的工件加工序列，這樣產生的規則解是唯一的。最后采用NR2規則進行解碼。NR2規則定義為[13]：將工件 j 分配給包含工件j 之后最大完工時間最小的工廠，由此生成新的調度方案。

隨機解引入了“虛擬工件”的概念，其包含了工件和工廠兩種因素。首先，將所有工件進行隨機排列，生成一個工件加工序列；然后，將工廠作為“虛擬工件”，插入到已有的工件加工序列中，“虛擬工件”的個數同工廠的數量一致，并且“虛擬工件”用數字“0”表示。需要注意的是，每個隨機解的第1 列必須是“虛擬工件”，即必須為“0”，否則將存在不能在任何工廠加工的工件，這樣的隨機解就變成了不可行解。除此之外，若隨機解存在兩個“虛擬工件”相鄰的情況，就表示存在某個工廠處于閑置狀態，不加工任何工件。這樣的解雖然屬于可行解，但根據實際生產過程可以判斷，此類解的適應度值一般比較低。為了提高初始可行解的質量，MBBO 算法以將工件均勻分配給各個工廠的方式生成新的初始解，取代存在工廠閑置情況的初始解。隨機解的解碼根據最大完工時間的計算公式進行計算。

以 8 個工件、2 臺機器、2 個工廠、2 個產品的分布式裝配置換流水車間調度問題為例，隸屬于2 個產品的工件分別為：產品1={1,2,4,8}，產品2={3,5,6,7}。對于規則解，所有工件按SPT 規則排列后，每個產品的工件加工順序如下：產品1={8,1,2,4}，產品2={7,5,3,6}，此時，兩個產品的開始裝配時間分別為：產品1=127，產品2=133，則規則解的工件排序如圖3 所示。最后根據NR2規則解碼，得出規則解的具體形式及最大完工時間 Cmax(Λrule)=501 ，規則解的具體形式如圖4所示。

圖 4 規則解的具體形式Fig. 4 Specific form of rule solution

針對這個例子，隨機解就是利用randperm 函數對1～9 進行隨機排序，并把大于8 的數置零，最后在首位插入一個“0”。隨機解的數量很多，從中挑出一個，其具體形式如圖5 所示。

圖 5 隨機解的具體形式Fig. 5 Specific form of random solution

3.2 按照適應度值排序

在執行精英保留策略、遷移操作和變異操作之前，需要計算各個棲息地即各個初始可行解的適應度值，并按照從大到小的順序進行降序排序，最優解排在第一位。

3.3 精英保留策略

BBO 算法在迭代過程中有可能生成適應度值更高的解，若不對這些優良解采取保護措施[17]，放任它們參與遷移操作和變異操作，很容易破壞優良解的結構，喪失獲取更優可行解的機會，導致算法的搜索能力下降。MBBO 算法加入了精英保留策略，即在每次執行遷移和變異操作之前，取初始可行解數量的10%作為精英解，不作任何改變，而是保留到下一步迭代過程再進行相應操作。

3.4 遷移操作

BBO 算法通過遷移操作，用較優解中的元素來取代較差解中的元素，以此實現棲息地之間的信息交互。MBBO 算法的遷移操作和BBO 算法的遷移操作大同小異。對每個解，在執行遷移操作時，改進前后的算法同樣都是按位進行循環，根據遷入率判斷該位是否發生遷入，若發生遷入，再根據輪盤賭法選擇遷出的位，進行相應位的交換操作。MBBO 算法有兩個特別之處：第一，對于規則解，規定其不參與遷移操作。因為規則解的特色就在于它是產品序列和各產品工件序列的結合，每個產品的工件不能分開，否則將會影響產品的裝配開始時間，進而影響解的結構，致使該解失去作為規則解的優勢。第二，對于隨機解，在按位循環判斷是否發生遷入或是根據輪盤賭選擇遷出位的時候，都必須跳過每個解的第一位（第一位都是“0”，即“虛擬工件”），否則將會生成不可行解。

3.5 改進的變異操作

BBO 算法利用變異操作來保證解的多樣性，抑制算法的早熟現象。BBO 算法的變異過程是根據變異概率判斷解（棲息地）的某個特征分量是否發生突變，具體操作與遷移過程相似。首先按位進行循環，根據變異概率判斷該位置元素是否發生變異，若發生變異，則隨機選擇變異的位，進行合法交換即可。然而，BBO 算法的變異過程隨機性較大，很有可能破壞之前的優勢解，因此MBBO 算法對此進行了改進，加入了基于工廠完工時間的工件插入啟發式方法。在MBBO 算法的變異過程中，利用變異概率判斷某個解而不是解的某個特征分量是否進行突變，若確定該解發生突變，則依次將該解中完工時間最大的工廠的每個工件插入到該解中完工時間最小的工廠的工件序列中，并找到最佳的插入位置。插入最佳位置后，比較新解和舊解的工廠最大完工時間，若新解的工廠最大完工時間小于舊解的最大完工時間，則接受新解，反之，則返回舊解。基于工廠完工時間的工件插入啟發式方法的偽代碼如下：

3.6 模擬退火算法

為了提高解的質量，MBBO 算法還結合了模擬退火算法，有助于跳出局部最優解，增強算法的搜索能力。

考慮到MBBO 算法的效率問題，在算法迭代過程中，記錄每次的最優值，若在最后20 次的迭代過程中，最優值都保持不變，則對得到的最優解采用模擬退火算法進行進一步尋優。模擬退火算法的偽代碼如下：

3.7 MBBO 算法求解 DAPFSP 問題

MBBO 算法求解DAPFSP 問題的過程中，可行解表示棲息地，每個可行解都由一個行矩陣表示，而棲息地中的物種由矩陣中的元素及它的位置信息共同表示。適應度值對應著于目標函數值的倒數，目標函數值即式(7)計算出的值。MBBO 算法求解DAPFSP 問題的具體流程如圖6 所示。

4 仿真實驗

為了驗證改進的生物地理學優化算法求解分布式裝配置換流水車間調度問題的有效性，對兩組基準數據（http://soa.iti.es）進行仿真計算。每組數據由4 個變量組成：n（工件數）、m（機器數）、F（工廠數）、H（產品數）。第1 組由900 個小型實例組成，其中，n={8,12,16,20,24}，m={2,3,4,5}，F={2,3,4}，H={2,3,4}。第2 組由540 個大型實例組成，其中，n={100,200}，m={5,10,20}，F={4,6,8}，H={30,40,50}。對于小型實例，每個組合都有5 個例子；對于大型實例，每個組合有 10 個例子[6]。

采用平均相對百分比偏差(ARPD)來評估算法的性能[7]，計算公式如下：

其中：Cbest為所有實例已知的最佳解決方案的最優值；Ci為算法每次運行后得到的最大完工時間的最小值，即算法的最優值，一共運行 R 次。如果ARPD＜0，則表明產生了新的最佳解決方案。所有實例的已知最優解都可在http://soa.iti.es 上獲得。

4.1 參數設置

MBBO 算法有4 個關鍵參數：棲息地數量P（初始化產生的可行解的數量）、最大突變率mmax、最大迭代次數MaxIterations 以及退火率α。為了研究這4 個參數對MBBO 算法性能的影響，采用正交試驗的方法對實例I_24_3_2_2_1 進行仿真計算。其中的“24”表示工件總數為 24，“3”表示每個工廠都有 3 臺機器，第 1 個“2”表示一共有兩個工廠，第 2 個“2”表示最終裝配出兩個產品，末尾的1 表示這個實例是這個組合的第1 個例子。表1 列出了影響算法性能的關鍵參數的不同組合。

圖 6 MBBO 算法求解DAPFSP 問題的流程圖Fig. 6 Flow chart of MBBO for solving DAPFSP

表 1 不同參數值的組合Table 1 Combination of different parameters

所有的參數組合都采用MBBO 算法運行10 次，計算平均最大完工時間(AM)，所得結果列于表2，由此觀察不同參數對算法性能的影響，最終找出最令人滿意的參數組合。

對于每個參數，將平均最大完工時間作為關鍵指標，判斷每個參數的趨勢，結果如圖7 所示。

由圖7 可以看出，棲息地數量和最大迭代次數越大，算法的性能越好，但同時計算成本會增加，時間明顯變慢。綜合考慮算法的性能效果以及耗費的時間成本，選取MBBO 算法參數如下：P=50，mmax=0.10，MaxIterations=100，α=0.9。此外，最大遷入率 I 和最大遷出率E 均設為1，取棲息地數量P 的10%作為保留的精英解。

4.2 模擬退火算法對MBBO 算法的影響

圖 7 參數趨勢圖Fig. 7 Parameter trend chart

表 2 不同組合的平均最大完工時間Table 2 Average maximum completion time for different combinations

為了驗證模擬退火算法對改進生物地理學優化算法的有效性，對所有小型實例進行仿真，比較了使用和不使用模擬退火算法的MBBO 算法的實例運算結果。兩個算法都具有相同的參數設置（除了SA 算法的部分）和停止條件，并且獨立運行5 次。表3 列出了F 和n 的15 個組合的平均ARPD 值，每個組合包含60 個小型實例。

模擬退火算法具有很強的全局搜索能力，能夠使算法跳出局部最優而趨向于全局最優。從表3 可以看出，在大多數組合中，融合了模擬退火算法的MBBO 算法可以利用模擬退火算法的優勢來獲得較低的ARPD 值。不僅如此，MBBO 算法在有和沒有模擬退火算法的情況下獲得的ARPD 平均值分別為0.051 和0.100，前者的算法性能明顯高于后者。由此可見，混合入模擬退火算法可以有效地改善所提出的MBBO 算法的性能。

4.3 DAPFSP 問題的小型實例

運用MBBO 算法求解分布式裝配置換流水車間調度問題的900 個小型實例，每個實例都獨立運行5 次，記錄每次得到的算法最優值，利用ARPD 值評估算法的性能。表4 列出了F 和n 的15 種不同組合分組的統計結果，每個組合都包含60 個實例。取60 個實例的平均ARPD 值作為最終結果，并與H11、H12、 H21、 H22、 H31、 H32、 V NDH11、 V NDH12、 V NDH21、VNDH22、 V NDH31、 V NDH32算法進行比較。這 12 個算法都是用來解決DAPFSP 問題的有效方法，各算法的結果直接從文獻中獲得[5]。

表 3 MBBO 算法的小型實例運算結果Table 3 Small-sized instances results of MBBO algorithm

表 4 小型實例平均ARPD 值的結果對比Table 4 Comparison of average ARPD values of small-sized instances

從表4 可以看出，對于所有的小型實例，MBBO算法獲得的結果明顯優于12 個啟發式與元啟發式算法，且每個組合的平均ARPD 值和MBBO 算法的平均值均遠遠小于列出的12 個算法。不僅如此，MBBO 算法還更新了一些已知最佳方案，例如組合2×20 和 2×24 的 60 個實例的 ARPD平均值小于零。

本文還將MBBO 算法與BBO 算法的運算結果進行了比較。由于BBO 算法較為簡單，運算速度快，因此對BBO 算法的參數進行如下調整：P=100，mmax=0.1，MaxIterations=200，I=E=1，取 P 的 10% 作為保留的精英解。由表4 可知，MBBO 算法求解DAPFSP問題的效率明顯高于BBO 算法。在工廠數和工件數均較小的情況下（如 2×8 和 2×12），BBO 算法以初始棲息地和迭代次數多的優勢，比MBBO 算法略勝一籌，但差別并不大。而當工廠數和工件數增大之后，BBO 算法便顯出頹勢，所得結果大不如MBBO 算法。所以，針對DAPFSP 問題，引入本文的3 種策略能有效地改善BBO 算法的性能，提高所得最優解的質量。

4.4 DAPFSP 問題的大型實例

針對分布式裝配置換流水車間調度問題的540 個大型實例，同樣運用MBBO 算法，將每個實例獨立運行5 次，記錄每次得到的算法最優值，利用ARPD 值評估算法的性能。表5 列出了工件數n=100和n=200 時的統計結果，每組都包含270 個實例，最終結果為每組所有實例的ARPD 平均值，然后與12 個啟發式與元啟發式算法以及BBO 算法的結果進行比較。

表 5 大型實例平均ARPD 值的結果對比Table 5 Comparison of average ARPD values of large-sized instances

由表 5 可以看出，當n=100 時，MBBO 算法有較大的優越性，其獲得的大型實例的ARPD 平均值要遠小于 H11、H12、H21、H22、H31、H32、 V NDH11、 V NDH12、VNDH21、 V NDH31這10 種算法的結果。當工件個數上升到 n=200 時，MBBO 算法獲得的大型實例的ARPD 平均值均優于 H11、H12、H31、H32這 4 種啟發式算法的結果，而比另外幾種啟發式和元啟發式算法稍顯不足。在大規模的實例中，與BBO 算法相比，MBBO 算法顯然更為合理、高效，兩個算法結果的平均值相差0.753，MBBO 算法優勢顯著。

綜上所述，利用MBBO 算法求解DAPFSP 問題時，針對ARPD 平均值這個指標，在多數規模的實例上均效果良好，在某些實例上還找到了比已知方案更佳的結果。表6 列出了小型實例和大型實例中MBBO算法更新的最佳方案。MBBO 算法在初始化階段利用SPT 規則、NR2規則和“虛擬工件”改良初始解，縮小算法搜索解空間的范圍，提高搜索效率。在變異階段，根據各工廠完工時間的信息，采用基于工廠完工時間的工件插入啟發式方法，優化工件的工廠分配及加工順序。同時，結合模擬退火算法，跳出局部最優，提高了算法的搜索能力。MBBO 算法是求解DAPFSP 問題的一種有效算法。

5 結束語

本文針對分布式裝配置換流水車間調度問題，提出了一種改進的生物地理學優化算法及其應用于分布式裝配置換流水車間調度問題的基本步驟，取得了較好的優化效果。針對BBO 算法的缺點，提出了3 種改進策略：使用SPT 規則和NR2規則初始化棲息地；在變異過程中加入基于工廠完工時間的工件插入啟發式方法；加入模擬退火算法跳出局部最優。這3 種改進策略提高了算法的搜索能力，改善了算法的尋優效果。通過900 小型實例和540 個大型實例的仿真計算，并與12 個啟發式與元啟發式算法以及BBO 算法進行比較，驗證了MBBO 算法求解DAPFSP 問題的有效性。

今后可以從以下幾個方面做進一步的研究：

(1) 在遷移和變異操作過程中，MBBO 算法只是針對遷移和變異的方式進行改進，沒有對其根本的

遷入率、遷出率和變異概率進行優化。可以考慮對遷移概率和變異概率的計算公式做出相應的改進，以提高算法的搜索能力。

表 6 MBBO 算法更新的最佳方案Table 6 Best solutions updated by MBBO

(2) 目前，利用啟發式方法和智能優化算法求解分布式裝配置換流水車間調度問題已經有了初步進展。可以考慮在DAPFSP 問題的基礎上進行拓展，進一步加深問題的復雜度，例如研究具有順序相關準備時間的分布式裝配置換流水車間調度問題等。