基于改進遺傳算法的民航客機地勤調度問題

朱傳軍，劉明英

(1 湖北工業大學 機械工程學院，湖北 武漢 430068；2 鶴壁技師學院，河南 鶴壁 458030)

民航客機的地勤保障可以看作是一個開放車間調度問題，如何安排保障順序歸結為如何得到一個最優的調度方案以減少等待時間并提高保障效率。開放車間調度問題是NP-hard，精確算法僅適用于有限的幾類問題。當機器數量小于3臺時，T. Gonzalez等[1]設計了多項式時間算法，使其能在多項式時間內得到最優值。其他精確算法中，非多項式時間算法還有分支定界法和數學規劃等方法。Brucker等設計了基于析取圖的分支定界算法[2]。由于非多項式時間算法的缺點，學者們提出了啟發式算法來求解開放車間調度問題。陳亞絨等針對晶粒分類揀選這一并行多機開放車間調度問題，提出了混合整數規劃模型，設計了同時考慮質量與求解效率的啟發式算法[3]。針對單一機器干擾下的開放車間重調度問題，劉樂等提出了基于右移、受影響工序和全局重調度方法，實現了開放車間高效率、低成本重調度[4]。國外，Brasel等提出了基于構造插入的高效啟發式算法[5]。Gueret和Prins提出了基于列表的啟發式方法求解開放車間問題[6]。

在求解開放車間調度問題中，真正具有重要意義的是元啟發式算法，而遺傳算法是最基本的元啟發式算法。Liaw和Prins分別使用遺傳算法求解了開放車間調度問題[7-8]。Blum結合蟻群算法和束搜索(Beam Search)算法，提出了一種混合算法[9]。王艷鵬將傳統粒子群算法離散化，提出的一種適合于求解開放車間調度優化的離散粒子群算法并取得了較優結果[10]。高亮等為克服粒子群算法在信息共享機制上的缺陷，基于群體智能的信息共享機制，引入了問題的領域知識為導向的局部搜索，得到了開放車間調度問題的高質量解[11]。Sha和Hsu也使用改進的離散粒子群算法，并結合束搜索及主動調度方法對開放車間調度問題進行了優化，得到了許多未求解問題的最優解[12]。王軍強等人基于多樣性增強的自適應遺傳算法[13]，設計了多種算子以提高算法的進化效率和質量，并驗證了算法的有效性和穩定性。此外，不同學者也在嘗試使用新穎的元啟發式算法，以期獲得更好的優化效果。例如，陳祥等使用了文化基因算法對開放車間標準問題進行了優化[14]。Hosseinabadi等評估了求解開放車間調度問題中交叉、變異等遺傳算子的效果，證實遺傳算法求解開放車間問題時選擇算子作用很大，并提出了更好的EGA_OS算法[15]。本文針對民航地勤調度問題的特點，建立了混合整數規劃模型，設計相應的編碼與解碼方案及相應的算子，使用遺傳算法對該問題進行優化。

1 混合整數規劃模型

有n個工件J1,J2,…,Jn需要在m臺機器M1，M2，…，Mm上加工，每個工件有m個工序Oij，且每個工序均有固定的加工時長tij。所有工件在零時刻均可開始加工，一個工件的各工序之間沒有先后關系且各工序經過的機器也沒有規定，但任意工序所使用的設備是事先確定的。此外，為研究問題方便，還有下列假設：1)各工序一經在某設備上開始加工就不能中斷，直至加工完畢；2)一個工件的任一工序只能由一臺機器加工，不能由多臺機器同時加工；3)每臺機器每次只能加工一個工件。

在滿足上述要求下為各臺機器合理安排工件及其開工時間，使最大完工時間最小。

混合整數規劃模型用于從數學角度描述開放車間調度問題。對于開放車間調度問題，在建立數學模型時，必須考慮兩個問題：1)機器上的工序排序；2)同一工件的工序排序。根據這兩點合理安排工序即可得到一個正確的模型。在建模前，先建立如下的集合、參數、變量。

下標與集合：i,i′為工件下標；j,j′為工序下標；k,k′為機器下標；Oi為工件i的所有工序集合。

參數：tij為工序Oij的加工時長；Eijk=1，表示工序Oij在機器k上加工，否則Eijk=0；n為工件個數；m為機器臺數；A為一個很大的正數。

變量：Cij為工序Oij的完工時間；Cmax為所有工件的最大完工時間，makespan；Xij,j′=1，表示工序Oij直接或間接地在工序Oij′前加工，否則Xij,j′=0；Ykij,i′,j′=1，表示機器k上工序Oij直接或間接地先于工序Oi′j′加工，否則Ykij,i′,j′=0。

目標與約束：對于同一工件的各個工序，若兩兩之間的加工先后關系得到確定，則各工序間的加工先后也得到確定。約束(1)用于確定各工序間的先后關系。

Xij,j′+Xij′j=1
?i=1,2,3,…,n,?j,j′∈Oi,j≠j′

(1)

對于屬于同一工件的各工序，其開工時間需要滿足一定的先后關系。

Cij≥Cij′+tij-A·Xij,j′?i=1,2,3,…,n,
?j,j′∈Oi,j≠j′

(2)

對于同一機器上加工的各個工序，也需要確定其先后順序，否則會出現一臺機器同時加工多個工序的情況。類似上述方法，需要先確定任意兩個工序間的先后加工關系：

Ykiji′j′+Yki′j′ij-A·(2-Eijk-Ei′j′k)≤1，
?k=1,2,3,…,m,?i,i′=1,2,3,…,n,
?j∈Oi,?j′∈Oi′

(3)

Ykiji′j′+Yki′j′ij+A·(2-Eijk-Ei′j′k)≥1，
?k=1,2,3,…,m,?i,i′=1,2,3,…,n,
?j∈Oi,?j′∈Oi′

(4)

這樣，就可以安排同一機器上不同工序開工的先后順序。如約束(5)所示，后一個工序的完工時間大于等于前一工序完工時間加上本道工序的加工時長。若兩個工序不在同一機器上或先后順序不滿足，則該約束不起作用。

Cij≥Ci′j′+tij-A·(3-Eijk-Ei′j′k-Yki′j′ij),
k=1,2,3,…,m,?i,i′=1,2,3,…,n,
j∈Oi,?j′∈Oi′

(5)

最后，所有工序的最大完工時間即為makespan：

Cmax≥Cij,?i=1,2,3,…,n,?j∈Oi

(6)

數學規劃方法只能用于求解小規模開放車間調度問題，其本質是一種非多項式時間算法。當問題規模增加時，數學規劃方法的計算復雜度會爆炸式增加，導致計算時間變得很長，因此采用改進遺傳算法來進行求解。

2 改進遺傳算法及其實現

本文將遺傳算法應用于開放車間調度問題中，設計相應的編碼方案及算法操作流程。

2.1 編碼與解碼

開放車間問題是一種特殊的作業車間問題，而針對作業車間問題的遺傳算法目前已經有較好的編碼方案——基于工序的編碼。因此，本文將借鑒已有的編碼方案對其進行適當的改進或擴展，以適應開放車間調度優化。用遺傳算法求解作業車間調度問題的編碼方案有兩類：直接編碼和間接編碼。直接編碼對個體解碼可直接得到相應的調度方案；例如：基于工序的編碼、基于工件的編碼等。而間接編碼著眼于工件在機器與時間上的分配規則，再由這些規則得到調度方案。上述兩種編碼方案中，兩者各有優劣。目前最常用的是直接編碼方案是基于工序的編碼。因此，本文采用基于工序的編碼方式。假設某開放車間調度問題含有n個工件且每個工件含有m道工序；每個工序只能在一臺機器上加工(總共m臺機器)，需要確定一個調度方案使總完工時間最短。根據基于工序的編碼方案可知，所有工序可以用一個編碼串來表示；每個工件號在編碼串中總共出現m次，因此編碼串(染色體)長度為n×m，其中每個位置代表一個工序。每個工件號必會恰好出現m次。按照從左向右順序依次讀取染色體中各個位置上的數字，若某位置數字i正好第j次出現，表示這是工件i的第j道工序。因此，每個工件的每個位置都能確保被找到。圖1給了一個基于工序編碼的開放車間調度遺傳算法編碼例子。假設有3個工件3臺機器且每個工件各有3個工序，一個編碼方案為[3,2,2,1,3,1,3,1,2]。

每個個體含有一條染色體，每條染色體有n×m個基因，每個基因上有一個基因位，每個基因代表一個工序；整條染色體表示示例中3個工件共含有所有工序。圖1中染色體代表工件ID的數字1,2,3均出現3次，即為各個工件均有3個工序。根據基于工序的編碼規則，染色體第一個位置是數字3，且該數字3第一次出現，表示第一個要處理的工序為第三個工件的第一個工序。以此類推，在染色體第6個位置是數字1，且該數字第二次出現，表示第6個處理的工序為工件1的第二個工序。最終得到的工序處理順序在圖1第二行給出。顯然，任意交換或打亂各個工序的順序并不會產生錯誤或非法解。因此，在初始化過程中隨機生成的個體均是正確的染色體(合法的編碼)。

圖1 個體編碼方案

從圖1知，一個個體中除了工序串外還有2個串，即機器串和時間串，分別表示對應的工序在哪一臺機器上加工及相應的加工時間。例如第一個處理的工序為3.1，該工序需要在機器1上加工且對應的加工時長為2。這樣通過合理的編碼一個個體可以將所有工件信息及調度要素表達出來。

解碼過程與編碼相反，解碼是利用一個個體內各個串的信息通過合理的方法與步驟或通過某種映射關系將其轉化為相應的調度的過程。目前對于車間調度問題存在多種解碼方法，且解碼過程并不是編碼的逆推，但編碼方法的優劣會影響解碼的效率與質量。一般來說，解碼過程要比編碼過程更加復雜。即使對同一個體使用不同的解碼方法，得到的調度方案可能會完全不同。

在車間調度問題中，常用的解碼方法即為三類：半主動調度、主動調度及無延遲調度。三種解碼方法的共同目的是在工序加工順序、使用的機器、對應的加工時間給定的前提下為每臺機器上的工序確定一個合理的開工順序，在滿足同一工件各工序加工順序合理的約束下使得總完工時間最小(或其他技術指標最優)。在一般情況下使用主動調度解碼方法可以得到更好的調度方案，同時也可提高機器利用率。本文給出的算法使用主動調度的解碼方法。

2.2 工序先后順序處理方法

在傳統作業車間調度優化中，各個工序的先后關系是事先給定的且任何時刻不能改變。對于開放車間調度問題，各工序間沒有先后關系。因此，本文所有算法中對于初始個體其工序的排列均為隨機生成。對于上一節提出的編碼方案，可以采用隨機打亂工序編碼串上的各個基因(連同的機器上加工時間也要調整)的方法實現。例如，對于圖1所示的例子，另一個允許的個體可以是如圖2所示的隨機生成個體。

圖2 一個隨機生成的個體

2.3 選擇操作

在遺傳算法中，新的個體組成了下一代群體；新個體的產生常常通過算法中任選兩個父代個體經由選擇操作、交叉操作和變異操作得到。其中，選擇操作是其中的第一步，其目的是以較大的概率將父代具有優勢的個體保留下來，父代個體對環境的適應能力越強、優勢越大其被保留的概率也越大。選擇操作主要有兩種：賭輪盤選擇法和錦標賽選擇法。

賭輪盤選擇法模擬博彩游戲中的輪盤賭。假設群體P(i)中有N個個體；一個輪盤也被劃分為N個扇形，每個扇形代表一個個體且個體越好、優勢越大(通常適應度值越大)扇形的面積越大。這樣，轉動輪盤，指針所指的扇形區域所代表的個體就會被選中。因為扇形面積與個體適應度的大小呈正比，因此適應度越好的個體越有可能被選中。

錦標賽選擇操作每次從群體P(i)中選取若干個體(一般是兩個)，每個個體被選中的概率相同。比較選出的各個個體的適應度，選取適應度較好的個體進入下一代。重復上述過程直到N個個體全部選出。相對賭輪盤選擇，錦標賽選擇方法操作比較簡單，無需復雜的轉換亦能保持下一代個體中解的多樣性。因此，本文采用錦標賽選擇法。

2.4 交叉操作

基于提出的編碼方式，設計了一種交叉操作。如圖3所示，任意選取經選擇操作后的兩個優秀父代個體；隨機在工件[1,2,3,…,N]中確定s個工件(1≤s

圖3 交叉操作示意

圖3是兩個父代個體交叉操作的例子，共有3個工件且工件2被選中。P1中屬于工件2的工序在2,3,9三個位置，P2中屬于工件2的工序在4,8,9三個位置。將這些位置表示工序、機器、加工時間的基因各復制一份，分別填充到子代個體O1、O2的相應位置上。圖中工件2有3個工序復制后分別放入O1、O2對應的位置(虛線框所示)。此時，O1、O2各有6個位置沒有填滿，同時P1、P2中工件1和3的6個工序也未處理。個體P2中剩余6個工序連同機器與相應的加工時間按照原來的順序331113復制一份后填入到個體O1的空余基因位中.這樣，子代O1中除虛線框中的工序外，其余工序的順序也是331113。同理可得個體O2。

本文提出的交叉操作通過對選定若干個工件的工序進行保留，并使用另一父代個體的工序對子代個體中空余基因位進行填充，確保了兩個父代個體的基因的深度融合，從而產生更優秀的個體。

2.5 變異操作

變異操作是遺傳算法中獨有的操作，用于模擬個體基因突變這一過程。在交叉操作中，新生成的子代群體由于繼承了父代的優秀基因，其總體性能優于父代群體。與交叉操作不同，變異操作沒有方向性，即一個個體經過變異后，與之前相比，可能變得更好但也可能變得更差。因此，為了充分發掘個體的潛力，獲得某些變異后表現更優的個體，算法中引入了變異操作。此外，相對交叉操作而言，變異操作發生的概率較低，這是變異操作的又一個特點。

如圖4所示，變異操作中首先隨機選擇兩個不同的基因位(第3、第6位)，將兩個位置代表的工序、機器及加工時間同時進行交換，交換后得到新的個體。如前所述，對于提出的編碼方案，任意交換兩個位置代表的工序、機器及加工時間不會影響解碼過程。

圖4 變異操作

2.6 算法的改進

傳統遺傳算法在每一代個體更新過程中沒有新的個體引入，這會導致在算法迭代后期各個個體內部基因高度相似，由此降低了交叉操作的效果，使得最優解停滯于當前值，而沒有新的最優解產生。這是由于群體多樣性受到了制約，無法通過遺傳操作得到更優秀的基因片段，產生更優的解。為克服這一不利因素，本文對傳統遺傳算法進行適當創新，改進了已有的選擇方法，即在每次迭代中留出少量的個體數，并用新生成的個體覆蓋老的個體。這樣，每次迭代中個體的多樣性得到了保證。

2.7 算法流程

本文算法流程總體的步驟與常規遺傳算法一致，都是通過選擇、交叉、變異從而完成一次迭代。

步驟1 確定算法的相關參數(個體數、交叉概率、變異概率等)并對個體進行初始化，即隨機生成個體。

步驟2 選擇操作：從當前群體P(i)中隨機選擇兩個個體，比較兩個個體的適應度值，選擇適應度較好的個體作為下一代個體的父代。

步驟3 交叉操作：隨機選取兩個父代個體，隨機生成區間[0, 1]內的有理數R，若R不大于給定的交叉概率，則進行交叉操作；否則放棄交叉操作。

步驟4 變異操作：隨機選取一個交叉后的個體，隨機生成區間[0, 1]內的有理數r，若r不大于給定的變異概率，則進行變異操作；否則放棄變異操作。

步驟5 對所有新一代個體計算適應度，并更新全局最優解。

步驟6 判斷是否達到算法停止條件，若不滿足轉到步驟2進行下一輪迭代；若滿足則輸出結果。

3 實驗結果與分析

3.1 民航客機保障與維護調度問題

計算實例來自民航客機的保障優化問題。根據保障類型及飛機種類的不同，表1～3給出了3組調度實例及相應的保障時間。實例1中有6架飛機需要維護，代表了中等規模的開放車間調度實例；實例2中有8架飛機規模較大；實例3中只有4架飛機，是一個小規模實例。對于維護時長，實例1和實例2的時長相差不大；實例3的維護時長較長。本文采用改進遺傳算法求解上述三個實例。

表1 第一個實例的數據 min

表2 第二個實例的數據 min

3.2 參數設置

遺傳算法采用C++語言編程并在Visual Studio 2010軟件上運行。為避免單次計算中算法所得結果的不確定性及偶然性，每個實例計算5次。此外，在預先多次測試的基礎上，選擇以下參數：群體中個體數400，迭代次數為400次，交叉概率0.7，變異概率0.05，每輪迭代后有10%的個體為新生成的個體。

3.3 遺傳算法計算結果與分析

實例1～3的計算結果列于表4中。第一個實例的最優解為266 min，且5次計算中均得到了最大工期為266 min。第二個實例工件個數較多，相應的最大工期較大為369 min。實例3雖然維護時間較長，但由于僅有4個工件，維護壓力較小且總完工時間較短。由表4可知，前兩個實例每次計算都能得到同一最大完工時間；而第三個實實例每次計算得到的結果略有差異，其最大完工時間均值為207 min，這是由于第三個實例各工序平均時長較長，最優調度方案稍有偏差即引起總完工時間較大的偏差。

表4 遺傳算法計算結果 min

圖5是求解實例1的收斂曲線?？梢钥吹?，開始時最大工期下降較快，這是由于初始時群體多樣性較好，即含有不同基因的個體較多，每個個體容易獲得優良基因。隨著迭代不斷進行，最優個體被保留，各個體中優秀的基因趨于一致，交叉后得到的個體中優秀基因與其父代相似度較高，此時算法對個體的改進有限，個體的改進幅度不斷變小，最大工期最終收斂于266 min。

圖5 遺傳算法求解實例1的收斂曲線

圖6是實例3最優解對應的甘特圖，最優最大工期為305 min。機器1處理的第一個工序為4.2，是第四個工件的第2個工序，其加工時長為63 min。對照表3.3可知，該工序為飛機4維護的第1個工序。由于開放車間中同一工件的各個工序先后處理順序沒有要求，本例工序4.2實質為工件4的第1個工序，這是允許的。圖6的甘特圖中所有工序對應的實際工序號、對應加工機器與加工時間列于表5中。不難發現，各個工序的實際加工時間均符合表3中相應數據，說明該調度方案是合理的。

表3 第三個實例的數據 min

圖6 實例3的最優甘特圖

表5 圖6機器上各工序詳細信息

4 結論

本文針對民航客機地勤保障調度問題的特性，建立了求解此類調度問題的混合整數規劃模型，兼顧求解效率與質量，設計了一種改進遺傳算法。根據生產實際設計了實驗算例，使用該算法成功求解了飛機保障調度這一典型的開放車間問題并對計算結果進行了分析。未來研究方向將側重于考慮更加實際的工程問題，如一個工序的加工時間并不是固定的，而是在一定范圍內波動或按照特定的概率分布的。此外，帶有工件輔助時間的開放車間調度問題的優化方法也可作為未來研究的方向。