魏夢媛，渠懷賡，孫 坤

（中國飛行試驗研究院，陜西 西安）

引言

資源受限工序調(diào)度問題(Resource-constrained Project Scheduling Problem,RCPSP)是指在滿足項目時序要求和多種資源的約束下，確定所有任務(wù)的開始時間及結(jié)束時間，使得總時間最短[1]。合理地調(diào)節(jié)各項目活動的開始時間和資源使得能夠有效地縮短項目完工時間，在實際航空維修保障過程中具有非常重要的意義。目前這類問題的研究主要集中在工期單目標(biāo)優(yōu)化問題上[2]。實際航空維修保障中，單一指標(biāo)難以評價方案優(yōu)劣，需考慮多個指標(biāo)并進(jìn)行權(quán)衡，本文將維修保障人力資源的合理配置作為工序調(diào)度問題的目標(biāo)，考慮維修人員數(shù)量的情況下，兼顧維修工序的緊前約束條件，基于RCPSP 構(gòu)建維修保障時間和資源配置的多目標(biāo)優(yōu)化函數(shù)，采用快速非支配排序遺傳算法(NSGA-II)對案例進(jìn)行求解分析，實現(xiàn)在合理安排人力資源對工序進(jìn)行維修的同時，維修時間最短，即合理利用維修資源，盡快完成維修任務(wù)。

1 修保障資源均衡多目標(biāo)優(yōu)化數(shù)學(xué)模型

資源受限情況下，實現(xiàn)航空維修保障過程時間最短、資源合理配置，可以歸結(jié)為多目標(biāo)優(yōu)化問題。

此類問題的數(shù)學(xué)描述如下

針對實際航空維修保障過程，主要從維修工序、維修時間、維修人力資源3 個方面構(gòu)建優(yōu)化模型：優(yōu)化目標(biāo)為時間最短、人力資源合理配置；約束條件為資源數(shù)量和維修工序緊前約束條件。

1.1 目標(biāo)函數(shù)

1.1.1 維修時間最短目標(biāo)

假設(shè)一個維修項目中包括N 個工序，其中活動1和活動N 為虛擬活動，分別作為項目的開始和項目的結(jié)束。

T 為總時間，則目標(biāo)函數(shù)為

以人力資源需要量的標(biāo)準(zhǔn)偏差作為均衡配置評價函數(shù)，數(shù)學(xué)模型表達(dá)如下

將Q 作為評價資源配置均衡的目標(biāo)函數(shù)，當(dāng)Q 越小，維修人員分配的擁擠程度越低，人員調(diào)配使用越合理，目標(biāo)函數(shù)為

1.2 約束條件

維修保障過程中存在2 種約束關(guān)系：一是維修人員的數(shù)量約束，即對工序中任意時刻，正在進(jìn)行的工序的維修人員總數(shù)，不超過限制的數(shù)量；二是緊前約束關(guān)系，即兩個工序具有必然的先后關(guān)系[3]。如工序1和工序2 具有緊前約束關(guān)系，則工序2 的開始時間晚于工序1 的結(jié)束時間。

在整個維修項目中有如下假設(shè)：

a.單個工序的活動具有連續(xù)性，不存在停頓；

b.各工序緊前關(guān)系保持不變；

c.各種資源之間相互獨(dú)立，不存在相關(guān)關(guān)系。

維修保障資源分配數(shù)學(xué)模型構(gòu)建可以描述如下：一是維修人員須按照維修手冊內(nèi)容逐步完成所有工序，在前一項工作還沒有完成的情況下，不能進(jìn)行下一步活動；二是維修人員總數(shù)有限，每步工序所需維修人員數(shù)量是一定的，同一時刻進(jìn)行的所有工序所需要的維修人員的數(shù)量之和應(yīng)不大于總的維修人員數(shù)量；三是維修人員只有在進(jìn)行完上一步維修活動后，才可以繼續(xù)下一項，不能同時進(jìn)行兩項維修活動；四是總的維修時間的約束，完成最后一項維修保障活動的時刻T 不能大于總的維修保障時間，T 即為實際總維修保障時間。數(shù)學(xué)模型可以描述為

式（6）表示所有的最早、最晚開工時間應(yīng)滿足工序排布邏輯條件，且資源利用在受限范圍內(nèi)。

2 基于NSGA-II 的多目標(biāo)優(yōu)化算法

以上優(yōu)化模型為多目標(biāo)規(guī)劃問題，一般不可能存在一個使每個目標(biāo)都達(dá)到最優(yōu)的解，本文選擇快速非支配排序遺傳算法-NSGA-II 作為多目標(biāo)優(yōu)化算法，可以得到一組均衡解，稱為最優(yōu)非劣解集或Pareto最優(yōu)解集[4]。

NSGA-II 算法的基本思想如下。

第一步隨機(jī)生成大小為N 的初始種群，對該種群進(jìn)行非支配排序，再根據(jù)遺傳算法，進(jìn)行選擇、交叉、變異操作，可以得到第一代子代種群；從第二代子代種群開始，合并父代種群與子代種群，進(jìn)行快速非支配排序，計算擁擠度，包括非支配層的所有個體，根據(jù)個體之間的關(guān)系和擁擠度，選擇出有優(yōu)勢的個體，形成新的父代種群；再重復(fù)第二步，通過遺傳算法中的選擇、交叉、變異操作形成新的子代種群，直到達(dá)到設(shè)定的循環(huán)數(shù)，或達(dá)到符合結(jié)合的條件[5]。

NSGA-II 算法主要的優(yōu)化策略包含以下3 個方面。一是快速非支配排序，這一步根據(jù)個體的優(yōu)勢排列將種群中個體排序；二是擁擠度比較算子，根據(jù)個體擁擠程度選擇進(jìn)入下一代進(jìn)行循環(huán)迭代的個體，保持種群多樣性；三是精英保留策略，對應(yīng)第二步，合并父代和子代個體再優(yōu)先選擇優(yōu)秀個體，作為下一代種群，這一步能夠保留歷代計算出的最優(yōu)個體。NSGA-II算法流程見圖1。

圖1 NSGA-II 算法流程框圖

3 基于isight 平臺構(gòu)建的多目標(biāo)優(yōu)化流程

以吊艙軟管更換試驗為例進(jìn)行分析。機(jī)務(wù)維護(hù)人員總數(shù)量為8 人。在吊艙拆卸試驗工序中，B、C、F，G四個工序?qū)儆诳刹⑿泄ぷ?。根?jù)據(jù)緊前工序排列原則，得到各工序的最早開工時間和最晚開工時間，并按實際工作中統(tǒng)計的各工序持續(xù)時間與人員數(shù)量，給出表1 中的試驗流程邏輯關(guān)系。

表1 專項試驗流程邏輯關(guān)系及時間表

在Matlab 軟件中，對前文中給出的優(yōu)化目標(biāo)和約束條件指標(biāo)進(jìn)行編程求解。

對多目標(biāo)函數(shù)的優(yōu)化設(shè)計，采用Isight 封裝的NSGA-II 方法。以Isight 軟件為平臺，集成Matlab 軟件完成并聯(lián)機(jī)構(gòu)的多目標(biāo)優(yōu)化。如圖2 所示，搭建并聯(lián)機(jī)構(gòu)多目標(biāo)優(yōu)化流程圖，箭頭為數(shù)據(jù)和過程傳遞路徑。

圖2 ISIGHT 調(diào)用Matlab

通過多目標(biāo)優(yōu)化最終得到可行的設(shè)計點(diǎn)，對結(jié)果的選擇提供重要的參考。圖3 中可以看出可行點(diǎn)和不可取的劣解的分布。各設(shè)計點(diǎn)數(shù)值見表2。表2 的6 組結(jié)果中，后3 組結(jié)果均為較優(yōu)，其中第6 組的資源均衡評價指標(biāo)Q 與總時間T 都為最小，對應(yīng)最優(yōu)情況。

圖3 可行解與最優(yōu)解

表2 優(yōu)化結(jié)果及相應(yīng)工序排列情況

優(yōu)化前和優(yōu)化后共7 組結(jié)果見圖4。

圖4 優(yōu)化結(jié)果對比

圖4 中第一組數(shù)值為優(yōu)化前的目標(biāo)值，可以看出，通過多目標(biāo)優(yōu)化，對工序進(jìn)行調(diào)度排布，使得維修保障時間逐漸縮短，其中最優(yōu)組時長為47 min，人員標(biāo)準(zhǔn)偏差也相應(yīng)達(dá)到了低區(qū)間，這說明整個過程對于人力資源的配置實現(xiàn)了均衡優(yōu)化。

4 結(jié)論

本研究針對航空維修保障過程中資源受限情況，構(gòu)建了資源約束與維修保障時間最短、人力資源均衡配置多目標(biāo)數(shù)學(xué)優(yōu)化模型，結(jié)合NSGA-II 多目標(biāo)優(yōu)化算法，在Isight 平臺中實現(xiàn)維修保障資源均衡多目標(biāo)優(yōu)化流程，可以達(dá)到時間縮短、資源均衡配置的目標(biāo)。本研究提出的方法可以為航空維修保障工序調(diào)度提供參考。