改進遺傳變鄰域算法求解飛機裝配線調(diào)度問題

蔡 瑋，趙 軼，陳浩杰，張 劍

（1.西南交通大學(xué) 先進設(shè)計與制造技術(shù)研究所；2.成都飛機工業(yè)（集團）有限責(zé)任公司成都，610000）

0 引言

飛機裝配具有作業(yè)數(shù)量大、裝配關(guān)系復(fù)雜等特點，且駕駛艙等部段區(qū)域可容納資源的空間有限，所以飛機裝配線作業(yè)調(diào)度問題可看作是一類具有特殊空間約束的資源受限項目調(diào)度問題[1]（Resource Constrained Project Scheduling Problem，RCPSP），該類問題已被證明為一類復(fù)雜的強NP-hard問題[2]，針對不同約束和目標的RCPSP建模及求解技術(shù)，國內(nèi)外學(xué)者展開了大量的研究。

建模中，Elmaghraby和Kamburowski[3]對活動緊前緊后約束進行了歸納并提出了相應(yīng)的建模方法，Slowinski[4]則從資源約束的角度對RCPSP建模，楊紅光[5]等對雙邊裝配線模型進行了研究，曹陽華[6]等考慮了U型裝配線的生產(chǎn)效率模型并對該問題進行了求解，孫寶鳳[7]等建立了混流裝配線的雙目標投產(chǎn)排序模型。從求解角度來看，解決RCPSP及其擴展問題的算法可分為三大類：精確算法、啟發(fā)式算法和元啟發(fā)式算法（智能算法），其中精確算法雖然能得到理論最優(yōu)解，但僅適用于小規(guī)模求解，由此近似算法開始被應(yīng)用于求解大規(guī)模RCPSP問題[8]。自1963年，Kelley[9]提出了調(diào)度生成方案后，在此基礎(chǔ)之上各種啟發(fā)式算法相繼被提出，但其不具備優(yōu)化能力，往往受到問題本身的影響而得不到滿意解。元啟發(fā)式算法和智能算法的應(yīng)用使問題的求解得到了新的發(fā)展，如喻小光[10]等引入局部搜索中的模擬退火算法（Simulated Annealing，SA）來求解RCPSP，進化算法（如遺傳算法[11]，Genetic Algorithm，GA）和群體智能算法（如蟻群優(yōu)化算法[12]，Ant Colony Optimization，ACO）都在求解RCPSP問題上得到了廣泛的應(yīng)用。

飛機裝配線調(diào)度問題屬于傳統(tǒng)RCPSP的擴展問題，其中作業(yè)活動除了受到緊前緊后約束和資源的約束外，在飛機的某些部段，眾多滿足資源的并行活動，常因空間的限制而無法同時進行，從而增加了問題空間和計算求解的復(fù)雜度。本文綜合考慮作業(yè)活動緊前緊后、資源約束和空間約束，以最小化裝配總工期為目標，建立了飛機裝配線作業(yè)調(diào)度的數(shù)學(xué)模型，并針對遺傳算法容易過早收斂的缺陷，提出了一種改進的遺傳變鄰域算法（Improved Genetic Algorithm Variable Neighborhood Search，IGA-VNS）用以求解模型。該算法采用RCPSP中兩種較優(yōu)的啟發(fā)式規(guī)則，即最晚開工時間最?。‥DDF）和最晚完工時間最?。∕INLFT）[13]進行初始化以改善初始種群，結(jié)合考慮接受閾值的變鄰域局部搜索來提高遺傳算法全局搜索能力，設(shè)計了交叉、變異策略和三種鄰域結(jié)構(gòu)以避免在算法搜索過程中產(chǎn)生非法解，通過PSPLIB中的標準算例驗證了算法的有效性。

1 問題描述及數(shù)學(xué)模型構(gòu)建

1.1 問題描述

飛機裝配過程是指飛機進入裝配線到裝配完成的一系列裝配與測試活動，其調(diào)度問題可描述如下。一項飛機裝配作業(yè)項目由活動集合J（J={0，1，2，…，n+1}）組成，其中活動0和n+1為虛活動，僅代表項目的開始和結(jié)束，不占用時間和資源?；顒觠（j∈J）的緊前作業(yè)集合用Pj表示，j的緊后作業(yè)集合用Sj表示。tj表示活動j的持續(xù)時間，sj表示活動j的作業(yè)開始時間。一項裝配作業(yè)項目中的活動分屬于飛機的不同部段，定義M為部段集合，M={1，2，…，z}，m∈M為部段號，Cm表示在部段m中的活動集合，ej表示作業(yè)活動j的空間占用量，各部段的最大空間容量為Nm。R（R={r1，r2，…，rq，…，rk}）表示裝配過程中的k種資源集合，用rjq表示活動j對第q種資源單位時間的需求量，bq為資源q單位時間的最大供應(yīng)量。對時間進行離散化處理，d={1，2，…，T}為離散的時間節(jié)點，T表示裝配作業(yè)總工期，Ad={j|stj＜d stj+tj}為d時刻正在執(zhí)行的作業(yè)活動集合。

1.2 數(shù)學(xué)模型構(gòu)建

其中：式(1)為目標函數(shù)，即最小化裝配作業(yè)總工期；式(2)為決策變量；式(3)表示每項作業(yè)活動必須在其規(guī)定持續(xù)時間完成；式(4)表示活動j一旦開始則在完成之前不能中斷；式(5)和(6)表示虛活動0和n+1的持續(xù)時間和資源需求量都為0；式(7)為活動緊前緊后約束，活動j必須在其全部緊前活動完成后才能開始；式(8)為資源約束，d時刻正在執(zhí)行的所有活動對某種資源的需求量不大于該資源單位時間的最大供應(yīng)量；式(9)為各部段的空間約束，d時刻在部段m中正在執(zhí)行的所有活動對空間的需求量不大于部段m的最大空間容量。

2 遺傳變鄰域算法設(shè)計

2.1 遺傳變鄰域算法策略及流程

由于遺傳算法存在容易陷入局部最優(yōu)的缺陷，本文設(shè)計了一種結(jié)合接受閾值的變鄰域算法進行局部搜索，并設(shè)計交叉、變異策略和三種產(chǎn)生合法解的鄰域結(jié)構(gòu)以確保算法的進行和提高搜索能力，其主要算法步驟如下：

步驟1：參數(shù)設(shè)置。設(shè)最大代次數(shù)為maxGen；種群規(guī)模為popSize；交叉概率為Pc；變異概率為Pm。

步驟2：種群初始化。采用整數(shù)編碼的方式產(chǎn)生popSize個染色體，并采用優(yōu)先級規(guī)則對部分個體進行初始化。

步驟3：計算個體適應(yīng)度值，并判斷當(dāng)前迭代次數(shù)gen是否達到最大迭代次數(shù)maxGen，若達到最大迭代次數(shù)則輸出最優(yōu)解；否則轉(zhuǎn)步驟4。

步驟4：選擇。采用錦標賽選擇的策略從初始種群中選擇部分個體。

步驟5：交叉。根據(jù)交叉概率Pc采用一種考慮緊前緊后的交叉策略對選擇過后的染色體隨機進行交叉操作。

步驟6：變異。根據(jù)變異概率Pm采用一種右移變異的策略對選中的個體進行變異操作產(chǎn)生新的種群newPop。

步驟7：變鄰域操作。從newPop中選擇適應(yīng)度值前20%的個體作為變鄰域操作的初始解集S，變鄰域操作后生成局部最優(yōu)解集。

步驟8：將局部最優(yōu)解集重插入到原種群中，轉(zhuǎn)步驟3。

圖1 IGA-VNS算法流程

算法流程圖如圖1所示。

2.2 算法設(shè)計

1）編碼設(shè)計與種群的初始化

該方法采用整數(shù)編碼的方式進行編碼，考慮每個活動的緊前緊后關(guān)系，例如染色體A=（0，1，2，…，n+1）中共包含n+2個活動，其中0和n+1代表開始和結(jié)束的虛活動，1，2，…，n代表了活動的調(diào)度順序且滿足緊前緊后關(guān)系。由于考慮到求解目標為最小化項目工期，本文選擇兩種較優(yōu)的優(yōu)先級規(guī)則（EDDF和MINLFT）初始化部分個體，其余個體采用隨機初始化以提高初始種群的多樣性，采用優(yōu)先級規(guī)則進行初始化有效的提高了初始解的質(zhì)量，從而縮小解空間。

2）解碼設(shè)計

解碼則為將編碼基因轉(zhuǎn)化為一個可行的調(diào)度，由此在解碼過程中則需要考慮資源與空間約束的限制，即根據(jù)基因的順序以及每個基因?qū)?yīng)的活動對資源與空間的需求量，校驗以保證在活動持續(xù)時間內(nèi)每一時刻均滿足資源的供應(yīng)和空間限制，從而計算每項活動的開始時間和完工時間，而最后一項虛活動的開始時間即為裝配作業(yè)總工期。

3）適應(yīng)度函數(shù)設(shè)計

選用目標函數(shù)的倒數(shù)1/T乘以系數(shù)C作為適應(yīng)度函數(shù)，既Fitness=C/T（C為常常數(shù)），則適應(yīng)度函數(shù)值越大的個體在群體中其解越優(yōu)。

4）選擇

采用錦標賽選擇策略對個體進行選擇，每次從種群中隨機選擇一定數(shù)量的個體，根據(jù)其適應(yīng)度函數(shù)值選擇其中最優(yōu)的個體進入新種群，并重復(fù)此操作直至選擇出的新種群規(guī)模達到初始種群的90%。

5）交叉

在單點交叉的基礎(chǔ)上進行了改進，形成了考慮緊前緊后關(guān)系的交叉策略。從父代取兩個個體進行交叉，分別為M1和M2，取隨機整數(shù)m作為斷點，1≤m＜n，則可以得到兩個子代C1和C2。子代C1的活動序列中，i=1，…，m的部分來自于父代M1，而i=m+1，…，n的部分來自于父代M2，但在這部分序列中，已經(jīng)從父代M1中選擇的活動將不再被考慮，這樣的操作保證了父代中的活動優(yōu)先順序得以被保留且每個活動只出現(xiàn)一次，所產(chǎn)生的子代個體不會出現(xiàn)非法個體，子代C2的產(chǎn)生同理可得，便得到了兩個新的子代個體。按照交叉概率pc進行以上的交叉操作得到與原種群規(guī)模相同的新種群。

6）變異

以變異概率pm對遺傳算子的基因型做變動，采用了一種右移變異的策略，考慮某一個體的活動序列λ={1，2，…，i，…，n}，i為隨機選擇的活動，現(xiàn)將i所在位點右移到某一位置產(chǎn)生新一代個體，為了使新個體的活動序列仍然符合活動的優(yōu)先級循序而不產(chǎn)生非法解，在右移之前需要判斷該活動最小的可右移位置，即不破壞原有的緊后關(guān)系，而由于是將活動右移，所以其緊前活動仍然有效，從而得到新的個體λ’={1，…，i-1，i+1，…，h-1，i，h，…，n}，h所在位置即為i最小的可右移位置。以上的變異操作按照變異概率pm進行產(chǎn)生下一代的種群。

7）變鄰域搜索操作

變鄰域搜索的關(guān)鍵在于鄰域結(jié)構(gòu)的設(shè)計，但由于本問題中個體編碼受到活動間優(yōu)先級順序的約束，常用鄰域動作如插入、交叉等不適用于該問題的求解，會產(chǎn)生不滿足優(yōu)先級順序的非法解，對非法解進行修正不僅增加了算法的復(fù)雜程度，而且影響運行效率。本方法借鑒之前所述的變異操作中右移變異的策略，設(shè)計了3種不會產(chǎn)生非法解的鄰域結(jié)構(gòu)，具體如下：

隨機選擇個體基因中的某一位點，根據(jù)活動的緊前緊后關(guān)系，記錄該位點上對應(yīng)活動的所有緊前活動在該項目列表中最大的下標位置，及該活動的所有緊后活動在該項目列表中最小的下標位置。1）將該基因右移插入到緊后活動最小下標位置前一位，構(gòu)成第一種鄰域結(jié)構(gòu)；2）將該基因左移插入到緊前活動最大下標位置后一位，構(gòu)成第二種鄰域結(jié)構(gòu)；3）將該基因隨機插入到最小下標位置與最大下標位置之間，構(gòu)成第三種鄰域結(jié)構(gòu)。

三種鄰域結(jié)構(gòu)具體示例如圖2所示。在染色體F中隨機選擇基因位點G，G對應(yīng)活動5的所有緊前活動中最大的下標位置為G1，其所有緊后活動中最大的下標位置為G2，則鄰域結(jié)構(gòu)1將活動5插入到P1位置得到新個體F1，鄰域結(jié)構(gòu)2將活動5插入到P2位置得到新個體F2，鄰域結(jié)構(gòu)3將活動5隨機插入到P1和P2的中間位置P3或P4，得到新個體F3或F3’。

圖2 鄰域操作示例

除了鄰域結(jié)構(gòu)的設(shè)計，考慮到鄰域搜索這種基于精英保留的策略仍然有陷入局部最優(yōu)的風(fēng)險，提出一種接受閾值的計算方法，即在接受閾值內(nèi)考慮是否接受變鄰域搜索得到的最優(yōu)解，設(shè)變鄰域搜索的初始解為s，目標函數(shù)值為f（s），經(jīng)過鄰域搜索后得到的新解為s’，目標函數(shù)值為f（s’）。當(dāng)?shù)玫降男陆鈨?yōu)于初始解，即f（s’）-f（s）＜0時，以概率p=1接受新解，令s=s’進入下一步迭代；當(dāng)?shù)玫降男陆饬优c初始解時，即f（s’）-f（s）＞0時，以概率p=exp{-[f（s’）-f（s）]/f（s）}接受劣解，令s=s’進入下一步迭代。

3 數(shù)值實驗設(shè)計與結(jié)果分析

3.1 實驗設(shè)計

為驗證本文提出算法的可行性與有效性，采用標準算例庫PSPLIB中的算例進行，即分別在活動數(shù)量為30、60、90的3種工況下隨機選取5組初始輸入數(shù)據(jù)。每種規(guī)模下的作業(yè)項目共享4種資源，每種資源設(shè)有單位時間最大的供應(yīng)量，每項活動需要到一種或多種資源。隨機選擇某一種資源作為空間需求量，對于每種工況隨機生成部段數(shù)[1，z]，并將活動隨機分配到各部段中，部段的最大空間容量Nm為在該部段執(zhí)行的活動中對空間需求量的最大值與作為空間需求量的資源的單位時間最大供應(yīng)量之間的隨機整數(shù)。通過Matlab2014b平臺進行數(shù)值實驗，采用IGA-VNS與傳統(tǒng)遺傳算法（GA），變鄰域算法（VNS）和遺傳模擬退火算法（GASA）進行對比，在每種工況下運算5次，得到的實驗結(jié)果如表1所示，其中Duration表示裝配總工期的均值，GAP為差值百分比。

式(5)中，T1為其他算法得到的總工期均值，T2為IGA-VNS算法的到的總工期均值。

3.2 結(jié)果分析

數(shù)值實驗結(jié)果如表1和圖3所示。實驗結(jié)果表明，在不同作業(yè)規(guī)模下，基于IGA-VNS算法求解的飛機裝配線調(diào)度問題的結(jié)果均優(yōu)于其他三種算法，在活動數(shù)量為30的規(guī)模下，IGA-VNS比其他算法的目標值在精度上平均提高4.69%。當(dāng)活動規(guī)模增大后，IGA-VNS的優(yōu)勢也不斷擴大，在活動數(shù)量為60的規(guī)模下，IGA-VNS與其他算法的目標值在精度上平均提高4.89%，在活動數(shù)量為90的規(guī)模下，IGA-VNS比其他算法的目標值在精度上平均提高9.84%。且IGA-VNS較GA與VNS的求解能力具有明顯優(yōu)勢，對于同樣具有全局與局部搜索能力的GASA也有一定的優(yōu)勢。

5 結(jié)語

本文考慮飛機裝配線受到空間限制的實際工程背景，同時考慮活動緊前緊后關(guān)系、資源約束與空間限制，建立了以最小化裝配作業(yè)總工期為目標函數(shù)的飛機裝配線作業(yè)調(diào)度數(shù)學(xué)模型，并設(shè)計了一種改進的遺傳變鄰域算法對該問題進行求解。數(shù)據(jù)實驗表明，本文中所提出的算法比其他三種智能算法的求解結(jié)果更加優(yōu)異，且隨著規(guī)模的增加其優(yōu)勢更加明顯，由此說明了該算法的有效性。為了更貼近飛機裝配線實際調(diào)度，下一步將考慮將此算法應(yīng)用至多工程項目調(diào)度問題和考慮資源和人員的動態(tài)變化所帶來的影響。

表1 3種規(guī)模下的實驗結(jié)果

圖3 不同算法完工時間比較