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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

2.2 問題描述與模型假設(shè)

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

(2)

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

Z=minT(Πopt(t))

(3)

(4)

(5)

(6)

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

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

3.1 基于聚類的任務(wù)分配

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

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

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

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

(7)

步驟3聚類的迭代更新。

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

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

(8)

(9)

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

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

2) 鄰域操作的設(shè)計。

步驟1基于分配階段所計算的mlkp(t)在Nlk(t)上的維修時間及排序結(jié)果，對應(yīng)得到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)作為操作目標(biāo)對象(如Plx(t)

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

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

(10)

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

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

4) 搜索策略與終止準(zhǔn)則。

相對于基本禁忌搜索中對問題元素的選取及鄰域操作目標(biāo)選取的隨機(jī)性，改進(jìn)的禁忌搜索方法中的約束主要體現(xiàn)在2個方面：一是在選取超載元素mlkp(t)時按照超載序列Π″lk進(jìn)行順序選取；二是在鄰域操作中依據(jù)mlkp(t)對應(yīng)序列P中的元素順序選取操作目標(biāo)對象。算法的終止條件是維修小組上的所有超載任務(wù)得到重新分配。

3.3 綜合求解流程

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

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

4 實例分析

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

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

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

表2 維修力量及其能力負(fù)載

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

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

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