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

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

1 引言

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

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

2 國(guó)內(nèi)外研究現(xiàn)狀

MRO企業(yè)是再制造工業(yè)的重要組成部分，一些復(fù)雜的特點(diǎn)使得MRO計(jì)劃與調(diào)度問題與傳統(tǒng)制造業(yè)有很大不同，例如：如拆分-修理-組裝的三級(jí)結(jié)構(gòu)、待維修件質(zhì)量水平的不確定、物料匹配需求以及不確定工藝路線和工時(shí)。MRO是生產(chǎn)計(jì)劃與調(diào)度的一種新的研究領(lǐng)域，它的復(fù)雜性和不確定性引起學(xué)術(shù)界的廣泛關(guān)注。

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

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

郝[1]等人在對(duì)航空維修企業(yè)調(diào)度問題國(guó)內(nèi)外研究現(xiàn)狀詳細(xì)分析的基礎(chǔ)上，建立以最小化期望權(quán)重延誤時(shí)間為目標(biāo)的混合整數(shù)線性規(guī)劃模型，因?yàn)樵搯栴}是NP-hard問題，通過使用傳統(tǒng)的優(yōu)化方法很難求得最優(yōu)解，他們提出基于多精度仿真模型的MO2TOS算法對(duì)該問題求解，并通過基于實(shí)際背景的算例驗(yàn)證了模型的可行性。然而，當(dāng)問題規(guī)模增大時(shí)，由于解空間巨大，MO2TOS算法將不再適合求解該問題。本文的研究背景是在該研究基礎(chǔ)上開展的，通過基于仿真優(yōu)化的方法解決大規(guī)模問題情況下的MRO調(diào)度問題。

3 MRO調(diào)度問題建模

3.1 MRO問題描述

一般的MRO系統(tǒng)基本框架包含三個(gè)車間，為了簡(jiǎn)便，即使現(xiàn)實(shí)中每個(gè)車間可能包含多個(gè)，但我們考慮每種車間只含有一個(gè)，三個(gè)車間各自主要的工序內(nèi)容如下：

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

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

組裝車間：組裝和最后的檢驗(yàn)。

待維修件首先在分解車間根據(jù)BOM結(jié)構(gòu)分解形成若干子部件，每個(gè)子部件的檢測(cè)后狀態(tài)可能是修理、完好、報(bào)廢三種狀態(tài)中的一種，每種維修狀態(tài)表示子部件在修理車間不同的維修工藝路線，因此，每個(gè)子部件的實(shí)際工藝路線是不知道的，直到待維修件完成分解和檢測(cè)工序；此外，因?yàn)樽硬考p壞程度不同，即使對(duì)于兩個(gè)相同的子部件，其在同一個(gè)工序上的加工時(shí)間也存在不確定性。

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

3.2 MRO調(diào)度問題的仿真模型

如上文所述，MRO問題不確定性因素多(不確定達(dá)到時(shí)間，不確定加工時(shí)間，不確定工藝路線等)，問題結(jié)構(gòu)復(fù)雜，為了實(shí)現(xiàn)對(duì)該問題的求解，結(jié)合作者在一家航空維修企業(yè)的項(xiàng)目經(jīng)歷，為不失一般性，本文對(duì)所研究的這類MRO調(diào)度問題做出以下假設(shè)：

整個(gè)MRO系統(tǒng)只由一個(gè)分解車間、一個(gè)修理車間和一個(gè)組裝車間構(gòu)成；

分解車間和組裝車間分別由一個(gè)工序組成，每種工序只包含一個(gè)機(jī)器；

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

修理車間每個(gè)工序只包含一個(gè)機(jī)器；

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

每個(gè)機(jī)器同一時(shí)間只能加工一個(gè)部件。

首先我們基于C++建立以最小化期望權(quán)重延誤時(shí)間為目標(biāo)的仿真模型，示意圖如圖1所示。

圖1 MRO系統(tǒng)結(jié)構(gòu)圖

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

4 基于仿真優(yōu)化的MRO調(diào)度問題算法研究

4.1 調(diào)度規(guī)則

調(diào)度規(guī)則算法是一種簡(jiǎn)單、易操作的啟發(fā)式算法，因?yàn)槠渚哂腥菀桌斫夂头奖銓?shí)現(xiàn)的特點(diǎn)，在實(shí)際中有著廣泛的應(yīng)用。在我們問題中，所有待維修件或子部件在分解車間、修理車間和組裝車間內(nèi)所有工序上的加工順序需要決策。每個(gè)工序前都可以通過指定一種規(guī)則來實(shí)現(xiàn)調(diào)度，根據(jù)現(xiàn)有文獻(xiàn)中對(duì)調(diào)度規(guī)則的研究[6]，我們對(duì)常見并且有效的調(diào)度規(guī)則分為兩類，如表1所示。其中，第一類調(diào)度規(guī)則可以考慮到待維修件在其維修工藝路線上所有工序的加工特點(diǎn)，而第二類調(diào)度規(guī)則主要針對(duì)某個(gè)特定工序。

表1 兩類調(diào)度規(guī)則

對(duì)于所有待維修件在分解車間中分解工序前的加工順序，我們采用第一類調(diào)度規(guī)則；對(duì)于子部件在修理車間以及組裝車間中工序前的加工順序，我們采用第二類調(diào)度規(guī)則。顯然為了實(shí)現(xiàn)MRO企業(yè)維修現(xiàn)場(chǎng)的生產(chǎn)調(diào)度，選擇何種調(diào)度規(guī)則組合是我們要研究的問題。

4.2 NEH算法

在構(gòu)造型啟發(fā)式算法中，Nawaz-Enscore-Ham(NEH)[7]被認(rèn)為是計(jì)算以make-span為目標(biāo)的排列flow-shop問題的一種非常高效的算法[6][8]?；贜EH算法的基本思路，F(xiàn)ernandez-Viagas[9]等人提出一種適用于以延誤時(shí)間為目標(biāo)的改進(jìn)NEH算法。這種新的NEH算法與傳統(tǒng)NEH算法有兩方面不同：第一，以EDD規(guī)則得到的解作為NEH的初始解；第二，通過計(jì)算總延誤時(shí)間來評(píng)價(jià)一個(gè)部分順序。

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

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

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

步驟3：設(shè)置k=3，如果k≤N，轉(zhuǎn)向步驟4；否則轉(zhuǎn)向步驟7；

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

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

步驟6：設(shè)置k=k+1，轉(zhuǎn)向步驟3。

步驟7：把當(dāng)前序列Seq作為NEH算法得到的最優(yōu)調(diào)度順序，并輸出該順序，算法結(jié)束。

4.3 遺傳算法(GA)

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

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

染色體的表示：因?yàn)楸疚哪Ｐ褪乔蠼夥纸廛囬g待維修件的加工順序，因此可以直接用自然數(shù)順序編碼。假設(shè)當(dāng)前有8個(gè)待維修件，編號(hào)分別為1,2,3,4,5,6,7,8。則某一排列(染色體)可為：86 2 3 7 5 1 4。

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

該算法的具體步驟如下：

步驟1：設(shè)置參數(shù)，根據(jù)文獻(xiàn)對(duì)GA參數(shù)的研究，我們?cè)O(shè)置種群大小為2.5*n，迭代次數(shù)為3*n，交叉和變異概率分別為0.75和0.25。

步驟2：設(shè)置t=0；通過隨機(jī)產(chǎn)生的方式初始化種群S(0)；

步驟3：通過計(jì)算適應(yīng)度函數(shù)來評(píng)價(jià)種群S(0)中所有個(gè)體；

步驟4：計(jì)算選擇概率；

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

步驟6：設(shè)置t=t+1；

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

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

步驟9：變異；

步驟10：評(píng)價(jià)新的種群S(t)；

步驟11：把當(dāng)前種群中適應(yīng)度值最高的順序作為GA算法得到的調(diào)度順序，輸出該順序，算法結(jié)束。

上面給出的GA算法的初始種群完全是隨機(jī)產(chǎn)生的，本文對(duì)這種傳統(tǒng)的GA算法進(jìn)行改進(jìn)，改進(jìn)的GA算法的初始種群中有一個(gè)個(gè)體是NEH算法的解，并且有0.25*n個(gè)個(gè)體是以NEH的解為基礎(chǔ)隨機(jī)變異產(chǎn)生的，在GA迭代過程中，始終保證每代種群中最優(yōu)秀的個(gè)體被保留下來。

4.4 算例設(shè)計(jì)與結(jié)果分析

為了研究不同算法在處理MRO調(diào)度問題上的效果，本節(jié)我們?cè)O(shè)計(jì)一系列算例進(jìn)行驗(yàn)證，并對(duì)計(jì)算結(jié)果進(jìn)行對(duì)比分析。這設(shè)計(jì)算例時(shí)，我們需要考慮以下四個(gè)變量：待維修件數(shù)量、每個(gè)待維修件可以拆分的子部件數(shù)量、每個(gè)子部件可能的工藝路線個(gè)數(shù)以及每個(gè)子部件所有可能工藝路線上的最大工序個(gè)數(shù)。

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

表2 60個(gè)算例編號(hào)

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

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

本文所有算法程序都使用C++編碼，并在英特爾酷睿i3，主頻3.40GHz的CPU和4.00GB內(nèi)存的64位win7電腦上進(jìn)行運(yùn)算。對(duì)于每個(gè)解，我們?cè)O(shè)置仿真次數(shù)為1000以消除噪音獲得穩(wěn)定目標(biāo)函數(shù)值。

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

其中，Heuristici表示對(duì)于第i個(gè)算例，該啟發(fā)式算法計(jì)算得到的目標(biāo)函數(shù)值，Besti表示對(duì)于第i個(gè)算例，所有啟發(fā)式算法得到的最好值。為了比較不同算法的計(jì)算效果，我們計(jì)算每個(gè)目標(biāo)函數(shù)值的均值和方差，最優(yōu)性比較是基于假設(shè)檢驗(yàn)，下文所有結(jié)果的置信度都是95%。

調(diào)度規(guī)則：表1給出了調(diào)度規(guī)則算法的表現(xiàn)，因?yàn)榈谝活愓{(diào)度規(guī)則有9種，第二類調(diào)度規(guī)則有6中，所以一共具有54種組合。因篇幅限制，本文根據(jù)平均ARPR值的大小只給出最好3種和最差3種的組合。其中EDD-FIFO表示分解車間的調(diào)度規(guī)則是EDD，而修理和組裝車間的調(diào)度規(guī)則是FIFO。

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

表3 ARPR結(jié)果對(duì)于調(diào)度規(guī)則算法

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

表4 NEH算法與調(diào)度規(guī)則相比的API值

GA算法：表5給出了GA算法、NEH算法的比較評(píng)價(jià)，表中的值都是與同種組合的調(diào)度規(guī)則相比得到的API。根據(jù)表3、4的結(jié)果，我們可以看出不管是NEH算法還是調(diào)度規(guī)則，EDD-FIFO和STPT-FIFO兩種組合表現(xiàn)的都比較好。所以在驗(yàn)證GA算法表現(xiàn)時(shí)，我們只展示這兩種組合分別作為GA的初始解時(shí)GA解的情況。在表5中，符號(hào)GA-EDD-FIFO中，EDD-FIFO表示將NEH-EDD-FIFO算法得到的解作為GA算法初始種群中的一個(gè)，與其它算法一樣，F(xiàn)IFO表示修理車間和組裝車間的調(diào)度規(guī)則是FIFO。

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

表5 GA、NEH算法分別與調(diào)度規(guī)則相比的API值

同樣我們可以注意到，對(duì)于同種調(diào)度規(guī)則組合，NEH算法對(duì)解質(zhì)量的提高百分比大于GA算法對(duì)NEH算法解質(zhì)量的提高百分比，這可能是因?yàn)镚A算法得到的解已經(jīng)接近最優(yōu)解或者是GA算法并沒有比NEH算法好太多。然而從算法計(jì)算時(shí)間方面來看，GA算法是非常耗時(shí)的，表5中GA算法最大計(jì)算時(shí)間設(shè)為3600秒。因此，實(shí)際應(yīng)用中，當(dāng)對(duì)解的質(zhì)量要求很高時(shí)，GA算法才有應(yīng)用價(jià)值。

5 結(jié)論

本文針對(duì)MRO調(diào)度問題的復(fù)雜性和不確定性構(gòu)建仿真模型，并提出三種啟發(fā)式算法，分別是調(diào)度規(guī)則、NEH算法和GA算法，其中NEH算法屬于構(gòu)造型啟發(fā)式算法，GA屬于改進(jìn)型啟發(fā)式算法。然后對(duì)三種啟發(fā)式算法的計(jì)算流程進(jìn)行詳細(xì)介紹，本文最后給出若干計(jì)算算例，分別使用三種啟發(fā)式算法進(jìn)行計(jì)算，并將計(jì)算結(jié)果進(jìn)行展示和對(duì)比分析。

通過大量算例可以得出結(jié)論：調(diào)度規(guī)則算法計(jì)算時(shí)間快，但計(jì)算結(jié)果較差，GA算法的計(jì)算結(jié)果最好，但是非常耗時(shí)，適用于對(duì)解的質(zhì)量要求很高的情況下，而NEH算法在計(jì)算時(shí)間和求解質(zhì)量方面居于調(diào)度規(guī)則和GA之間。