基于改進PSO 的裝備維修任務(wù)調(diào)度方法*

呂亞娜，田永林，杜秀麗

（大連大學(xué)通信與網(wǎng)絡(luò)重點實驗室，遼寧 大連 116622）

0 引言

裝備維修的快速性對維修資源、維修人員、維修經(jīng)費、維修時間等的合理分配提出了更高要求，開展裝備維修任務(wù)調(diào)度方法研究，對提高參戰(zhàn)裝備的完好率與戰(zhàn)斗恢復(fù)率，為取得戰(zhàn)爭最終勝利具有重要意義。

裝備維修包含了使裝備保持、恢復(fù)或改善到規(guī)定狀態(tài)的全部活動，其貫穿于戰(zhàn)場服役的全過程，其核心在于裝備維修任務(wù)調(diào)度方法。近年來，學(xué)術(shù)界開展了大量的裝備維修任務(wù)調(diào)度方法研究，并取得了一定的成果。文獻［1］分析了戰(zhàn)場裝備維修任務(wù)特點，以故障裝備盡快恢復(fù)作戰(zhàn)所需狀態(tài)為目標(biāo)，提出了動態(tài)維修任務(wù)調(diào)度方法。文獻［2］建立了用于評估維修任務(wù)調(diào)度策略的定點修理過程仿真模型，給出了維修任務(wù)執(zhí)行模式、維修任務(wù)選擇及維修資源分配中較好的策略。文獻［3］提出了一種基于排隊論的裝甲裝備故障維修任務(wù)調(diào)度方法，實現(xiàn)了任務(wù)調(diào)度的最優(yōu)化配置。文獻［4］分析了裝備維修作業(yè)調(diào)度工序并行性的特點，建立以最小維修任務(wù)時間為目標(biāo)的作業(yè)調(diào)度模型，并設(shè)計了基于遺傳算法的模型求解算法。文獻［5］考慮了維修任務(wù)調(diào)度中時間不確定因素，建立了一種裝備維修任務(wù)調(diào)度模型，并采用改進的最大-最小螞蟻系統(tǒng)對模型求解。文獻［6］提出了一種伴隨修理裝備維修任務(wù)調(diào)度的多目標(biāo)動態(tài)調(diào)度方法，并設(shè)計了基于改進非支配排序遺傳算法（NSGA-II）對模型求解。文獻［7］提出了一種基于貪婪啟發(fā)式的本地搜索算法（GHLSA）用于裝備多組件的系統(tǒng)維護，旨在最大程度地減少停機時間。文獻［8］考慮了裝備剩余壽命、重要性和距離等因素，提出了一種基于裝備剩余壽命的最優(yōu)調(diào)度模型。

以上研究對于裝備維修任務(wù)調(diào)度問題具有一定借鑒，但方法適應(yīng)于特定場景，且求解算法效率不高，易造成維修時間過長、維修成本過高等不足。因此，尋求一種更加合理有效的裝備維修任務(wù)調(diào)度方法迫在眉睫。本文以戰(zhàn)場環(huán)境下故障裝備為研究對象，構(gòu)建以武器裝備重要程度、維修時間、維修成本為目標(biāo)的維修任務(wù)調(diào)度模型，并設(shè)計了改進的粒子群算法對模型進行求解，該方法提高了裝備維修任務(wù)調(diào)度方法的有效性，可為戰(zhàn)場維修任務(wù)調(diào)度提供一定的參考。

1 裝備維修任務(wù)調(diào)度模型

1.1 問題描述

裝備維修任務(wù)調(diào)度是確保戰(zhàn)時裝備維修保障工作能夠合理有效進行的重要組成部分，相對于一般維修任務(wù)而言，戰(zhàn)時維修任務(wù)在維修復(fù)雜度、維修方法、維修時限性、維修順序及裝備故障發(fā)生范圍和頻率方面都有很大不同。戰(zhàn)時裝備維修任務(wù)調(diào)度的最終目標(biāo)是能夠使戰(zhàn)損裝備盡快恢復(fù)戰(zhàn)斗力，及時投入戰(zhàn)斗序列。

設(shè)有M 個維修保障分隊（m=1，2，3，…，M）對N個戰(zhàn)損裝備（n=1，2，3，…，N）進行維修，裝備故障類型有L 種（l=1，2，3，…，L），每個維修保障分隊可維修K 個戰(zhàn)損裝備（k=1，2，3，…，K），每種故障類型裝備有S 個（s=1，2，3，…，S），假設(shè)：

1）一臺戰(zhàn)損裝備同一時間發(fā)生故障的故障類型不變。

2）一臺戰(zhàn)損裝備由一個維修分隊進行維修。

3）維修分隊通過調(diào)度后維修中途不再更換其他分隊，直至維修任務(wù)結(jié)束。

4）故障發(fā)生時維修分隊即接收相關(guān)維修任務(wù)指令，忽略不計維修人員在不同戰(zhàn)損裝備之間的走動時間。

戰(zhàn)時裝備發(fā)生故障后，保障部門接收相關(guān)維修指令，維修輔助決策者對維修人員進行任務(wù)調(diào)度，之后不同分隊的維修人員依據(jù)任務(wù)部署對戰(zhàn)損裝備進行維修，維修任務(wù)調(diào)度示意圖如圖1 所示。

圖1 武器裝備維修任務(wù)調(diào)度示意圖

1.2 模型建立

根據(jù)戰(zhàn)時裝備維修的特點及裝備維修保障的相關(guān)要求，本文提出的戰(zhàn)時裝備維修任務(wù)調(diào)度問題重點考慮裝備重要程度、維修時間、維修成本等指標(biāo)。

1）裝備重要程度。不同作戰(zhàn)裝備，如指揮裝備、信號裝備、后勤保障裝備等的重要程度不同，重要程度高的裝備具有更高的優(yōu)先級，往往先對優(yōu)先級較高的裝備進行維修，再對優(yōu)先級較低的裝備進行維修。第n 個裝備重要程度pn可由戰(zhàn)損裝備可維修性βn1、裝備對作戰(zhàn)結(jié)果影響程度βn2以及作戰(zhàn)任務(wù)緊迫性βn3構(gòu)成，ei為指標(biāo)權(quán)重，可根據(jù)戰(zhàn)損裝備盡快恢復(fù)戰(zhàn)斗力的重要程度確定。

2）維修時間。指維修分隊從開始維修戰(zhàn)損裝備到維修結(jié)束所需時間，最短的維修時間可使較多的火力裝備盡快參與戰(zhàn)斗。

3）維修成本。指裝備從受損到恢復(fù)戰(zhàn)斗力的停機成本，主要包括了裝備維修耗材、維修運輸及維修管理等相關(guān)費用，合理支配成本支出有助于保障部隊維修更多的戰(zhàn)損裝備。

以裝備重要程度、維修時間及維修成本為指標(biāo)，建立裝備維修任務(wù)調(diào)度模型如下：分別為3 個指標(biāo)權(quán)重值；xn為維修任務(wù)調(diào)度標(biāo)志，若對其進行維修，則xn=0，反之，xn=1；tmk表示第m 個維修分隊對第k 個戰(zhàn)損裝備的維修時間；tls表示第l 種類型裝備中第s 個戰(zhàn)損裝備的維修時間；cls表示第l 種類型裝備中第s 個戰(zhàn)損裝備從發(fā)生故障到維修結(jié)束單位時間損失成本。約束1 表示裝備重要程度介于［0，1］之間；約束2 表示不同維修分隊中最大維修時間需小于最大保障時間T；約束3 表示維修總時間的平衡性。

式（2）表示維修任務(wù)調(diào)度總目標(biāo)最優(yōu)；式（3）表示未維修裝備重要程度盡可能低；式（4）表示裝備維修工作結(jié)束總時間最短；式（5）表示維修任務(wù)總成本盡可能最低。

為避免維修時間及維修成本數(shù)據(jù)量綱的影響，需對多目標(biāo)進行去量綱化處理。

2 基于改進PSO 的裝備維修任務(wù)調(diào)度算法

2.1 改進PSO 優(yōu)化算法

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是由美國電氣工程師Eberhart 和社會心理學(xué)家Kennedy［9］在1995 年最先提出。粒子群算法與其他算法相比具有結(jié)構(gòu)簡單、參數(shù)設(shè)置少、易于操作、搜索速度快等特點，但同時也存在精度低、易發(fā)散、易陷入局部最優(yōu)等缺點。本文提出的改進粒子群算法將從慣性權(quán)重w，學(xué)習(xí)因子c1、c2兩方面入手，改進后的w、c1、c2調(diào)整公式為：

其中，t 為算法當(dāng)前迭代次數(shù)，tmax為算法的最大迭代次數(shù)，A、B、C、D 為常數(shù)，由常用測試函數(shù)及已有的學(xué)習(xí)因子調(diào)整方法可得A=0.5，B=1，C=0.5，D=2.2。對于慣性權(quán)重的調(diào)整方法，專家學(xué)者對其進行了深入研究，文獻［10］表明，當(dāng)wmin=0.4，wmax=0.9 時，粒子群算法能夠快速收斂。改進后的粒子速度更新公式及位置更新公式如下所示：

2.2 改進PSO 算法流程

圖2 改進粒子群算法流程圖

本文提出的基于改進粒子群的裝備維修任務(wù)調(diào)度方法流程如圖2 所示。其主要步驟描述如下：

Step1：初始化種群：初始化種群規(guī)模sizepop，最大迭代次數(shù)tmax；設(shè)置粒子最大更新速度Vmax，最小更新速度Vmin，最大位置邊界Xmax和最小位置邊界Xmin，根據(jù)戰(zhàn)場裝備維修特點隨機產(chǎn)生粒子初始速度和位置。

Step2：計算粒子適應(yīng)度值：根據(jù)式（2）計算每個粒子的適應(yīng)度值，并將其作為各自粒子個體最優(yōu)值pbest，繼而比較所有粒子的個體最優(yōu)值，選取出最小值作為全局最優(yōu)值gbest。

Step3：更新慣性權(quán)重、學(xué)習(xí)因子、粒子速度與粒子位置：根據(jù)式（8）～式（11）分別對慣性權(quán)重、學(xué)習(xí)因子、粒子速度和位置進行更新，更新后的粒子速度與位置約束如下：

表3 各裝備重要程度

式（12）控制粒子的飛行速度，不但可避免因粒子速度過小算法陷入局部最優(yōu)，而且同時避免粒子速度過大超出種群區(qū)域；式（13）約定了粒子的可行解區(qū)域，確保每次搜尋結(jié)果的可用性。

Step4：更新個體極值與全局極值：根據(jù)式（2）計算出粒子個體適應(yīng)度值，將其與個體極值，全局極值作比較，由比較結(jié)果更新個體極值pbest，全局極值gbest。

Step5：比較當(dāng)前迭代次數(shù)t 與最大迭代次數(shù)tmax，若達到最大迭代次數(shù)tmax，則輸出粒子最優(yōu)位置，算法結(jié)束，得出最優(yōu)裝備維修調(diào)度序列，否則，轉(zhuǎn)向Step3。

3 實例驗證

以某次戰(zhàn)場環(huán)境下裝備維修保障活動為例，假設(shè)有4 個維修保障部隊，可對4 種類型的戰(zhàn)損裝備進行維修，各待維修裝備的故障類型、維修時間、重要程度及維修成本如表1～表4 所示，時間以單位時間為準，不同維修保障分隊最大保障時間T=25。

綜合考慮本文提出的武器裝備重要程度、維修時間及維修成本3 個指標(biāo)，采用層次分析法對各目標(biāo)權(quán)重進行確定，各目標(biāo)函數(shù)兩兩比較矩陣如表5所示，由表5 可知，CR=0.003 6<0.1，通過一致性檢驗，故，f1，f2，f3，的權(quán)重分別為0.647 9，0.229 9，0.122 2。對本文算法與基本粒子群算法及線性遞減慣性權(quán)重粒子群算法進行仿真實驗，其中參數(shù)設(shè)置為：種群規(guī)模sizepop，最大迭代次數(shù)tmax=200，適應(yīng)度收斂曲線如下頁圖3 所示，相比于基本粒子群算法與線性遞減慣性權(quán)重粒子群算法，本文算法收斂速度快，大致在20 代即收斂至最優(yōu)且精度較高，不易陷入局部最優(yōu)。圖4～圖6 分別為基本粒子群算法、線性遞減慣性權(quán)重粒子群算法，以及本文算法所對應(yīng)的裝備維修任務(wù)調(diào)度甘特圖。

表1 各裝備故障類型

表2 各類型裝備由各維修分隊維修時（單位時間）

表4 各類型裝備單位時間損失成本（元）

表5 各目標(biāo)函數(shù)兩兩比較判斷矩陣

圖3 適應(yīng)度收斂曲線

圖4 基本粒子群算法裝備維修任務(wù)調(diào)度甘特圖

圖5 線性遞減慣性權(quán)重粒子群算法裝備維修任務(wù)調(diào)度甘特圖

圖6 改進粒子群算法裝備維修任務(wù)調(diào)度甘特圖

表6 為以上3 種算法得出的裝備維修任務(wù)調(diào)度方案下維修總時間及維修成本對比表，可以看出，相比基本粒子群算法及線性遞減慣性權(quán)重粒子群算法，本文算法下維修調(diào)度總時間更少，維修成本更低。因此，采用本文算法對裝備維修任務(wù)進行調(diào)度，可有效提高裝備維修效率，節(jié)省維修成本，有助于故障裝備及時投入戰(zhàn)斗序列，從而取得戰(zhàn)爭的最后勝利。

表6 不同粒子群算法維修時間、維修成本對比

4 結(jié)論

針對作戰(zhàn)裝備維修任務(wù)調(diào)度問題，建立了以裝備重要程度、維修時間及維修成本為目標(biāo)的維修任務(wù)調(diào)度模型，設(shè)計了基于改進粒子群算法的維修任務(wù)調(diào)度模型求解方法，實例驗證了該改進算法的有效性。今后將進一步結(jié)合戰(zhàn)場裝備維修任務(wù)調(diào)度典型需求，細化模型參數(shù)，提高裝備維修任務(wù)調(diào)度方法的適應(yīng)性。