基于IIGA 的分布式裝配置換流水車間調(diào)度＊

董 海 王志彬

（①沈陽大學(xué)應(yīng)用技術(shù)學(xué)院，遼寧 沈陽 110000；②沈陽大學(xué)機械工程學(xué)院，遼寧 沈陽 110000）

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

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

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

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

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

1.1 問題模型

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

圖1 分布式裝配置換流水車間調(diào)度

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

根據(jù)上述問題描述并參考文獻(xiàn)[12]建立TF 數(shù)學(xué)模型及其相關(guān)約束條件

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

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

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

圖2 兩個階段的調(diào)度甘特圖示例

表1 產(chǎn)品的處理時間和關(guān)系

2 迭代貪婪算法

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

2.1 解的表示

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

2.2 基于CDS 和NEH 的啟發(fā)式算法

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

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

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

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

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

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

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

圖3 初始解對比圖

2.3 本地搜索

對于組合優(yōu)化問題，每個最優(yōu)解都是所有鄰域結(jié)構(gòu)下的局部最優(yōu)解，本文基于傳統(tǒng)IG 算法提供了兩種本地搜索過程，一個用于產(chǎn)品，另一個用于作業(yè)。

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

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

2.4 破壞與重構(gòu)階段

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

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

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

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

圖4 破壞重構(gòu)操作示意圖

2.5 選擇和接受準(zhǔn)則

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

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

2.6 算法流程

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

圖5 改進(jìn)IG 算法流程圖

3 仿真實驗

3.1 實驗設(shè)置

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

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

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

3.2 參數(shù)設(shè)置

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

3.3 算法比較

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

表2 各算法ARD 結(jié)果對比

圖6 對比算法95%置信區(qū)間

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

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

圖7 算法類型與m 置信區(qū)間交互關(guān)系

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

圖8 算法類型與f 置信區(qū)間交互關(guān)系

圖9 算法類型與s 置信區(qū)間交互關(guān)系

4 結(jié)語

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