溫海駿，李 清，邵延君，劉永姜

（中北大學(xué)機(jī)械與動(dòng)力工程學(xué)院，太原 030051）

基于Pareto排序法的戰(zhàn)時(shí)裝備維修任務(wù)多目標(biāo)調(diào)度方法*

溫海駿，李 清，邵延君，劉永姜

（中北大學(xué)機(jī)械與動(dòng)力工程學(xué)院，太原 030051）

針對(duì)戰(zhàn)時(shí)武器裝備維修保障問(wèn)題，建立了包括最大完工時(shí)間、延遲時(shí)間和維修單元負(fù)荷在內(nèi)的多目標(biāo)優(yōu)化調(diào)度模型。為提高解的多樣性和收斂性，構(gòu)建了一種基于Pareto排序法和小生境技術(shù)相結(jié)合的遺傳算法用于模型求解，引入Pareto排序和擁擠距離進(jìn)行適應(yīng)度計(jì)算，通過(guò)混沌系統(tǒng)隨機(jī)生成權(quán)重系數(shù)，并使用小生境技術(shù)改進(jìn)選擇方式。通過(guò)實(shí)例驗(yàn)證表明，該方法能夠有效地解決裝備維修多目標(biāo)調(diào)度問(wèn)題。

裝備維修，多目標(biāo)調(diào)度，Pareto排序法，混合遺傳算法

0 引言

高技術(shù)戰(zhàn)爭(zhēng)背景下，武器裝備維修是保障軍隊(duì)?wèi)?zhàn)斗力迅速恢復(fù)的必要條件。當(dāng)前，武器裝備呈現(xiàn)大型化、復(fù)雜化的特征，導(dǎo)致裝備維修任務(wù)難度大大增加。對(duì)戰(zhàn)時(shí)資源配置及維修任務(wù)調(diào)度都提出了極高的要求［1］。在軍隊(duì)資源有限的情況下，如何縮短維修保障時(shí)間，以最低成本、最快速度和最好質(zhì)量開展對(duì)戰(zhàn)損、故障裝備的維修保障工作，以最大程度發(fā)揮維修保障系統(tǒng)效能，成為亟待解決的問(wèn)題。

對(duì)于裝備維修保障，傳統(tǒng)研究多以保障性分析［2］、能力評(píng)價(jià)［3］和建立預(yù)測(cè)方法［4-5］為主，近年來(lái)，研究人員圍繞戰(zhàn)時(shí)裝備維修調(diào)度問(wèn)題相繼展開研究。王正元等［6-7］提出了一種動(dòng)態(tài)維修任務(wù)調(diào)度的優(yōu)化方法，實(shí)現(xiàn)了戰(zhàn)時(shí)維修任務(wù)的動(dòng)態(tài)調(diào)度。朱波等［8］建立了一種通過(guò)控制到達(dá)時(shí)間的維修調(diào)度模型。高建軍［9］在考慮維修時(shí)間與戰(zhàn)斗力關(guān)系的基礎(chǔ)上構(gòu)建了動(dòng)態(tài)維修調(diào)度模型。朱昱［10］從滿足最大保障時(shí)間角度出發(fā)，建立了靜態(tài)維修調(diào)度模型。萬(wàn)明［11］以裝備維修效益最大化為目標(biāo)，建立了維修保障調(diào)度模型。然而戰(zhàn)時(shí)情況錯(cuò)綜復(fù)雜，維修任務(wù)兼具隨機(jī)多發(fā)性、動(dòng)態(tài)全局性、區(qū)域分布性等特點(diǎn)［12］，各目標(biāo)之間相互制約、相互沖突，使得裝備維修調(diào)度問(wèn)題呈現(xiàn)多批量、多工藝、多目標(biāo)、不確定性等特點(diǎn)，缺乏更加符合實(shí)際戰(zhàn)時(shí)狀況的維修調(diào)度模型。

本文針對(duì)這種情況，借鑒生產(chǎn)車間調(diào)度問(wèn)題，建立了多目標(biāo)柔性維修調(diào)度模型。并提出一種基于Pareto排序法的混合遺傳算法進(jìn)行求解。算法使用基于擴(kuò)展維修工序編碼方式，采用混沌加權(quán)和小生境技術(shù)提高進(jìn)化過(guò)程中解的多樣性。以期為快速、高效地進(jìn)行裝備維修保障提供理論支持。

1 問(wèn)題描述及模型建立

武器裝備維修調(diào)度優(yōu)化的目標(biāo)就是要在保證待維修裝備在維修順序約束的條件下，為每道工序分配合適的維修單元，并確定每個(gè)維修單元中待修設(shè)備的排列順序和開始維修時(shí)間，使得多個(gè)性能指標(biāo)達(dá)到最優(yōu)。具有柔性特征的武器裝備維修調(diào)度模型，可描述為：

不同于日常維護(hù)，為贏得戰(zhàn)爭(zhēng)主動(dòng)權(quán)，戰(zhàn)時(shí)裝備維修要求武器裝備在有限維修資源條件下盡快修復(fù)投入使用，并需要綜合考慮多種性能指標(biāo)的要求。因此，本文選用最大完工時(shí)間、延遲時(shí)間和維修單元總負(fù)荷作為維修調(diào)度的優(yōu)化目標(biāo)，具體模型描述如下：

其中：

1）最大完工時(shí)間

2）最大延遲時(shí)間

3）維修單元總負(fù)荷

此外，維修調(diào)度模型還需滿足如下條件：

①即同一時(shí)刻同一個(gè)維修單元只能進(jìn)行一道維修工序，維修過(guò)程不能中斷；②同一個(gè)待修裝備的維修工序有前后制約關(guān)系。③所有維修單元在0時(shí)刻均可用，所有故障設(shè)備在0時(shí)刻都可被維修；④維修工序在維修單元中的維修時(shí)間是確定的；⑤維修作業(yè)是非搶占式的。

約束條件：

式（5）為決策變量約束；式（6）～式（7）為待修裝備在維修單元中的先后順序約束關(guān)系；式（8）為維修單元中各個(gè)待修裝備的先后順序約束。

2 模型求解

2.1 多目標(biāo)遺傳算法設(shè)計(jì)

與車間調(diào)度問(wèn)題類似，超過(guò)兩個(gè)待維修裝備的柔性維修調(diào)度問(wèn)題就是NP-hard問(wèn)題，無(wú)法獲得求解問(wèn)題的最優(yōu)解的多項(xiàng)式時(shí)間算法，只能爭(zhēng)取用較小的計(jì)算量得到問(wèn)題的近似最優(yōu)解［13］。遺傳算法是借鑒生物進(jìn)化規(guī)律發(fā)展而成的隨機(jī)搜索優(yōu)化算法，被廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)等工程技術(shù)領(lǐng)域。但對(duì)于大規(guī)模計(jì)算問(wèn)題，易于陷入“早熟”，因此，本文針對(duì)多目標(biāo)維修調(diào)度問(wèn)題，采用基于Pareto排序的小生境混合遺傳算法進(jìn)行求解。

2.1.1 初始種群產(chǎn)生

首先產(chǎn)生一組具有維修工序順序排列的隨機(jī)染色體，然后在維修工序的可選維修單元集中隨機(jī)選擇兩個(gè)。若隨機(jī)數(shù)大于0.7則選擇維修工時(shí)長(zhǎng)的單元，否則的話選擇維修工時(shí)短的單元。通過(guò)這種方式產(chǎn)生初始種群，可較好地保持種群多樣性。

2.1.2 編碼規(guī)則

裝備維修柔性調(diào)度問(wèn)題中除了要考慮修復(fù)工序的排列順序，還要為每一個(gè)修復(fù)工序選擇一個(gè)合適的修復(fù)單元?；谶@個(gè)特點(diǎn)，編碼方式采取擴(kuò)展維修工序編碼規(guī)則，編碼由兩階段組成，第1段為被修復(fù)裝備順序碼，用來(lái)確定待修復(fù)工件的修復(fù)順序；第2段為維修單元順序碼，用以將每道修復(fù)工序分配給合適的維修單元。以具有4個(gè)維修單元和3臺(tái)損壞裝備的維修系統(tǒng)為例，編碼方式如圖1所示。

解碼過(guò)程將染色體視為維修工序的有序序列，通過(guò)式（7）、式（8）進(jìn)行解碼，把每道工序安排到可用維修單元的盡可能早的時(shí)刻進(jìn)行修復(fù)，直至所有工序都安排完成。

2.1.3 適應(yīng)度計(jì)算

適應(yīng)度的計(jì)算采用Pareto排序的適應(yīng)度賦值機(jī)制［14］，將可行解進(jìn)行Pareto排序，按支配程度將種群劃分為不同集合，集合中的個(gè)體按其非支配程度給定序號(hào)Xj-rank；然后，計(jì)算相同非支配性集合中個(gè)體之間的相互距離，在本集合中找出距離個(gè)體i最近的個(gè)體，兩者之間的距離就是局部擁擠距離Xk-dis。具體步驟如圖2所示。

為提高解的多樣性，通過(guò)Logisitic映射混沌系統(tǒng)隨機(jī)生成權(quán)重系數(shù)，進(jìn)而將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題，即令w1、w2和w3為目標(biāo)函數(shù)權(quán)重向量。優(yōu)化問(wèn)題中的混沌序列權(quán)重系數(shù)可由式（10）產(chǎn)生：

其中，μ為控制參數(shù)，μ∈（2，4]，多目標(biāo)權(quán)重向量w1和 w2由式（10）產(chǎn)生，w3由給出。

2.1.4 選擇

選擇操作采用輪盤賭的方式，為了防止群體收斂于單一個(gè)體的趨勢(shì)，迭代過(guò)程中采用小生境技術(shù)對(duì)每一代適應(yīng)度非常接近的個(gè)體進(jìn)行處理。

式（11）中，r是個(gè)體數(shù)量，maxlj和 minlj分別為進(jìn)化到j(luò)代時(shí)第l個(gè)個(gè)體的最大值和最小值，P為種群規(guī)模大小。式（11）表明小生境域密度越大的個(gè)體被遺傳下去的概率越小。通過(guò)這種選擇方式，可以保持解的多樣性，避免算法陷入局部最優(yōu)解。

2.1.5 交叉和變異

交叉的過(guò)程分兩步進(jìn)行：

1）代維修裝備編碼交叉

首先將全部待修裝備分成兩部分S1和S2；其次隨機(jī)選擇兩條父染色體P1和P2，分別在P1和P2中選出包含在S1和S2中的基因，并依次復(fù)制到子染色體Q1和Q2中，基因位置保持不變；然后，再次選擇在P1和P2中包含在S1和S2中的基因，將其復(fù)制到Q2和Q1中的空閑位置，其順序保持不變，如圖3所示。

2）維修單元編碼交叉

首先，隨機(jī)產(chǎn)生一列與維修單元編碼染色體長(zhǎng)度相等的序列，序列中只包含0、1元素，記為集合H；其次，從P1和P2中選出與集合H中1元素對(duì)應(yīng)的工序，分別復(fù)制到Q1和Q2中；然后將P1和P2中剩下的元素依次復(fù)制到Q1和Q2中，至此完成全部交叉過(guò)程。

變異的過(guò)程分兩步進(jìn)行，首先在待修裝備編碼染色體中隨機(jī)選擇一道工序，隨機(jī)插入到另一工序之前，并保持對(duì)應(yīng)維修單元的編碼不發(fā)生變化；其次，在維修單元編碼染色體中隨機(jī)選擇兩個(gè)工序，然后在可選單元集中選擇其他單元進(jìn)行替換。

2.2 算法驗(yàn)證

為了測(cè)試模型及算法的正確性，對(duì)具有6個(gè)待維修裝備和8個(gè)維修單元的裝備維修調(diào)度問(wèn)題進(jìn)行仿真驗(yàn)證，維修過(guò)程中各待維修裝備的各道工序?qū)?yīng)的維修單元與維修時(shí)間（維修時(shí)間中包含了運(yùn)輸時(shí)間）如表1所示。由于戰(zhàn)時(shí)的需要，部分損壞裝備有限時(shí)送達(dá)要求，即有維修交貨期的要求。

表1 再制造加工過(guò)程FGERT網(wǎng)絡(luò)的活動(dòng)參數(shù)表

根據(jù)表1中的數(shù)據(jù)，使用Matalb2009進(jìn)行編程求解，設(shè)定混合遺傳算法的參數(shù)為：種群大小Pop_size=100，迭代次數(shù) Giter=2 000，交叉概率 Pc=0.8，變異概率Pm=0.1。求解的結(jié)果如表2所示。

表2 實(shí)驗(yàn)結(jié)果

圖4為采用混合優(yōu)化算法得到的裝備維修多目標(biāo)調(diào)度問(wèn)題的Pareto解集三維分布圖，圖5為該三維分布圖對(duì)應(yīng)的平面投影圖。從圖中可以看出，多目標(biāo)優(yōu)化算法能夠有效解決具有柔性特征的維修任務(wù)調(diào)度問(wèn)題，該算法能夠得到一組分布均勻的Pareto前端，表明其Pareto解有較好的分布性。

通過(guò)得到的一組Pareto解，決策者可根據(jù)主觀經(jīng)驗(yàn)或多屬性決策方法進(jìn)行評(píng)估。限于篇幅，此處只給出第1個(gè)Pareto解對(duì)應(yīng)的維修調(diào)度甘特圖，圖中第1位數(shù)字表示待維修裝備，第3位表示維修工序。

3 結(jié)論

本文針對(duì)具有柔性特征的戰(zhàn)時(shí)裝備維修問(wèn)題，建立了多目標(biāo)優(yōu)化調(diào)度模型，并提出了一種基于Pareto和小生境技術(shù)相結(jié)合的混合遺傳算法用于模型的求解，深入研究了混合算法的編碼方式、初始種群生成方式、適應(yīng)度值計(jì)算方式、交叉和變異方式等。并應(yīng)用具有6個(gè)損壞裝備、8個(gè)維修單元的維修系統(tǒng)對(duì)該算法進(jìn)行驗(yàn)證，驗(yàn)證結(jié)果表明，本文提出的模型能夠較好地描述裝備維修的柔性調(diào)度問(wèn)題，算法能夠得到多目標(biāo)最優(yōu)解，證明了算法的合理性和有效性。

［1］朱亞紅，曹繼平，王正元，等.變精度粗糙集的戰(zhàn)時(shí)裝備維修保障資源優(yōu)化配置［J］.火力與指揮控制，2014，39（6）：40-44.

［2］于維銘.保障性分析在現(xiàn)役裝備維修資源確定中的應(yīng)用［J］.裝甲兵工程學(xué)院學(xué)報(bào)，2003，17（1）：55-59.

［3］郭玉明，陳東林，李志剛，等.航空裝備戰(zhàn)時(shí)維修保障能力評(píng)價(jià)模型［J］.火力與指揮控制，2010，35（10）：166-170.

［4］王亞彬.仿真技術(shù)在維修資源預(yù)測(cè)中的應(yīng)用研究［J］.計(jì)算機(jī)仿真，2005，22（7）：249-251.

［5］張申，徐豪華.基于仿真的戰(zhàn)時(shí)維修保障力量需求預(yù)測(cè)方法研究［J］.系統(tǒng)仿真學(xué)報(bào)，2013，25（S1）：386-389.

［6］王正元，朱昱，宋建社，等.動(dòng)態(tài)維修任務(wù)調(diào)度的優(yōu)化方法［J］.機(jī)械工程學(xué)報(bào)，2008，56（1）：92-97.

［7］王正元，嚴(yán)小琴，朱昱，等.一種考慮專業(yè)的動(dòng)態(tài)維修任務(wù)調(diào)度的優(yōu)化方法［J］.兵工學(xué)報(bào)，2009，31（2）：252-256.

［8］朱波，宮俊，唐加福，等.分布式到達(dá)時(shí)間控制器裝備維修任務(wù)實(shí)時(shí)調(diào)度方法［J］.火力與指揮控制，2011，36（8）：126-128.

［9］高建軍，蔣里強(qiáng)，郭強(qiáng)，等.基于戰(zhàn)斗力的維修調(diào)度模型優(yōu)化研究［J］.火力與指揮控制，2014，39（3）：95-98.

［10］朱昱，宋建社，王正元.一種基于最大保障時(shí)間的戰(zhàn)時(shí)裝備維修任務(wù)調(diào)度［J］.系統(tǒng)工程與電子技術(shù)，2007，39（11）：1900-1903.

［11］萬(wàn)明，張鳳鳴，樊曉光.戰(zhàn)時(shí)裝備維修任務(wù)調(diào)度的兩種新算法［J］.系統(tǒng)工程與電子技術(shù)，2012，34（1）：107-110.

［12］牛天林，王潔，杜燕波，等.戰(zhàn)時(shí)維修保障資源優(yōu)化調(diào)度的μPSO算法研究［J］.計(jì)算機(jī)工程與應(yīng)用，2011，38（9）：210-213.

［13］王曉娟.多目標(biāo)柔性作業(yè)車間調(diào)度方法研究［D］.武漢：華中科技大學(xué)，2011.

［14］張師，博華，車阿大，等.基于Pareto排序和混沌加權(quán)的多目標(biāo)項(xiàng)目調(diào)度［J］.計(jì)算機(jī)集成制造系統(tǒng)，2012，18（6）：1215-1222.

Multi-objective Scheduling Method of Wartime Equipment Maintenance Task Based on Pareto Sorting

WEN Hai-jun，LI Qing，SHAO Yan-jun，LIU Yong-jiang
（School of Mechanical and Power Engineering，North University of China1，Taiyuan 030051，China）

For the problem of weapons and equipment maintenance during wartime，this paper built a multi-objective scheduling model considering of the maximum completion time，delay time and maintenance unit load.In order to improve the diversity and convergence of solutions，a genetic algorithm combined Pareto sorting method and the niche technology was developed to solve the model.The fitness was evaluated by Pareto sorting and crowding distance，the weight coefficients was generated randomly by chaotic system，and the niche technology was used to improve the way of choice.The application results show that the proposed method can solve the multi-objective scheduling problem during equipment maintenance process effectively.

equipment maintenance，multi-objective scheduling，pareto sorting，hybrid genetic algorithm

TJ07

A

10.3969/j.issn.1002-0640.2017.11.31

1002-0640（2017）11-0146-05

2016-10-05

2016-11-07

山西省自然科學(xué)基金資助項(xiàng)目（2015011060）

溫海駿（1975- ），男，山西太原人，博士，講師。研究方向：制造過(guò)程監(jiān)測(cè)與控制、生產(chǎn)系統(tǒng)建模優(yōu)化與仿真等。