考慮維修效率的油料裝備維修任務分配問題研究

文/ 陸思錫 周慶忠 熊 彪

?

考慮維修效率的油料裝備維修任務分配問題研究

文/ 陸思錫 周慶忠 熊 彪

摘 要：油料裝備維修效率對油料裝備戰時保障能力具有重要影響。本文針對在油料裝備維修力量有限的條件下如何通過合理的任務分配，使完成油料裝備維修任務的總效率最高的問題，建立了考慮維修效率的油料裝備戰時維修任務分配模型，并針對可能出現的情況對模型進行了討論，利用匈牙利算法對模型進行了求解。通過模型的運用表明，考慮維修效率的油料裝備戰時維修模型可以更好地對維修任務的分配進行優化，確保油料裝備總維修效率最高。

關鍵詞：油料裝備；維修；效率；決策

信息化條件下，為了使油料裝備維修能夠有效進行，必須對油料裝備維修任務進行高效、合理地分配，尤其是油料裝備易暴露，損壞率高，維修任務大，經常會面臨因維修力量不足，而使戰損油料裝備無法及時恢復保障能力的情況。因此，在油料裝備維修力量十分有限的戰場環境條件下，如何對油料裝備維修力量進行合理地分配，使完成各項油料裝備維修任務的總效率最高，是需要迫切解決的問題。

1.油料裝備戰時維修任務分配模型建立

1.1油料裝備戰時維修任務分配問題的數學描述

假設在油料裝備維修任務中，有m個油料裝備維修小組，要完成n項維修任務，且不同的維修小組的維修保障能力不完全相同，第i個小組完成第j項油料裝備維修任務的效率為eij( i ,j∈ [1, n ])，且≥0，則油料裝備戰時維修決策的最終目標是通過對維修任務的分配，使完成n項油料裝備維修任務的總效率最高，即油料裝備的維修耗時最少。為了達到維修耗時最少的目標，引入0～1決策變量pij，當分配第i個維修小組完成第j項任務時，pij=1，否則pij=0。

1.2模型建立

由于受到戰時各種復雜因素的影響，在油料裝備維修過程中可能出現油料裝備維修力量不足等情況，因此，模型的建立分別基于不同的情況來考慮。

①m＞n，且每個維修小組僅分配一項維修任務，第j項任務可由aj個小組共同完成，則此時的維修任務分配模型可描述為：

上述模型中待求的未知數為aj。

②m＜n，每項任務僅由一個維修小組來完成，但是第i個小組可完成bi項任務，此時的決策模型可描述為：

上述模型中待求的未知數為bi。

③每個維修小組最多可分配一項維修任務，且每項任務只由一個維修小組完成，則此時的任務分配模型可描述為：

2.油料裝備戰時維修任務分配模型求解

從上述建立的維修任務分配模型可以看出，油料裝備戰時維修任務分配問題實質是一種規劃問題，求解規劃問題的方法較多，有表上作業法、單純形法、匈牙利算法等，但表上作業法和單純形法對于考慮維修效率的任務分配模型求解比較復雜，因此，本文采用更為有效的匈牙利算法對模型進行求解。

2.1匈牙利算法基本原理

匈牙利算法的基本原理是構造效益矩陣，從效益矩陣出發來確定任務分配的最優方案。利用匈牙利算法解決油料裝備維修任務分配問題時，要求m=n，即維修任務與維修小組的數量相同。對于上述三種情況的模型，當m=n時，可直接利用匈牙利算法進行求解，在效率矩陣中尋找分布在不同行、不同列的n個獨立的0元素，并且使這些元素的和最小，對于其它兩種情況的模型則需構造廣義效益矩陣來求解[1]。廣義效益矩陣就是在效益矩陣的基礎上構造虛擬的維修任務，或虛擬的油料裝備維修小組來使維修任務和維修小組的數量相等，來達到利用匈牙利算法求解的要求，但不影響真實的油料裝備維修任務分配。

2.2模型求解方法

①當m＞n時，可以先安排一個維修小組來完成一項維修任務，則剩下m-n個維修小組，可將其剩下的每個小組分配給n項維修任務中的任何一個，則每項任務都有另外的m-n個虛擬任務，且每個維修小組完成虛擬任務的效益值完全一樣，則維修任務數就變為n（m-n+1）個，多于維修小組數量。假設還有n （m-n+1）-m個小組，完成任何維修任務的效益都最小，則可構造廣義效益矩陣：

式中，第一行有m-n+1個E={ eij}m× n；B的值是E中每列效益最小的數，為（m-n）（n-1）行n列矩陣。則當m＞n時，決策模型的解就可根據廣義效益矩陣A所對應的最優解[pij]n( m- n + 1)×n ( m- n + 1)前m行中等于1的元素來確定。

②當m＜n時，先給每個維修小組安排一項維修任務，則剩下n-m項維修任務，每項任務可由m個維修小組完成，假設每個小組都存在另外n-m個與其完全相同的虛擬小組，這些虛擬小組完成每項任務的時間完全一樣。則維修小組數量就達到n （n-m+1），可確保每項維修任務有且僅有一個維修小組來完成[2]。假設還有m（n-m+1）-n項虛擬任務，其由任何一個維修小組完成的效益值都最小，則可構造廣義效益矩陣：

式中，第一行有n-m+1個ET，BT為m行（n-m）（m-1）列矩陣。則當m＜n時，決策模型的解就可根據廣義效益矩陣A所對應的最優解[pij]m( n- m + 1)× m ( n- m + 1)前n列中等于1的元素來確定。

③當每個維修小組最多可分配一項維修任務，且每項任務只由一個維修小組完成時，可分三種情況考慮。若m=n，則可利用匈牙利算法直接求解[3]；若m＞n，即任務少，則添加虛擬維修任務，在效率矩陣添加m-n列0元素，構成m×m的效率矩陣；若m＜n，即維修小組少，則添加虛擬維修小組，在效率矩陣添加m-n行0元素，構成n×n的效率矩陣。

3.油料裝備戰時維修任務分配模型應用

某次油料保障中，需要對油料裝備進行快速搶修以恢復其油料保障能力。現有5項不同的油料裝備維修任務，其中任務R1非常緊急，對維修時間要求較高，R2、R5兩項任務較為重要，對維修時間有一定要求，剩余兩項任務對時間要求不高，目前可同時對上述任務進行維修的油料裝備維修小組有4個，為了保證油料裝備的維修效率，每個維修小組最多可分配一項維修任務，且每項任務只由一個維修小組完成。各維修小組完成不同任務所需時間的效率值如下表所示，下面對上述油料裝備維修任務的分配進行分析。

各油料裝備維修小組維修效率值

對上述問題的具體情況進行分析可知，該問題屬于所建立的決策模型中的第3類問題，由于R1非常緊急，優先對任務R1進行分配，根據上表中的數據得到效率矩陣E：

則E1=[2.5 4.2 3.0 3.5]T，因此，對于維修任務R1來說，維修小組V1完成該任務的效率最高，首先將油料裝備維修任務R1分配給V1。

由于每項任務只由一個維修小組完成，因此，在考慮剩余任務時，不考慮V1，剩余3個維修小組完成R2、R5兩項任務的效率矩陣為：

根據 中效率值可知，R2、R5任務的分配方案是： R2→V2，R5→V4。

最后對剩下的任務進行分配。由于只剩下維修小組V3，其對R3、R4的效率矩陣為E3=[1.0 2.9]，因此應將R3分配給V3。對于最后剩下任務R4，由于各維修小組已全部分配任務，則需等待維修小組完成其它任務后再完成該任務。于是對與任務R4，可計算各維修小組對已分配任務的效率與承擔任務R4效率之和，并派最小值對應的維修小組去完成任務R4。經計算，V4的效率最高，為2.8，因此，將任務R4分配給V4。

于是得到最終的油料裝備維修任務分配方案： 完成任務R1， 完成任務R2， 完成任務R3， 先完成任務R5，再完成任務R4。

4.結語

維修任務的分配，直接影響到油料裝備戰時維修保障工作效率，特別是在戰時條件下，維修任務重、時間緊，油料裝備維修任務分配工作，對油料裝備維修效率的影響更大。本文在考慮維修效率的基礎上，建立了維修任務分配模型，可以在戰時復雜條件下得到油料裝備維修任務的優化分配方案，使得在維修力量有限的情況下，能夠更高效地完成油料裝備戰時維修任務。

（作者單位：解放軍后勤工程學院）

參考文獻

[1]張惠珍，馬良． 一種基于匈牙利算法的二次分配問題求解方法[J]． 數學的實踐與認識． 2009， 39（13）：121～130．

[2]欒飛，楊瑋． 基于匈牙利算法的自動化立體倉庫出入庫優化調度[J]． 陜西科技大學學報． 2011， 29（3）：122～125．

[3]于煥英，孫晚華，何峣． 基于匈牙利算法的多車型配送問題[J]． 物流技術． 2011， 6：74～75．