基于仿真優化的MRO調度問題研究

□ 丁金想，欒世超，石曉磊，連福詩

(中國航空綜合技術研究所，北京 100028)

1 引言

在航空產業鏈中，全球民用航空運輸市場的發展帶動了民用航空維修業(MRO)和民用航空制造業的發展，民用航空維修業的經濟價值越來越受到關注和青睞。從行業類型來看，MRO企業屬于服務行業，民航公司是其最大客戶群，與民航運輸業呈相互依存關系[1]。

對于MRO企業來說，除定期維修外，更多的維修工作存在不確定性，例如，飛機故障發生時間、原因、程度不可預測，導致維修的工作內容、時間和周期等無法按例行工作安排，因而MRO企業面臨諸多不確定因素，調查顯示，47%的MRO公司維修過程中面臨著40%-59%不確定工作內容[2]。雖然近年來國內外航空維修市場發展迅速，但是生產管理卻面臨著很多難以有效解決的問題，如何有效地解決維修生產調度中的問題對于MRO企業提高生產效率、提升生產能力、優化庫存管理以及提高客戶滿意度等方面具有重要意義。

2 國內外研究現狀

MRO企業是再制造工業的重要組成部分，一些復雜的特點使得MRO計劃與調度問題與傳統制造業有很大不同，例如：如拆分-修理-組裝的三級結構、待維修件質量水平的不確定、物料匹配需求以及不確定工藝路線和工時。MRO是生產計劃與調度的一種新的研究領域，它的復雜性和不確定性引起學術界的廣泛關注。

仿真優化是一種適合解決含有不確定性調度問題的有效方法，Guide[3]等人研究了再制造的調度策略，分解機制和優先調度規則被建立在仿真模型中，通過大量的對比實驗證明了最早交期(EDD)的調度規則往往能夠得到很不錯的結果，而分解機制的不同對調度效果的影響比較小。Guide等人[4]以最短交貨期為目標，研究了調度規則對再制造系統的訂單執行策略的影響，結果表明，通過采用簡單的調度規則能顯著提高再制造系統的性能指標。Christoph[5]等人將研究目標定位于尋找適合修理車間job-shop運作的調度規則，首先假設使用調度規則可以提高調度結果，考慮到MRO系統的復雜特點，文章通過建立仿真模型，將準時交貨率、在制品率、利用率以及生產周期作為衡量標準，結果表明，調度規則對MRO的調度效果的確有一定的影響，并且發現FIFO/Slack和ESD/Slack的規則組合會取得更好的效果。

Kim[6]等人首先分析了再制造系統的復雜特點，考慮到分解-修理-組裝的三級結構，并將決策變量定義為待維修件在分解車間中被分解的順序、子部件在修理車間中每個工作站前的修理順序以及待維修件在組裝車間被組裝的順序，文章建立基于仿真的整數規劃模型，通過分析，認為該模型是NP-hard問題，文章提出基于調度規則的啟發式算法、基于NEH的啟發式算法以及IG(Iterated greedy)算法進行求解，并通過大量算例對比分析了不同啟發式算法的優缺點。然而，模型中針對修理車間的建模是確定的，他們認為子部件在修理車間有固定的維修工藝路線，此外也沒有考慮到工時的不確定性。

郝[1]等人在對航空維修企業調度問題國內外研究現狀詳細分析的基礎上，建立以最小化期望權重延誤時間為目標的混合整數線性規劃模型，因為該問題是NP-hard問題，通過使用傳統的優化方法很難求得最優解，他們提出基于多精度仿真模型的MO2TOS算法對該問題求解，并通過基于實際背景的算例驗證了模型的可行性。然而，當問題規模增大時，由于解空間巨大，MO2TOS算法將不再適合求解該問題。本文的研究背景是在該研究基礎上開展的，通過基于仿真優化的方法解決大規模問題情況下的MRO調度問題。

3 MRO調度問題建模

3.1 MRO問題描述

一般的MRO系統基本框架包含三個車間，為了簡便，即使現實中每個車間可能包含多個，但我們考慮每種車間只含有一個，三個車間各自主要的工序內容如下：

分解車間：分解維修件、清洗以及檢測；

修理車間：包含很多不同的工序和機器，一般認為是job-shop類型，子部件在該車間的工藝流程不確定；

組裝車間：組裝和最后的檢驗。

待維修件首先在分解車間根據BOM結構分解形成若干子部件，每個子部件的檢測后狀態可能是修理、完好、報廢三種狀態中的一種，每種維修狀態表示子部件在修理車間不同的維修工藝路線，因此，每個子部件的實際工藝路線是不知道的，直到待維修件完成分解和檢測工序；此外，因為子部件損壞程度不同，即使對于兩個相同的子部件，其在同一個工序上的加工時間也存在不確定性。

可見，整個維修過程受到很多約束條件，在我們的問題中，對于N個給定的待維修件，決策變量是待維修件在分解車間分解的先后順序、拆分出的子部件在修理車間每個工序上的修理順序、以及子部件在組裝車間的組裝順序。優化目標是期望權重延誤時間之和最小。

3.2 MRO調度問題的仿真模型

如上文所述，MRO問題不確定性因素多(不確定達到時間，不確定加工時間，不確定工藝路線等)，問題結構復雜，為了實現對該問題的求解，結合作者在一家航空維修企業的項目經歷，為不失一般性，本文對所研究的這類MRO調度問題做出以下假設：

整個MRO系統只由一個分解車間、一個修理車間和一個組裝車間構成；

分解車間和組裝車間分別由一個工序組成，每種工序只包含一個機器；

修理車間有多種工序類型，每個子部件在修理車間的工藝路線是不確定的；

修理車間每個工序只包含一個機器；

每個拆分出的子部件都只能組裝到原主部件上；

每個機器同一時間只能加工一個部件。

首先我們基于C++建立以最小化期望權重延誤時間為目標的仿真模型，示意圖如圖1所示。

圖1 MRO系統結構圖

其中OP1和OP8分別表示分解車間和組裝車間，剩余工序表示修理車間。假設調度開始時刻，n個待維修件已經可以被安排調度，所有待維修件在每個機器上的加工順序是相同的，這個順序也是我們要決策的，其中OP4和OP5各自擁有兩個不同的機器處理不同的工作內容，并且各自擁有一個概率值，這體現出MRO系統在修理車間的工藝路線不確定性。基于實際的維修企業信息，并不是所有的工序的加工時間都是不確定的，例如，清洗工序。因此，我們只假設OP6和OP7有不確定的加工時間，其他工序加工時間是確定的。

4 基于仿真優化的MRO調度問題算法研究

4.1 調度規則

調度規則算法是一種簡單、易操作的啟發式算法，因為其具有容易理解和方便實現的特點，在實際中有著廣泛的應用。在我們問題中，所有待維修件或子部件在分解車間、修理車間和組裝車間內所有工序上的加工順序需要決策。每個工序前都可以通過指定一種規則來實現調度，根據現有文獻中對調度規則的研究[6]，我們對常見并且有效的調度規則分為兩類，如表1所示。其中，第一類調度規則可以考慮到待維修件在其維修工藝路線上所有工序的加工特點，而第二類調度規則主要針對某個特定工序。

表1 兩類調度規則

對于所有待維修件在分解車間中分解工序前的加工順序，我們采用第一類調度規則；對于子部件在修理車間以及組裝車間中工序前的加工順序，我們采用第二類調度規則。顯然為了實現MRO企業維修現場的生產調度，選擇何種調度規則組合是我們要研究的問題。

4.2 NEH算法

在構造型啟發式算法中，Nawaz-Enscore-Ham(NEH)[7]被認為是計算以make-span為目標的排列flow-shop問題的一種非常高效的算法[6][8]。基于NEH算法的基本思路，Fernandez-Viagas[9]等人提出一種適用于以延誤時間為目標的改進NEH算法。這種新的NEH算法與傳統NEH算法有兩方面不同：第一，以EDD規則得到的解作為NEH的初始解；第二，通過計算總延誤時間來評價一個部分順序。

針對MRO仿真模型，我們通過NEH求解待維修件在分解車間的加工順序，對于修理車間和組裝車間內工序前的加工順序，我們通過調度規則得到加工順序。與一般NEH算法相比，本文提出的NEH算法會考慮不同調度規則得到的解作為NEH初始解，與修理車間和組裝車間的調度規則的最佳組合。此外，在算法執行過程中，對于具有相同目標函數的兩個順序，我們通過使用最小總空閑時間[10]的選擇機制進行選擇，而非隨機選擇。

步驟1：通過上節調度規則中給出的某種第一類調度規則得到一個初始順序，記為Seq0=(J1,J2,…,Jn)；

步驟2：設置k=2，從Seq0中選擇前兩個待維修件J1和J2，分別形成序列(J1,J2)和(J2,J1)，計算各自的tardiness，以較小tardiness的序列作為當前序列Seq，假設Seq=J1,J2,…,Jn；

步驟3：設置k=3，如果k≤N，轉向步驟4；否則轉向步驟7；

步驟4：從Seq0中選擇第k個待維修件；

步驟5：將待維修件Jk分別插入到序列Seq中的k個可能位置，得到k個新的序列，如：{Jk,J1,J2,…,Jk-1}，{J1,Jk,J2,…,Jk-1},…,{J1,J2,…,Jk-1),Jk}。計算各自的tardiness，把最小tardiness的序列作為當前序列Seq；如果有多個相同的最小tardiness，則通過最小總空閑時間的選擇機制進行選擇。

步驟6：設置k=k+1，轉向步驟3。

步驟7：把當前序列Seq作為NEH算法得到的最優調度順序，并輸出該順序，算法結束。

4.3 遺傳算法(GA)

NEH算法雖然效率高，但只是一個局部搜索的構造型啟發式算法，為了獲得更好的解，我們需要具有全局搜索特性的改進型啟發式算法。在生產計劃與調度領域，遺傳算法(GA)已經被廣泛應用于求解NP-hard組合優化問題[10][11][12]。基于生物進化的“優勝劣汰”原理，GA通過選擇、交叉和變異操作來實現群體并行優化。作為一種通用的全局優化算法，GA近年來在各領域得到廣泛應用，但大量研究表明GA存在易早熟、算法參數敏感等缺點，取得良好的性能需要依賴較大的種群并對算法參數作精心設計[13]。

在遺傳算法中，我們直接通過順序編號作為染色體編碼。針對本文提出的問題，與NEH算法一樣，通過GA求解待維修件在分解車間的加工順序，對于修理車間和組裝車間內工序前的加工順序，我們通過調度規則得到加工順序。

染色體的表示：因為本文模型是求解分解車間待維修件的加工順序，因此可以直接用自然數順序編碼。假設當前有8個待維修件，編號分別為1,2,3,4,5,6,7,8。則某一排列(染色體)可為：86 2 3 7 5 1 4。

交叉操作方法：本文采用典型的PMX方法，假如有兩個個體A和B，A：8 62 3 75 1 4，B：1 5 4 2 8 6 3 7。PMX 操作方法的基本過程如下：首先在A、B 染色體上隨機選取一段，例如2,3,7 和4,2,8，用該段內的基因對應關系來決定一系列的交換，雜交變換后的新個體A和B分別為：7 64 2 85 1 3，1 5 2 3 7 6 4 8。

該算法的具體步驟如下：

步驟1：設置參數，根據文獻對GA參數的研究，我們設置種群大小為2.5*n，迭代次數為3*n，交叉和變異概率分別為0.75和0.25。

步驟2：設置t=0；通過隨機產生的方式初始化種群S(0)；

步驟3：通過計算適應度函數來評價種群S(0)中所有個體；

步驟4：計算選擇概率；

步驟5：如果t>3*n，轉向步驟11；否則，轉向步驟6；

步驟6：設置t=t+1；

步驟7：從種群S(t-1)選擇新的種群S(t)；

步驟8：交叉操作，交叉操作使用PMX方法[10][14]；

步驟9：變異；

步驟10：評價新的種群S(t)；

步驟11：把當前種群中適應度值最高的順序作為GA算法得到的調度順序，輸出該順序，算法結束。

上面給出的GA算法的初始種群完全是隨機產生的，本文對這種傳統的GA算法進行改進，改進的GA算法的初始種群中有一個個體是NEH算法的解，并且有0.25*n個個體是以NEH的解為基礎隨機變異產生的，在GA迭代過程中，始終保證每代種群中最優秀的個體被保留下來。

4.4 算例設計與結果分析

為了研究不同算法在處理MRO調度問題上的效果，本節我們設計一系列算例進行驗證，并對計算結果進行對比分析。這設計算例時，我們需要考慮以下四個變量：待維修件數量、每個待維修件可以拆分的子部件數量、每個子部件可能的工藝路線個數以及每個子部件所有可能工藝路線上的最大工序個數。

本文給出的算例中，待維修件數量可以為(6,10,15,30,50)，每個待維修件可以拆分出的子部件個數為(2,3)，對于每一個子部件，其可能的工藝路線為(2,3)，而對于每個子部件，其所有工藝路線中最大工序個數為(3,5,7)。根據這些參數，我們可以隨機產生60個算例，為了表述方便，對其進行編號如表2所示：

表2 60個算例編號

在隨機產生算例時，考慮到模型中工時和工藝路線是不確定的，所以，我們將每個工序的工時設定為一個三點分布，例(2,4,5)，而這三個值相應的概率從U(0,1)中隨機產生，例(0.1,0.6,0.3)。其中U(a,b)表示一個在區間[a,b]內的均勻分布。具體來講，基于一定的實際數據，每個待維修件在修理車間任一工序的工時從U(2,6)中產生，而在分解車間和組裝車間任一工序的工時從U(1,3)中產生。

每個待維修件的交期(due date)從U(P(1-T-R/2),P(1-T+R/2))中隨機產生[15]，其中T和R分別表示延遲參數和交期范圍參數，并分別設置為0.37和0.26，P是make-span的下界，每個待維修件的延遲權重(λ值)從U(1,2)中隨機產生。

本文所有算法程序都使用C++編碼，并在英特爾酷睿i3，主頻3.40GHz的CPU和4.00GB內存的64位win7電腦上進行運算。對于每個解，我們設置仿真次數為1000以消除噪音獲得穩定目標函數值。

由于篇幅有限，不失一般性，我們只展示編號為(6,12,18,24,30,36,42,48,54,60)的算例的計算結果。為了比較不同算法的表現，兩種測量標準在本文被采用，分別是平均相對性能比率(ARPR)和平均提高百分比(API)。

其中，Heuristici表示對于第i個算例，該啟發式算法計算得到的目標函數值，Besti表示對于第i個算例，所有啟發式算法得到的最好值。為了比較不同算法的計算效果，我們計算每個目標函數值的均值和方差，最優性比較是基于假設檢驗，下文所有結果的置信度都是95%。

調度規則：表1給出了調度規則算法的表現，因為第一類調度規則有9種，第二類調度規則有6中，所以一共具有54種組合。因篇幅限制，本文根據平均ARPR值的大小只給出最好3種和最差3種的組合。其中EDD-FIFO表示分解車間的調度規則是EDD，而修理和組裝車間的調度規則是FIFO。

從表3可以看出，EDD-EDD、EDD-FIFO和STPT-FIFO三種調度規則普遍來說表現比較好，但是并不能說其中哪一種調度規則絕對比其他更好。隨著問題規模增大，顯然EDD-EDD調度規則逐漸更具有優勢。此外，調度規則算法計算速度很快，即使對于包含50個待維修件的算例-60，其計算時間也在1秒之內，這也是調度規則能夠在實際中廣泛使用的原因之一。

表3 ARPR結果對于調度規則算法

NEH算法：NEH算法的計算時間要比調度規則大，對于算例60，NEH算法的計算時間約為8分鐘。雖然NEH算法的計算比較耗時，但是其解的質量相對于調度規則也有一定的提高，表4給出NEH算法與同種調度規則相比解的API值。從表4可以看出，當把調度規則作為NEH的初始解時，NEH算法獲得的解的質量有很大的提高，最大的提高值可以達到23.51%(如NEH-LTRT-FIFO)。顯然，從解的質量方面來看，即使調度規則支持快速決策，但是解的質量仍有很大的提升空間。

表4 NEH算法與調度規則相比的API值

GA算法：表5給出了GA算法、NEH算法的比較評價，表中的值都是與同種組合的調度規則相比得到的API。根據表3、4的結果，我們可以看出不管是NEH算法還是調度規則，EDD-FIFO和STPT-FIFO兩種組合表現的都比較好。所以在驗證GA算法表現時，我們只展示這兩種組合分別作為GA的初始解時GA解的情況。在表5中，符號GA-EDD-FIFO中，EDD-FIFO表示將NEH-EDD-FIFO算法得到的解作為GA算法初始種群中的一個，與其它算法一樣，FIFO表示修理車間和組裝車間的調度規則是FIFO。

從表5中可以看出，對于給出的算例，GA-EDD-FIFO和GA-STPT-FIFO兩種組合得到的解與相同組合的調度規則得到的解相比，其平均API值分別為21.16%和21.18%，而對于NEH-EDD-FIFO和NEH-STPT-FIFO兩種組合，其平均API值分別為18.07%和16.57%。所以，與NEH算法相比，有初始解的GA算法可以得到質量更高的解。相比有初始解的GA算法，純GA算法的平均API仍然大于NEH算法，但是隨著待維修件數量增大，純GA算法的API值遠小于有初始解的GA算法，可見，純GA算法此時效率較低，改進的GA算法表現優于純GA算法。

表5 GA、NEH算法分別與調度規則相比的API值

同樣我們可以注意到，對于同種調度規則組合，NEH算法對解質量的提高百分比大于GA算法對NEH算法解質量的提高百分比，這可能是因為GA算法得到的解已經接近最優解或者是GA算法并沒有比NEH算法好太多。然而從算法計算時間方面來看，GA算法是非常耗時的，表5中GA算法最大計算時間設為3600秒。因此，實際應用中，當對解的質量要求很高時，GA算法才有應用價值。

5 結論

本文針對MRO調度問題的復雜性和不確定性構建仿真模型，并提出三種啟發式算法，分別是調度規則、NEH算法和GA算法，其中NEH算法屬于構造型啟發式算法，GA屬于改進型啟發式算法。然后對三種啟發式算法的計算流程進行詳細介紹，本文最后給出若干計算算例，分別使用三種啟發式算法進行計算，并將計算結果進行展示和對比分析。

通過大量算例可以得出結論：調度規則算法計算時間快，但計算結果較差，GA算法的計算結果最好，但是非常耗時，適用于對解的質量要求很高的情況下，而NEH算法在計算時間和求解質量方面居于調度規則和GA之間。