文/ 陸思錫 周慶忠 熊 彪

?

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

文/ 陸思錫 周慶忠 熊 彪

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

關(guān)鍵詞：油料裝備；維修；效率；決策

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

1.油料裝備戰(zhàn)時維修任務(wù)分配模型建立

1.1油料裝備戰(zhàn)時維修任務(wù)分配問題的數(shù)學(xué)描述

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

1.2模型建立

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

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

上述模型中待求的未知數(shù)為aj。

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

上述模型中待求的未知數(shù)為bi。

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

2.油料裝備戰(zhàn)時維修任務(wù)分配模型求解

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

2.1匈牙利算法基本原理

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

2.2模型求解方法

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

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

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

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

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

3.油料裝備戰(zhàn)時維修任務(wù)分配模型應(yīng)用

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

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

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

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

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

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

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

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

4.結(jié)語

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

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

參考文獻(xiàn)

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

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

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