基于IIGA 的分布式裝配置換流水車間調度＊

董 海 王志彬

（①沈陽大學應用技術學院，遼寧 沈陽 110000；②沈陽大學機械工程學院，遼寧 沈陽 110000）

近年來，由于分布式制造系統在提高生產效率和降低成本中起到了關鍵的作用，生產制造開始從集中式向分布式轉變。分布式裝配置換流水車間調度問題（distributed assembly permutation flowshop scheduling problem，DAPFSP）是分布式置換流水車間調度問題和裝配流水車間調度問題的結合，在計算復雜度上，分布式裝配置換流水車間已被證明屬于NP-hard 問題。DAPFSP 通常以最小化最大完工時間（makespan）和最小化總流經時間（total flowtime，TF）為優化目標，兩種優化目標既涉及機器的平衡使用，又涉及工件的快速處理。對于以最小化最大完工時間為優化目標，Sara H[1]等建立了混合整數線性規劃（mixed integer linear program，MILP）模型，提出了多個啟發式方法用于構造初始解，并設計變領域下降算法進行求解。Lin J 等[2]提出1 種回溯搜索超啟發式（backtracking search hyper-heuristic,BS-HH）算法進行求解，并與文獻[1]以及分布估計等智能優化算法進行比較，突出了BS-HH 算法的有效性。Pan Q K 等[3]提出了一個混合整數線性模型，列出了3 種不同結構的啟發式算法，最后通過與其他16 個已有算法進行仿真實驗，驗證了所提算法在算法性能和運算時間兩方面的優越性。黃佳琳[4]等提出了一種改進的生物地理學（modified biogeography-based optimization,MBBO）優化算法進行求解，與現有的12 種啟發式算法以及基本生物地理學優化算法進行比較，證明了MBBO 算法的優越性。對于以最小化總流經時間為優化目標，Fernandez-Viagas V[5]等首先提出了這個問題，并提出18 種啟發式算法和1 種進化算法進行求解。Pan Q K[6]等提出了3 種構造性啟發式和4種元啟發式進行求解。Sang H Y[7]等設計了3 種離散的雜草入侵算法，該算法具有很強的自適應性和魯棒性，可以有效求解最優解。張梓琪等[8]針對低碳分布式裝配流水車間調度問題，提出一種基于多維分布估計算法（multidimesnsional estimation of distribution algorithm,MEDA）進行求解。

綜上所述，在問題求解層面，該問題具有大規模、強耦合和不確定等復雜性，目前基于分布式裝配置換流水車間調度模型的各類優化目標研究得非常廣泛，但以總流經時間為優化目標的DAPFSP 研究還十分有限。因此，對其研究具有重要的學術意義和工程應用價值。

迭代貪婪（iterated greedy，IG）算法是由Jacobs L W[9]等提出的一種結構簡單、參數少以及快速有效的智能優化算法，通常在當前解的鄰域內不斷地進行局部搜索來獲得最優解，并在此基礎上，通過破壞和重構策略加強對較好解所在局部領域的搜索能力，IG 算法針對不同的優化目標和不同的流水線調度問題都展現出其優異的性能。Lin S W[10]等提出1 種改進IG 算法解決以最小化最大完工時間為目標的DPFSP，增加了解的質量。Fernandez-Viagas V[11]等針對以最小化最大完工時間為優化目標的DPFSP，提出一種有界搜索IG 算法進行求解。Huang Y Y[12]等針對以總流經時間為優化目標的DAPFSP，提出一種基于群體思維的改進迭代貪婪（groupthink iterated greedy，GI）算法。錢斌[13]等針對以最小化總延遲時間為優化目標的 DPFSP 問題，建立問題排序模型，并提出混合迭代貪婪算法（hybrid iterated greedy，HIG）進行求解。

以上研究均使用了IG 算法求解流水車間的相關調度問題，其在局部鄰域搜索上展現了良好的效果。然而，僅僅采用局部鄰域搜索難以使解在迭代過程中跳出搜索范圍，降低了解的多樣性。傳統IG 算法使用模擬退火準則來提高解的多樣性，但實驗效果并不明顯。針對DAPFSP 問題，構建以最小化總流經時間為目標的數學模型，提出一種改進的迭代貪婪(improved iterated greedy，IIG)算法。該算法主要通過結合NEH 算法和CDS 算法提出一個新的初始化方法以獲得高質量的初始解，為加快算法效率、降低問題復雜性，設計了新的兩段銷毀、構建和本地搜索方法，增加了解決方案的多樣性且擴大了搜索空間；最后通過仿真驗證改進的迭代貪婪算法求解DAPFSP 的有效性和魯棒性。

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

1.1 問題模型

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

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

在生產階段，有n個工件和f個相同的工廠。工件j∈{1,2,···,n}需要分配給任意工廠l∈{1,2,···,f}進行加工；每個工件都能在所有工廠進行加工，并且只能在一個工廠加工；每個工廠都配有m臺相同的機器，所有工件都需要根據機器i∈ {i1,i2,···,im}的順序依次在相同的路徑中加工；工件j在機器i上加工時記作Pi,j。在裝配階段只有一個裝配工廠，所有的工件在生產加工完畢后都會運輸到裝配工廠進行產品的組裝；在裝配階段，有s個產品和一臺裝配機器，每種產品r∈{1,2,···,s}均具有已定義的組裝程序；產品的裝配只能在其包含的作業完成且裝配機空閑時開始；屬于同一產品的作業是連續處理的，下一個產品的操作只能在屬于同一產品所有作業處理完畢后才能執行。解決DAPFSP 的關鍵是確定任務分配給工廠、每個工廠中任務生產順序以及產品裝配順序，從而使整個操作的TF 最小化。

根據上述問題描述并參考文獻[12]建立TF 數學模型及其相關約束條件

式中：Xj,k表示二進制變量，如果作業j是作業k的前身，則等于1；否則，Xj,k=0。對于Yr,t也是如此。如果產品r是產品t的前序，則等于1；否則，Yr,t=0。Ci,j是機器i上作業j的完成時間，Cr是產品r的完成時間。Pr是產品r的裝配時間，zr是產品序列中第一個r產品中包含的作業總數。此外，g是一個足夠大的正數，nt是產品t中包含的作業數。

式（1）表示TF 最小化；式（2）和（3）表示每個作業必須只有一個前置作業和一個后續作業；式（4）和（5）表示虛擬作業0 的前置作業和后續作業被強制執行f次；式（6）表示一個作業不能同時是另一個作業的前置作業和后續作業；式（7）表示連續處理屬于同一產品作業；式（8）表示作業j在機器i上處理后，只能在機器i上處理；式（9）表示如果作業j是作業k的后續任務，則作業j只能在作業k處理完成后在機器i上處理；式（10）和（11）表示每個產品只能有一個前置產品和一個后續產品；式（12）表示一個產品不能同時是另一個產品的前置產品和后續產品；式（13）表示每個產品所包含的作業部分在尚未生產之前，產品無法進入裝配階段；式（14）表示如果產品t是產品r的前置任務，則產品r在產品t完成之前無法開始裝配操作；公式（15）定義TF；式（16）～（19）定義決策變量的域。

為了更好地理解上述問題，引用1 個例子。假設有6 個工作崗位、2 臺機器、2 個工廠和3 種產品。表1 列出產品和作業之間的關系、機器處理的時間，圖2 是調度甘特圖，從甘特圖中可以清楚地看到一個產品與其包含的作業具有相同的顏色。作業3、1、4 分配給工廠1，其他作業在工廠2 生產，TF是每個產品完成時間的總和。

圖2 兩個階段的調度甘特圖示例

表1 產品的處理時間和關系

2 迭代貪婪算法

迭代貪婪算法自提出以來已在各種調度環境中獲得了許多成功的應用，本文提出一種改進的IG算法解決DAPFSP，與傳統的IGA 不同，該算法首先使用所提出的初始化過程生成一組解的集合?，并對集合?中的最優解進行局部搜索；然后算法進入迭代階段，在迭代過程中，使用選擇機制在集合?中選擇解φ；將破壞階段應用于解φ獲得兩個部分序列，一個是被移除的產品和工作所組成的序列φD，另一個φR是解的剩余部分；對φR進行產品的本地搜索，生成次優解將移除的產品和作業重新插入，該過程稱為構造階段，并重新生成完整的解φ′，對φ′執行作業的本地搜索生成解φ″；最后，使用接受準則來判斷新解φ″是否符合標準，具體過程如下。

2.1 解的表示

解決方案分為兩部分內容，產品序列和作業序列，每一部分都對應一個產品。只有當一個產品中包含的所有作業都生產完成后，才能進行下一個產品作業的生產。當產品中包含的所有作業完成時，允許產品進入裝配階段進行加工。假設1 個解表示為φ，其中產品序列記錄為Δ={Δ1,Δ2,···,Δs}，以及產品Δr中包含的作業序列πr={πr1,πr2,···,πrn}，其中n指產品Δr中包含的作業數量。

2.2 基于CDS 和NEH 的啟發式算法

初始解的質量可能會影響IGA 的性能，因此本文提出一種基于 CDS 方法和NEH 的初始化啟發式方法（CDS-NEH）。CDS 方法是通過將機器m分為2 組，反復使用Johsnon 算法對2 臺機器上的作業進行排序，從而基本上將流水車間中n個作業問題劃分為m-1 個兩臺機器作業問題的集合，得到盡可能多的替代作業序列，然后以最小化總流經時間排序，選取最佳序列。NEH 已被證明是解決流水車間問題最有效的啟發式方法之一，并且已被擴展到以最小化完工時間和最小化總流經時間為優化目標的DPFSP。其具體步驟如下：

步驟1：使用CDS 方法初始化每個產品的作業序列，找到最佳序列πorigin={π1,π2,···,πm}。

步驟2：計算每個產品的裝配時間和其包含的所有作業的總處理時間r∈{1,2,···,s}。

步驟3：按照Pr對各工件進行降序排序，得到初始序列Δorigin={Δ1,Δ2,···,Δs}。

步驟4：隨機取產品Δu將其插入到Δ 中所有可能位置并測試其TF值，最終將產品插入到使TF最小的位置pt處。

步驟5：從Δ 中抽取位置pt-1或pt+1的產品h，重復執行步驟4，直到所有工件都被考慮。

該啟發式算法具有一定的隨機性質，在初始化步驟中重復使用CDS-NEH 算法生成多個初始解。如圖3 所示為工件數n=100，機器數m=5，工廠數F=4 和產品數s=30 的一組DAPFSP 標準實例，采用隨機初始化和CDS-NEH 方法的對比圖，從圖中可以明顯看出改進后的初始解更優。

圖3 初始解對比圖

2.3 本地搜索

對于組合優化問題，每個最優解都是所有鄰域結構下的局部最優解，本文基于傳統IG 算法提供了兩種本地搜索過程，一個用于產品，另一個用于作業。

（1）假設φ代表當前解，其產品序列為Δ={Δ1,Δ2,···,Δs}，隨機且不重復抽取1 個產品Δr將其插入Δ 中所有可能的位置，若所生成的鄰域解中的最優解優于當前解（φ*＜φ），則將當前解替換為最佳鄰域解，重復這一過程，直到所有產品都被考慮，且沒有更好的新解決方案生成。

（2）根據產品序列Δ 對每個產品的作業執行本地搜索操作，假設Δr中的作業序列為πr={πr1,πr2,···,πrn}。隨機且不重復抽取πr中一道工序，將其插入所有可能位置并計算TF值，找到使TF 最小所生成的新序列，重復這一過程，直到所有工序都被考慮。

2.4 破壞與重構階段

破壞階段的設計是為了增加解的多樣性，并為隨后的局部搜索階段增加搜索空間。首先針對產品，從當前產品序列Δ 中隨機刪除d個產品，得到兩個產品序列ΔD和ΔR，然后隨機刪除序列ΔD中每個產品的α個作業，得到2 個作業序列。

在重構階段，產品和工作將從破壞階段被重新插入到剩余的解決方案中，以生成完整的解決方案。因此，與破壞階段類似，重構階段也分別針對產品和工作。首先將移除的產品序列ΔD中的產品插入序列ΔR中，每當插入1 個產品時，該產品刪除的作業序列 πD r也將被插入到序列中。重復這一過程，直到生成1 個新的完整的解決方案。產品的插入規則為：假設要插入的產品是Dr，r∈{1,2,···,d}，首先測試其插入到ΔR中每個可能位置時的TF值，然后比較這些TF值，最終將產品插入到TF值最低的位置，作業的插入規則與產品相同，具體操作步驟如下：

步驟4：每次插入后檢測其TF值，產品最終將插入到TF值最低的位置，持續執行步驟3，直到生成一個完整的解決方案。

圖4 所示[14]為1 個長度為5 的完整方案隨機取出2 個工件，得到一個長度為3 的部分序列，將取出的工件逐個重新插入到序列中，插入過程中同時檢驗其TF值，重復這一過程，直到得到完整的解決方案。

圖4 破壞重構操作示意圖

2.5 選擇和接受準則

選擇機制每次在迭代開始時從解集?中選擇一個解φ，然后對其進行破壞，重構階段，TF值和迭代次數經常被用作選擇因子。因此，提出一種新的選擇機制：在集合?中隨機選擇兩個解，然后選擇TF值比較低的解或者選擇迭代次數較小的解。

接受準則是用于判斷算法通過局部搜索后生成的解是否可以進入集合?。比較集合中最差的解決方案和新的解決方案的TF值。如果新的解決方案的TF值較低，并且與當前集合中的所有個體不同，那么將新的解決方案替換，并將其迭代次數增加1。否則，新的解決方案將被丟棄。

2.6 算法流程

根據上述描述，整個算法流程如圖5 所示：

圖5 改進IG 算法流程圖

3 仿真實驗

3.1 實驗設置

算法程序是在Matlab2018b 進行編程，實驗運行環境為Intel（R）Core（TM）i5-7300HQ 2.50 GHz 12 GB 內存的計算機。

為驗證改進迭代貪婪算法求解DAPFSP 的有效性，本文選取文獻[15]驗數據作為參考，并對其進行修正和擴充，得到如下實驗數據：工件數n={100}，機器數m={5,10}，工廠數F={4,6,8}和產品數s={30,40,50}，一共18 組測試問題，每組實例包含10 個具有不同處理時間的實例。評價指標采用平均相對百分比偏差（average relative deviation,ARD）。

式中：TFbest表示最佳解決方案，每個測試獨立運行20 次進行比較。因此，獨立運行的數量R為20，TFr表示20 次獨立運行中第r個實驗的解。

3.2 參數設置

所提出的算法需要確定3 個重要參數，初始化生成種群中解的個數ω，在銷毀階段移除的產品數d以及在銷毀階段與移除的作業數有關的參數β。根據初步實驗，將ω設置為6、8、10 和12 四個級別，d分為3、5、7 和9 四個級別，β分為1、2 兩個級別。該算法參數校準共有32 種不同的配置，在測試過程中，為了避免結果出現過擬合現象，每組參數獨立運行5 次，當運行時間大于（20×m×n）ms 時，算法退出迭代。最后，通過使用方差因素分析（ANOVA）方法研究實驗結果，進而確定了算法最佳關鍵參數組合為：ω=6，d=5，β=2。

3.3 算法比較

為驗證改進迭代貪婪算法的有效性，選取文獻[16]中的競爭模因算法（competitive memetic algorithm，CMA），文獻[4]混合生物地理學算法（hybrid biogeography-based ptimization，HBBO），文獻[7]混合搜索的離散入侵雜草優化算法（hiscrete invasive weed optimization with hybrid search，HDIWO）和文獻[17]種群迭代局部搜索算法（group iterated local search，GILS）進行比較，其中GILS 算法已被證實在求解DAPFSP 問題上優于單純的IG 算法，每種算法在相同的時間下進行性能比較，運行停止標準都為（n×m×20）ms，對18組（每組10 個）實例均進行20 次獨立實驗，表2為18 組實例各算法平均ARD實驗結果和每組實例中得到最優值的運行時間，圖6 為對比算法95% 置信區間。

表2 各算法ARD 結果對比

圖6 對比算法95%置信區間

由表2 可知，ARD值越小算法所得總流經時間性能越優，每組實例最佳結果用粗體標出。本文所提出算法在ARD值方面的性能明顯優于其他4 種算法，僅在第8 組實例中平均ARD值與GILS 算法相等，在第3 組、第9 組和第13 組中得到最小TF值運行時間略大于GILS 算法，其余測試問題中都表現最好；GILS 算法表現僅次于所提出的算法，CMA 算法在5 種算法中表現最差。根據表2 中數據結果對比，繪制如圖6 所示各算法類型的95% 置信區間，可以看出本文所提出的算法與CMA、HBBO、HDIWO 和GILS 有顯著差異。

為了更詳細地分析特征之間的關系，圖7～9 分別繪制了算法類型與m、f和s之間的95%置信水平顯著差異的交互圖。從圖5 中可以清楚地看到，當機器數較小時，各種算法的ARD 表現得更好。從圖7～8 可知，工廠和產品的數量越多，這3 個因素對IIGA 的影響小于其他4 種算法，實驗結果更優。

圖7 算法類型與m 置信區間交互關系

綜上，本文通過提出一種IIGA 解決DAPFSP問題，且在上述測試問題中取得較好的結果。實現了協調各個不同工廠的任務分配，進行合理的資源能力配置，有效降低了分布式車間調度中企業的生產成本。為解決新型DAPFSP 提供了一種新的途徑和方法。

圖8 算法類型與f 置信區間交互關系

圖9 算法類型與s 置信區間交互關系

4 結語

本文針對分布式裝配置換流水車間調度問題，建立基于改進的迭代貪婪算法的分布式裝配置換流水車間調度模型。針對傳統IG 的缺點，提出一種新的初始化方法，提升初始解的質量；設計了一種新的破壞重構過程，同時考慮工廠之間和工廠內的分配規則，擴大了搜索空間，提高了種群的多樣性；最后，通過180 個不同規模的仿真實例進行比較，驗證了本文提出的改進的迭代貪婪算法求解DAPFSP問題的有效性。本文所提出算法還具有一定的局限性，如改進的迭代貪婪算法在初始化階段只生成一組解，會導致種群中的個體之間高度相似，不利于后續的搜索和優化，且初始化時間過高，今后可以從該方面做深入研究。