考慮多屬性約束的戰(zhàn)時裝備維修任務動態(tài)調(diào)度

米巧麗,盧明章,李本威,王永生

(1.中國人民解放軍91049部隊，山東 青島 266100；2.海軍航空大學，山東 煙臺 264001)

1 引言

在現(xiàn)代信息化戰(zhàn)爭中，武器裝備的使用環(huán)境、作戰(zhàn)任務與保障條件等諸多不確定性因素,使得裝備故障的發(fā)生及維修保障力量的變化具有突發(fā)性、復雜性和頻率高等特點，而戰(zhàn)時對于裝備故障修復的時效性和維修效率要求更高。因此，戰(zhàn)時維修任務調(diào)度必須有效協(xié)調(diào)當前待調(diào)度的維修任務和可用的維修力量，以快速恢復裝備戰(zhàn)斗力為目標對維修任務與維修力量進行動態(tài)調(diào)度。

戰(zhàn)時維修任務調(diào)度相對于平時來說，所需考慮的約束條件更多、目標要求更高，因此研究難度也更大。針對戰(zhàn)時各種特殊情況下維修任務調(diào)度的特點，相關領域的學者從調(diào)度的屬性約束、調(diào)度模型的優(yōu)化目標及模型求解方法等方面展開了理論和方法研究。通過對現(xiàn)有研究成果的分析，可以發(fā)現(xiàn)：

1) 由于戰(zhàn)時維修任務的增加、維修力量的變化與維修時間等方面具有不確定性，因此需要根據(jù)戰(zhàn)場態(tài)勢與維修需求適時、動態(tài)地調(diào)整維修任務調(diào)度方案。如文獻[1]中針對維修任務出現(xiàn)的隨機性，在考慮維修時間不確定性前提下對維修任務進行優(yōu)化調(diào)度。文獻[2]考慮了戰(zhàn)時修理能力的變化，對伴隨修理任務進行動態(tài)調(diào)度研究。

2) 戰(zhàn)時維修任務繁雜、時效性要求高，且不同維修任務的緊急情況與重要程度不同，調(diào)度時需綜合考慮維修任務的分類、優(yōu)先級、維修時間等屬性。如文獻[3-5]中根據(jù)維修任務的重要程度、維修和等待時間等因素確定任務的優(yōu)先級，以優(yōu)先級為約束進行維修任務調(diào)度。文獻[6-7]在考慮維修專業(yè)分類基礎上構建了基于維修專業(yè)的調(diào)度模型。

3) 戰(zhàn)時維修力量相對平時復雜且多變，分配時需要綜合考慮維修力量的類別、調(diào)度時的維修資源與維修能力等屬性。如文獻[8,9]通過考慮戰(zhàn)時巡回維修力量的相關約束，規(guī)劃維修力量派遣路線，實現(xiàn)維修力量與任務的分配優(yōu)化。

4) 對于復雜的動態(tài)調(diào)度問題，通過構建實現(xiàn)對應目標的調(diào)度模型，采用智能算法可以有效提升模型的求解效率和調(diào)度效率。文獻[10-15]中，在構建的單目標或多目標調(diào)度模型基礎上，通過運用和改進遺傳算法、蟻群算法、粒子群算法等對模型進行求解，提高求解效率的同時實現(xiàn)了維修任務的優(yōu)化調(diào)度。

由上述分析可知，目前相關研究文獻中針對戰(zhàn)時維修任務與維修力量均出現(xiàn)突變的動態(tài)調(diào)度研究較少，且大部分文獻在考慮調(diào)度的屬性約束時側重于考慮維修任務或維修力量單方面的屬性約束，與戰(zhàn)時實際情況存在一定的差距。因此，本文中擬針對戰(zhàn)時維修任務及維修力量均發(fā)生變化的復雜情況，綜合考慮維修任務、維修力量的專業(yè)分類、優(yōu)先級和能力負載等屬性約束，以快速、有效恢復裝備戰(zhàn)斗力為目標進行動態(tài)調(diào)度，以此提高維修任務調(diào)度應對戰(zhàn)場環(huán)境與保障要素隨機變化的響應能力。

2 分階段的動態(tài)調(diào)度模型構建

2.1 戰(zhàn)時維修任務動態(tài)調(diào)度需求

戰(zhàn)時維修任務動態(tài)調(diào)度是在故障裝備隨時出現(xiàn)、維修時間和維修能力有限且可能出現(xiàn)變化的情況下，將故障裝備所產(chǎn)生的維修任務分配到適合的維修力量，并確定各維修力量所承擔的維修任務的維修順序、修復時間及修復狀態(tài)，同時還需要根據(jù)需求變化進行動態(tài)調(diào)整，使戰(zhàn)斗力得到最及時有效的恢復?？梢?，維修任務動態(tài)調(diào)度主要包含2個階段：一是在出現(xiàn)故障后，依據(jù)維修任務的需求及維修力量的能力,將維修任務分配到對應滿足能力需求的維修力量上，在此簡稱為分配階段；二是依據(jù)維修任務的優(yōu)先級及資源需求等條件，對每個維修力量上所分配維修任務的維修順序、時間和狀態(tài)等進行具體規(guī)劃，簡稱為規(guī)劃階段。

戰(zhàn)時裝備的維修力量主要包括伴隨維修、機動巡回維修以及定點維修等3類維修機構，這3類維修機構的維修能力與備件資源各有特點。通過調(diào)研與統(tǒng)計分析可知，依據(jù)裝備故障部位與類型，針對性地配置專業(yè)對口的維修人員及對應的專業(yè)器材進行故障維修，可有效地提高維修效率和維修資源的利用率。因此，在進行動態(tài)調(diào)度時，首先對維修任務依據(jù)專業(yè)分類得到初始的專業(yè)任務集，并將維修機構及對應配置的維修資源整合，并劃為若干專業(yè)維修小組。由此，在分配階段可將維修任務快速分配到對應專業(yè)的維修小組上，規(guī)劃階段則對每個專業(yè)維修小組上所分配的維修任務進行進一步調(diào)整，在滿足約束條件下獲得最佳的調(diào)度方案。

2.2 問題描述與模型假設

在靜態(tài)維修任務調(diào)度的基礎上，動態(tài)調(diào)度重點考慮維修過程中維修任務、維修力量出現(xiàn)變化后對任務調(diào)度的影響。當出現(xiàn)維修任務與維修力量變化時，需要對待調(diào)度任務與新增任務在當前維修力量下進行重新調(diào)度。在調(diào)度過程中，任務的分配與規(guī)劃均以維修任務集為基本操作對象，而每個任務集的任務數(shù)量及操作所需時間均不同。根據(jù)調(diào)度的階段劃分，對應構建待調(diào)度任務池TP1、分配任務池TP2、待規(guī)劃任務池TP3、規(guī)劃任務池TP4、已調(diào)度任務池TP5。當出現(xiàn)新任務及維修力量變化時，更新TP1，重新調(diào)用任務調(diào)度算法，更新TP2、TP3、TP4，由此降低任務調(diào)度的復雜度。

為明確動態(tài)調(diào)度過程，做出如下約定：

1) 維修任務不可中途取消，如遇到需要取消的維修小組正在執(zhí)行某一維修任務的情況，則將該維修任務未完成的任務量按原優(yōu)先級進行重新調(diào)度；

2) 維修小組上維修任務的分配按照優(yōu)先級高的任務優(yōu)先，優(yōu)先級相同以維修時間短的任務優(yōu)先的原則進行；

3) 每個專業(yè)維修小組可對同一專業(yè)的若干維修任務進行操作，但每項維修任務不能同時由2個維修小組維修；

4) 每個維修任務的維修時間為維修等待、故障件送修、故障維修等時間的總和；

5) 出現(xiàn)維修任務的增加及維修小組增減等變化時，均按照專業(yè)分類進行調(diào)度，其他沒有變化的專業(yè)維修任務和維修小組無需進行重新調(diào)度；

6)如某一專業(yè)維修小組臨時取消，則該小組上未完成的維修任務需要重新調(diào)度，其他專業(yè)的維修小組及維修任務保持原來的調(diào)度安排。

2.3 動態(tài)調(diào)度模型的構建

假設在t時刻裝備出現(xiàn)新故障或維修小組出現(xiàn)增減，通過對維修任務進行專業(yè)分類，得到初始維修任務集為：

(1)

記t時刻專業(yè)l下待調(diào)度任務總數(shù)為I(t)，I(t)=I0(t)+Q(t)。將式(1)中的任務合并后，綜合任務優(yōu)先級(從高到低)與維修時間(從小到大)對任務進行排序，得到專業(yè)任務集為Ml(t)={Mli(t),i=1,2,…,I(t)}。

記t時刻專業(yè)維修小組集合為N(t)={Nlk(t),k=1,2,…,K(t)}。分配階段的任務即將Mli(t)分配到對應的Nlk(t)上，得到分配方案為：

Π1(t)=[xlik(t)]I(t)×K(t)

(2)

式中: 專業(yè)l下的第i個任務被分配到第k個維修小組時，xlik(t)=1，反之xlik(t)=0。

Z=minT(Πopt(t))

(3)

(4)

(5)

(6)

其中，式(4)表示每個維修任務只能由一個維修小組進行維修。式(5)表示所有的維修任務均需要得到維修。記Mli(t)在Nlk(t)上的維修時間為tlik(t)，Nlk(t)的最大能力負載(在此用可承擔的最大維修時間衡量)為Qlk(t)，式(6)表示每個維修小組所承擔的維修任務不能超出其能力負載。

3 動態(tài)調(diào)度模型的求解

3.1 基于聚類的任務分配

任務分配的過程就是維修任務的需求與維修機構能力匹配與優(yōu)化的過程。聚類是將一組對象逐步分解為若干個相似度較高的類或簇的過程[16]。對于維修任務的分配階段，可以看作將需求相似的任務與能力最匹配的維修小組逐步聚類的過程。將同專業(yè)的維修任務Mli(t)與維修小組Nlk(t)作為聚類對象。聚類距離用于衡量任務的需求與維修小組能力之間的匹配程度。聚類距離越小，說明匹配程度越低?；诰垲惖娜蝿辗峙溥^程主要包括以下幾個步驟：

步驟1將承擔維修任務的K(t)個維修小組Nlk(t)作為聚類中心。

步驟2非中心與中心的聚類距離用任務Mli(t)在維修小組Nlk(t)上的維修時間tlik(t)衡量，即聚類距離表示為dlik=tlik。

通過計算每個非中心對象(任務Mli(t))與每個聚類中心(維修小組Nlk(t))之間的距離dlik，可構造距離矩陣Dl為：

(7)

步驟3聚類的迭代更新。

將矩陣Dl中每一行元素由小至大排序，從第1行(第1個任務)開始，選取該行的最小值并入該值對應的聚類中心，即如第1行的最小值為dl1k≥0，則將Ml1(t)并入聚類中心Nlk(t)所在的簇，更新各聚類中心。然后依次選取每行最小值進入對應簇，直至最后1行。

3.2 基于約束禁忌搜索的任務規(guī)劃

(8)

(9)

當Nlk(t)上任務為串并混聯(lián)時，將并聯(lián)的所有任務視為一個整體，時間設為其中的最大值，然后再依據(jù)串行關系對時間求和。

1) 初始解與適配值函數(shù)的確定。

2) 鄰域操作的設計。

步驟1基于分配階段所計算的mlkp(t)在Nlk(t)上的維修時間及排序結果，對應得到mlkp(t)按維修時間從小到大的維修小組序列P。易知P的第1個元素為P[0]=Nlk(t)，選取P的第2個元素P[1]=Nlx(t)，其中，x≠k,1≤x≤K(t)。

步驟2判斷Nlx(t)是否超載。如Plx(t)≥Qlx(t)，依次向后選取直至不超載元素Nly(t),(x

步驟3選取不超載元素Nly(t)作為操作目標對象(如Plx(t)

步驟4判斷是否到達p[K(t)-1]。如沒有則按順序選取Nlx(t)或Nly(t)的下一個元素，進行插入操作；如到達，則結束該次鄰域操作，更新變動向量的分配方案。

max(Tlk(Πl(fā)k′(t)),Tly(Πl(fā)y′(t)))

(10)

通過計算所有鄰域解對應的適配值差,并依據(jù)適配值差從小到大對鄰域解進行排序，選取適配值差最小的鄰域解作為當前解，在接下來的鄰域操作中即被視為禁忌對象，進入禁忌表中。

3) 禁忌規(guī)則與藐視準則。

4) 搜索策略與終止準則。

相對于基本禁忌搜索中對問題元素的選取及鄰域操作目標選取的隨機性，改進的禁忌搜索方法中的約束主要體現(xiàn)在2個方面：一是在選取超載元素mlkp(t)時按照超載序列Π″lk進行順序選?。欢窃卩徲虿僮髦幸罁?jù)mlkp(t)對應序列P中的元素順序選取操作目標對象。算法的終止條件是維修小組上的所有超載任務得到重新分配。

3.3 綜合求解流程

所有的待調(diào)度任務只有在經(jīng)過分配及規(guī)劃操作后，到達已調(diào)度任務池后才能完成整個調(diào)度周期。而當時刻t出現(xiàn)新的維修任務時，將新的維修任務經(jīng)過初始專業(yè)分類后，將其與對應的專業(yè)下現(xiàn)存待調(diào)度的任務共同存儲于待調(diào)度任務池，通過觸發(fā)分配與規(guī)劃時間窗口，對所有待調(diào)度任務進行重新調(diào)度。在完成現(xiàn)階段的維修任務調(diào)度后，判斷下一個時刻是否出現(xiàn)新任務，如出現(xiàn)新任務，則將時間窗口滾動到下個時刻t+Δt，進行重新調(diào)度。根據(jù)上述分析，維修任務動態(tài)調(diào)度模型求解算法流程如圖1所示。

圖1 維修任務動態(tài)調(diào)度模型求解流程框圖Fig.1 Solution flow of flexible task scheduling

4 實例分析

以某型導彈裝備戰(zhàn)時出現(xiàn)并發(fā)故障情況為例，通過對各類故障原因及維修策略的分析，將每個故障相應分解為基本維修任務集合。任務集中各維修任務的任務量與優(yōu)先級如表1所示。

表1 維修任務的任務量與優(yōu)先級

依據(jù)參戰(zhàn)裝備的維修策略及相應的維修保障組織設置，將現(xiàn)有的維修力量進行專業(yè)分類后，其能力負載(維修時間/h)如表2所示。

表2 維修力量及其能力負載

通過分析該型導彈裝備維修策略、各維修任務的類型、能力需求與維修小組職能范疇、能力的對比，得出距離矩陣為：

假定每個維修小組能夠連續(xù)執(zhí)行維修任務，中間無需停休。通過維修任務分配，得到初始調(diào)度方案。初始調(diào)度方案中所有維修任務的完成時間為13.7 h。在初始調(diào)度方案的基礎上，采用Matlab 7.1編程實現(xiàn)改進禁忌搜索的任務規(guī)劃算法，以初始調(diào)度方案為初始解，實現(xiàn)維修任務調(diào)度方案的規(guī)劃調(diào)整。為驗證本文中模型及算法的正確性及求解性能，應用精確求解的匈牙利法，對上述案例中的維修任務優(yōu)化調(diào)度模型進行求解，本文中方法求解的最優(yōu)值為與匈牙利法的精確求解最優(yōu)值一致，均為10.9 h，由此說明了本文中所建模型的正確性及所提出的模型求解方法對于維修任務優(yōu)化調(diào)度模型求解的有效性。

為驗證本文中的算法對維修任務動態(tài)調(diào)度的求解效果及效率，假設在當t=5時，導彈裝備突發(fā)新的故障，并且維修分隊N13被臨時調(diào)離。假定執(zhí)行過程的維修任務不會中途停止。因此，維修小組數(shù)量減少1，同時，N13上正在執(zhí)行的任務及已分配的任務需要被重新調(diào)度。對新產(chǎn)生的故障進行分析，按專業(yè)分解為基本維修任務集，與現(xiàn)存的任務進行重新調(diào)度。為對比本文中的動態(tài)調(diào)度方案，同時采用2個傳統(tǒng)調(diào)度方案進行分析。方案1中采取先到先維修的方法，方案2中采取優(yōu)先級高先維修的方法，方案3為本文中考慮的多屬性約束動態(tài)調(diào)度方案。通過調(diào)用分配算法得出初始調(diào)度方案，在此基礎上分別設置規(guī)劃階段算法參數(shù)。通過求解，方案1所有任務完成時間為54.6 h，方案2任務完成時間為49.7 h，方案3最優(yōu)目標值為37.2 h。其中，方案3的維修任務調(diào)度方案如圖2所示(圖2中數(shù)字編號代表“專業(yè)-任務序號”)。

圖2 維修任務動態(tài)調(diào)度甘特圖Fig.2 Gantt chart of dynamic optimization scheduling for maintenance tasks

為驗證模型在多次復雜動態(tài)變化下的適用性，在某型導彈維修保障過程仿真中，進行50次隨機故障擾動，增加維修任務數(shù)量，設定4個專業(yè)，每個專業(yè)維修任務產(chǎn)生概率分別為0.15，0.38，0.27，0.20，在每個維修小組維修時間取值范圍為[2.5,25.5]，且每次隨機增加或減少一個維修小組。每次擾動后對新產(chǎn)生及原待調(diào)度的維修任務進行重調(diào)度，對維修小組的選擇及維修時間進行隨機抽樣。同樣采用3種調(diào)度方案進行動態(tài)調(diào)度，對3種方案進行仿真計算，所得目標函數(shù)值即所有維修任務完成時間如圖3所示。

為驗證本文中考慮的分階段動態(tài)調(diào)度方法及改進的禁忌搜索方法的求解性能，在不考慮維修任務關聯(lián)性的基礎上，同時采用迭代啟發(fā)式算法中的NEH方法、經(jīng)典禁忌搜索方法對相同數(shù)據(jù)擾動下的維修任務進行重調(diào)度與求解，3種方法在同一計算機上的運行時間如圖4所示。

由圖3可知，相對于傳統(tǒng)的和只考慮單一約束條件的維修任務調(diào)度方案，采用本文中動態(tài)調(diào)度方法的維修任務完成時間平均提前約30%，且隨著重調(diào)度次數(shù)的增加，優(yōu)勢更加顯著。圖4表明，改進的禁忌搜索任務規(guī)劃方法相比其他2種方法在求解效率上具有明顯的優(yōu)勢。

圖3 不同方案的目標函數(shù)值曲線Fig.3 Objective function values under different schemes

圖4 不同方法的運行時間曲線Fig.4 Running time of different methods

5 結論

1) 在戰(zhàn)時裝備維修任務調(diào)度研究中，同時考慮維修任務與維修力量的變化更貼近戰(zhàn)時的實際情況與需求；

2) 相對于傳統(tǒng)的先到先維修與單純只考慮優(yōu)先級的調(diào)度方案，綜合考慮維修任務的專業(yè)分類、優(yōu)先級、任務量及維修小組的專業(yè)和負載等各方面屬性約束的調(diào)度方案，有效提高了將維修任務匹配到具有對應維修能力的維修力量的準確度和速度，明顯縮短了維修任務完成時間；

3) 在發(fā)生維修任務和維修力量變化的時刻，進行維修任務重調(diào)度，可以將復雜的動態(tài)問題簡化為每個變化時刻的靜態(tài)調(diào)度問題，并生成近實時的調(diào)度方案；

4) 實例表明，在考慮多屬性約束的基礎上，將維修任務的動態(tài)調(diào)度過程劃分為分配和規(guī)劃2個階段，可以降低調(diào)度過程的復雜性和冗余性，提高維修任務的調(diào)度效率；

5) 實例驗證了改進禁忌搜索方法在維修任務動態(tài)調(diào)度模型求解中的有效性和可行性，且在實現(xiàn)全局優(yōu)化的同時，能夠保證針對性有效搜索范圍及相對較少的計算量，模型的求解效率得到提高。