朱傳軍，劉明英

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

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

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

1 混合整數(shù)規(guī)劃模型

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

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

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

下標(biāo)與集合：i,i′為工件下標(biāo)；j,j′為工序下標(biāo)；k,k′為機(jī)器下標(biāo)；Oi為工件i的所有工序集合。

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

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

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

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

(1)

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

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

(2)

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

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)

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

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)

數(shù)學(xué)規(guī)劃方法只能用于求解小規(guī)模開放車間調(diào)度問題，其本質(zhì)是一種非多項式時間算法。當(dāng)問題規(guī)模增加時，數(shù)學(xué)規(guī)劃方法的計算復(fù)雜度會爆炸式增加，導(dǎo)致計算時間變得很長，因此采用改進(jìn)遺傳算法來進(jìn)行求解。

2 改進(jìn)遺傳算法及其實現(xiàn)

本文將遺傳算法應(yīng)用于開放車間調(diào)度問題中，設(shè)計相應(yīng)的編碼方案及算法操作流程。

2.1 編碼與解碼

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

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

圖1 個體編碼方案

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

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

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

2.2 工序先后順序處理方法

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

圖2 一個隨機(jī)生成的個體

2.3 選擇操作

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

賭輪盤選擇法模擬博彩游戲中的輪盤賭。假設(shè)群體P(i)中有N個個體；一個輪盤也被劃分為N個扇形，每個扇形代表一個個體且個體越好、優(yōu)勢越大(通常適應(yīng)度值越大)扇形的面積越大。這樣，轉(zhuǎn)動輪盤，指針?biāo)傅纳刃螀^(qū)域所代表的個體就會被選中。因為扇形面積與個體適應(yīng)度的大小呈正比，因此適應(yīng)度越好的個體越有可能被選中。

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

2.4 交叉操作

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

圖3 交叉操作示意

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

本文提出的交叉操作通過對選定若干個工件的工序進(jìn)行保留，并使用另一父代個體的工序?qū)ψ哟鷤€體中空余基因位進(jìn)行填充，確保了兩個父代個體的基因的深度融合，從而產(chǎn)生更優(yōu)秀的個體。

2.5 變異操作

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

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

圖4 變異操作

2.6 算法的改進(jìn)

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

2.7 算法流程

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

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

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

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

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

步驟5 對所有新一代個體計算適應(yīng)度，并更新全局最優(yōu)解。

步驟6 判斷是否達(dá)到算法停止條件，若不滿足轉(zhuǎn)到步驟2進(jìn)行下一輪迭代；若滿足則輸出結(jié)果。

3 實驗結(jié)果與分析

3.1 民航客機(jī)保障與維護(hù)調(diào)度問題

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

表1 第一個實例的數(shù)據(jù) min

表2 第二個實例的數(shù)據(jù) min

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

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

3.3 遺傳算法計算結(jié)果與分析

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

表4 遺傳算法計算結(jié)果 min

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

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

圖6是實例3最優(yōu)解對應(yīng)的甘特圖，最優(yōu)最大工期為305 min。機(jī)器1處理的第一個工序為4.2，是第四個工件的第2個工序，其加工時長為63 min。對照表3.3可知，該工序為飛機(jī)4維護(hù)的第1個工序。由于開放車間中同一工件的各個工序先后處理順序沒有要求，本例工序4.2實質(zhì)為工件4的第1個工序，這是允許的。圖6的甘特圖中所有工序?qū)?yīng)的實際工序號、對應(yīng)加工機(jī)器與加工時間列于表5中。不難發(fā)現(xiàn)，各個工序的實際加工時間均符合表3中相應(yīng)數(shù)據(jù)，說明該調(diào)度方案是合理的。

表3 第三個實例的數(shù)據(jù) min

圖6 實例3的最優(yōu)甘特圖

表5 圖6機(jī)器上各工序詳細(xì)信息

4 結(jié)論

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