面向多目標(biāo)資源受限的航空維修保障工序調(diào)度方法研究

魏夢(mèng)媛，渠懷賡，孫 坤

（中國(guó)飛行試驗(yàn)研究院，陜西 西安）

引言

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

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

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

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

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

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

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

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

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

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

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

1.2 約束條件

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

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

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

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

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

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

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

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

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

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

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

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

圖1 NSGA-II 算法流程框圖

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

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

表1 專項(xiàng)試驗(yàn)流程邏輯關(guān)系及時(shí)間表

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

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

圖2 ISIGHT 調(diào)用Matlab

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

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

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

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

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

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

4 結(jié)論

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