基于改進(jìn)遺傳算法的民航客機(jī)地勤調(diào)度問題

朱傳軍，劉明英

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

民航客機(jī)的地勤保障可以看作是一個(gè)開放車間調(diào)度問題，如何安排保障順序歸結(jié)為如何得到一個(gè)最優(yōu)的調(diào)度方案以減少等待時(shí)間并提高保障效率。開放車間調(diào)度問題是NP-hard，精確算法僅適用于有限的幾類問題。當(dāng)機(jī)器數(shù)量小于3臺(tái)時(shí)，T. Gonzalez等[1]設(shè)計(jì)了多項(xiàng)式時(shí)間算法，使其能在多項(xiàng)式時(shí)間內(nèi)得到最優(yōu)值。其他精確算法中，非多項(xiàng)式時(shí)間算法還有分支定界法和數(shù)學(xué)規(guī)劃等方法。Brucker等設(shè)計(jì)了基于析取圖的分支定界算法[2]。由于非多項(xiàng)式時(shí)間算法的缺點(diǎn)，學(xué)者們提出了啟發(fā)式算法來求解開放車間調(diào)度問題。陳亞絨等針對(duì)晶粒分類揀選這一并行多機(jī)開放車間調(diào)度問題，提出了混合整數(shù)規(guī)劃模型，設(shè)計(jì)了同時(shí)考慮質(zhì)量與求解效率的啟發(fā)式算法[3]。針對(duì)單一機(jī)器干擾下的開放車間重調(diào)度問題，劉樂等提出了基于右移、受影響工序和全局重調(diào)度方法，實(shí)現(xiàn)了開放車間高效率、低成本重調(diào)度[4]。國(guó)外，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)域知識(shí)為導(dǎo)向的局部搜索，得到了開放車間調(diào)度問題的高質(zhì)量解[11]。Sha和Hsu也使用改進(jìn)的離散粒子群算法，并結(jié)合束搜索及主動(dòng)調(diào)度方法對(duì)開放車間調(diào)度問題進(jìn)行了優(yōu)化，得到了許多未求解問題的最優(yōu)解[12]。王軍強(qiáng)等人基于多樣性增強(qiáng)的自適應(yīng)遺傳算法[13]，設(shè)計(jì)了多種算子以提高算法的進(jìn)化效率和質(zhì)量，并驗(yàn)證了算法的有效性和穩(wěn)定性。此外，不同學(xué)者也在嘗試使用新穎的元啟發(fā)式算法，以期獲得更好的優(yōu)化效果。例如，陳祥等使用了文化基因算法對(duì)開放車間標(biāo)準(zhǔn)問題進(jìn)行了優(yōu)化[14]。Hosseinabadi等評(píng)估了求解開放車間調(diào)度問題中交叉、變異等遺傳算子的效果，證實(shí)遺傳算法求解開放車間問題時(shí)選擇算子作用很大，并提出了更好的EGA_OS算法[15]。本文針對(duì)民航地勤調(diào)度問題的特點(diǎn)，建立了混合整數(shù)規(guī)劃模型，設(shè)計(jì)相應(yīng)的編碼與解碼方案及相應(yīng)的算子，使用遺傳算法對(duì)該問題進(jìn)行優(yōu)化。

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

對(duì)于同一機(jī)器上加工的各個(gè)工序，也需要確定其先后順序，否則會(huì)出現(xiàn)一臺(tái)機(jī)器同時(shí)加工多個(gè)工序的情況。類似上述方法，需要先確定任意兩個(gè)工序間的先后加工關(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)所示，后一個(gè)工序的完工時(shí)間大于等于前一工序完工時(shí)間加上本道工序的加工時(shí)長(zhǎng)。若兩個(gè)工序不在同一機(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)

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

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

(6)

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

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

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

2.1 編碼與解碼

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

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

圖1 個(gè)體編碼方案

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

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

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

2.2 工序先后順序處理方法

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

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

2.3 選擇操作

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

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

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

2.4 交叉操作

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

圖3 交叉操作示意

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

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

2.5 變異操作

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

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

圖4 變異操作

2.6 算法的改進(jìn)

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

2.7 算法流程

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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