崔 萌 耿伯英

(海軍工程大學電子工程學院 武漢 430033)

基于序列關(guān)系的維修資源匹配算法研究*

崔 萌 耿伯英

(海軍工程大學電子工程學院 武漢 430033)

由多個維修工序組成的維修任務(wù),是依照三種基本邏輯關(guān)系構(gòu)建形成的有向序列。論文給出維修任務(wù)的形式化定義,并將維修資源匹配問題簡化為維修工序?qū)S修保障能力需求的滿足。在建立單維修工序維修資源匹配模型的基礎(chǔ)上,構(gòu)建形成多維修工序維修任務(wù)資源匹配模型。仿真算例表明在資源分配中論文方法在滿足時間約束以及克服資源分配局部短視等方面具有優(yōu)勢。

維修資源; 邏輯關(guān)系; 有向序列; 匹配約束

(College of Electronic Engineering, Naval University of Engineering, Wuhan 430033)

Class Number TP391.9

1 引言

在維修保障活動中,“事后維修”和“計劃維修”等方式往往采用經(jīng)驗推算法,甚至采取高冗余儲備維修資源的方法。基于任務(wù)序列圖的資源能力匹配問題在兵力規(guī)劃、資源調(diào)度、并行處理[1～2]等諸多領(lǐng)域有著廣泛的應(yīng)用,從文獻來看通常采用尋找最優(yōu)解或啟發(fā)式方法解決。對于最優(yōu)解需找方法,主要包括整數(shù)規(guī)劃、分支定界法以及枚舉法[3]。啟發(fā)式方法是求解該類問題較常用的方法,主要采用規(guī)劃表方法,如動態(tài)列表規(guī)劃(Dynamic Level Scheduling,DLS)方法[4]、多維動態(tài)列表規(guī)劃(Multidimensional Dynamic List Scheduling,MDLS)[5]、多優(yōu)先級動態(tài)列表規(guī)劃(MultiPRI List Dynamic Scheduling,MPLDS)[6],以及蟻群算法[7]、遺傳算法[8]等。

2 維修任務(wù)形式化表達

根據(jù)維修工作的實際情況,系統(tǒng)裝備維修時,可能會同時安排多項維修任務(wù),而每項維修任務(wù)又由多道維修工序組成,維修工序間執(zhí)行邏輯關(guān)系的不同,將對維修資源的運用和需求數(shù)量產(chǎn)生較大的影響。

維修工序定義為不可分解為其他工序組合的基本維修活動,由描述該工序的名稱、標識、類型的基本屬性、描述其作用對象的維修目標、描述其對保障資源的維修能力需求、維修資源需求以及描述開展該維修工序的前序條件和后續(xù)條件等六個子要素組成,每個子要素可定義為一個信息集合[2]。

維修工序間執(zhí)行邏輯關(guān)聯(lián)主要由時間邏輯關(guān)聯(lián)、功能邏輯關(guān)聯(lián)確定。確定維修工序發(fā)生的時間邏輯先后關(guān)系后,工序間根據(jù)功能邏輯約束自發(fā)關(guān)聯(lián),工序間時間邏輯關(guān)聯(lián)是包含在維修任務(wù)概念屬性中的隱性約束,在表述維修任務(wù)序列時只需向維修工序結(jié)點添加時間屬性,就可表述工序間的時間邏輯關(guān)聯(lián)。功能邏輯關(guān)聯(lián)是工序間執(zhí)行順序邏輯關(guān)系的描述[9],邏輯功能關(guān)聯(lián)的全面分類、準確的形式化表達以及有效的數(shù)據(jù)模型構(gòu)建是表述維修任務(wù)序列的基礎(chǔ)[2]。

順序關(guān)系是指由順序開展多個維修工序形成的功能邏輯關(guān)系,常見于某職掌人順序完成某個設(shè)備維修任務(wù)多個維修工序的維修活動。并行關(guān)系是指由多個維修工序同時進行的功能邏輯關(guān)系,常見于由多個職掌人同時完成多個維修工序的維修活動。條件關(guān)系是指某個設(shè)備存在多個可能的維修工序,但當完成某項維修工序后若設(shè)備恢復(fù)正常,則剩余維修工序毋須開展。

由前可知,維修任務(wù)T是以維修工序為節(jié)點、維修工序間邏輯關(guān)聯(lián)關(guān)系為邊的有向圖,用三元組描述如下:T={{Ti},GT,{AttrTi}};其中Ti表示維修工序i,{Ti}表示維修任務(wù)序列圖中所有維修工序的集合;GT是維修工序間的邏輯關(guān)聯(lián)關(guān)系集合,根據(jù)前述內(nèi)容由順序關(guān)系SeqR、并行關(guān)系ConcR、條件關(guān)系CndR三種基本功能關(guān)系組成;AttrTi為維修工序Ti的屬性集,{AttrTi}表示所有任務(wù)屬性集的集合。屬性集AttrTi包含為了保障維修工序Ti執(zhí)行而應(yīng)具備的保障能力CapTi,以及任務(wù)Ti開始時間STi,任務(wù)Ti執(zhí)行時間ETi,任務(wù)Ti的其他時空靜態(tài)信息LocTi,AttrTi表示為:AttrTi={LocTi,CapTi,〈STi,ETi〉}。

3 維修資源與維修能力的統(tǒng)一表達

維修資源對艦艇機電系統(tǒng)工作效能的發(fā)揮具有重要影響,維修資源攜帶是否充足、利用率高低直接影響到艦艇裝備是否能夠遂行規(guī)定的使命任務(wù)、降低全壽命周期費用。

各類維修資源在維修活動中發(fā)揮不同的作用,比如有的屬于消耗品,有的則可以重復(fù)使用,根據(jù)維修資源的不同特點,將備品備件、耗損器材、維修人員、保障器材、保障設(shè)施等分為兩大類:消耗型保障資源和占用型保障資源。消耗型資源是指在裝備維修過程中逐漸被消耗掉的不可重復(fù)使用的資源,通常情況下將備品備件、耗損器材等看作消耗型資源。占用型資源是指在裝備維修過程的一段時間內(nèi)被使用的資源,但在相關(guān)維修過程結(jié)束后,這些資源回歸為空閑狀態(tài)[24],可以再分配給別的維修任務(wù)。

觀察景物，要確定觀察點，也就是觀察景物的立足點。觀察點不同，所看到的景物就不同。要恰當?shù)剡\用一些常用的修辭手法，如擬人、比喻、排比等。

維修保障資源是維修保障活動開展的根本要素,用AtomResi來描述原子維修保障資源時空狀態(tài)等靜態(tài)屬性和保障資源維修能力等動態(tài)屬性,記為AtomResi=〈ResAttri,Capi〉,其中ResAttri是原子保障資源靜態(tài)屬性的表達,Capi是原子保障資源i所具備的維修能力。維修能力定義為維修保障資源輸入和裝設(shè)備技術(shù)狀態(tài)輸出之間的映射關(guān)系:Atomfi=f(Inputi,Outputi),Inputi是形成維修能力所必須具備的裝設(shè)備技術(shù)狀態(tài)、維修知識等信息流和維修保障資源等物質(zhì)流的描述,Outputi為經(jīng)過維修工序處理后產(chǎn)生的裝設(shè)備/系統(tǒng)技術(shù)狀態(tài)的描述。則保障資源集合可表示為ER={AtomRes1,AtomRes2,…,AtomResm},m為保障資源種類;保障資源集合所有的保障能力組成集合EC={Cap1,Cap2,…,Capm}。

本文擴展維修保障資源概念,將維修保障資源視為保障資源要素和其具備維修能力的集合,表示為:Res={R,Cap},其中R是保障資源AR的子集;Cap是保障資源所具備維修保障能力集合。艦船任務(wù)攜帶維修保障資源所具備的維修能力集合可表示為F={Atomf1,Atomf2,…,AtomfN}。任何一項裝備保障維修能力Cap可看作是由一項或多項維修工序能力按照邏輯功能關(guān)系在輸入輸出作用下形成的整體映射關(guān)系。顯然Cap為整體裝備維修能力集合M的子集,F?M。因其為映射關(guān)系,Cap可表示為Cap=G(U,Struct),其中U是形成裝設(shè)備維修能力的原子能力集合,U?M;Struct是原子保障能力集合U中原子維修保障能力所對應(yīng)的保障資源輸入輸出交互結(jié)構(gòu)集合;映射關(guān)系G既可反映消耗型資源由于輸入輸出作用形成的消耗作用,也可表述占用型資源由于輸入輸出作用形成的組合保障功能。Cap=G(U,Struct)充分表達了任何一種維修保障能力都可由其他原子保障能力或其組合形成,同樣可以適用于對多類、多量維修資源聚合時產(chǎn)生新的維修保障能力的形式化定義。

4 多維修工序維修任務(wù)資源匹配模型

本文僅考慮多維修工序維修任務(wù)前提下的資源匹配問題。多維修工序維修任務(wù)的資源匹配問題,不僅要考慮每一維修工序施行所需的維修資源數(shù)量和對應(yīng)的維修保障能力,還需要進一步考慮在時間約束和邏輯功能約束條件下的維修資源匹配。

4.1 多維修工序單維修資源匹配

維修工序與資源/能力匹配應(yīng)滿足以下約束條件:

1) 維修資源維修保障能力約束:如果維修工序Ti對維修保障能力的需RCapTi可由RES集合中某個維修資源ARm的能力CapARm滿足,則該約束條件可表示為:S(CapARm,RCapTi)≥1;

2) 單維修資源選擇約束:在多個維修資源所具備的維修保障能力均能滿足維修工序Ti對維修保障能力的需RCapTi的情況下,選擇可選維修資源優(yōu)先權(quán)最高的資源以滿足維修工序?qū)Y源/能力的需求。

定義維修資源在與維修工序Ti對資源/能力的需求的匹配中優(yōu)先權(quán)函數(shù)為P(ARm,Ti):

P(ARm,Ti)=α·ΔTij+(1-α)·S(ARm,RCapTi)

其中α為因子權(quán)重,表示維修資源轉(zhuǎn)移時間與資源能力對維修能力需求的滿足程度在多維修資源選擇過程中的權(quán)重分配;ΔTij為維修資源從維修工序Ti轉(zhuǎn)至其后續(xù)工序Tj的能力轉(zhuǎn)移時間。

4.2 多維修工序維修資源匹配

則基于維修任務(wù)的資源/能力匹配模型目標函數(shù)表示為

其中Y′表示維修任務(wù)的最后完成時間,α和β是該維修任務(wù)完成時間與資源冗余在目標函數(shù)中所占的比例,根據(jù)維修保障目標分別設(shè)置兩者的數(shù)值用來調(diào)節(jié)維修任務(wù)規(guī)劃對保障效益與經(jīng)濟效益追求的偏重。

維修任務(wù)—資源/能力匹配模型表示如下:

5 算例

圖1 維修任務(wù)序列圖

資源分配過程中涉及的其他任務(wù)與資源屬性如下所示。

表1 任務(wù)預(yù)定開始和執(zhí)行時間

表中任務(wù)發(fā)生時間ETi為24小時制,執(zhí)行時間ETi以小時(h)為單位。

表2 任務(wù)與資源關(guān)系屬性

表中S(Cj,RCapRm)表示當前資源對任務(wù)需求的滿足程度,S(Cj,RCapRm)≥1,DRmTi表示當前資源與任務(wù)的距離,該距離以千米(km)為單位。表中T3和T7是消耗型資源,消耗型資源數(shù)量以噸(t)為單位,RCapTj表示任務(wù)Tj的資源數(shù)量需求,設(shè)置消耗型資源數(shù)量CapM6=300和CapM7=260。

表3 任務(wù)距離表

任務(wù)之間的距離以千米(km)為單位。

圖2(a)和(b)表示MDLS算法資源分配中條件關(guān)系選擇不同執(zhí)行任務(wù)造成后序資源分配方案的差異;圖3(a)和(b)表示本文方法資源分配中條件關(guān)系選擇不同執(zhí)行任務(wù)造成后序資源分配方案的差異。

圖中trans表示資源在該時間段內(nèi)處于轉(zhuǎn)移狀態(tài),trans開始時間點表示資源向任務(wù)轉(zhuǎn)移的最晚開始時間,Ti表示時間段內(nèi)任務(wù)的執(zhí)行;圖2中資源連續(xù)使用情況都采用雙線表示的方法,這也更加清晰的表達條件關(guān)系不同選擇下資源轉(zhuǎn)移關(guān)系。

從圖中結(jié)果分配的差異性可以看出,MDLS方法進行資源分配過程中將M2分配給T1,在對T2進行資源分配時仍選擇資源M2,而本文方法利用資源選擇任務(wù)的優(yōu)先權(quán)選擇將M2分配給T2,M1分配給T1從而從基本任務(wù)序列整體角度提高了效益,而局部、短視的缺陷是MDLS方法的在資源分配中存在的典型問題,而這也同樣造成了資源在具有直接先后序關(guān)系的任務(wù)中連續(xù)轉(zhuǎn)移而帶來的后序任務(wù)執(zhí)行時間的延長。雖然在資源選擇優(yōu)先權(quán)函數(shù)中存在排斥資源連續(xù)轉(zhuǎn)移的參數(shù)設(shè)置,但是參數(shù)取值是否合理難以預(yù)估,而本文資源分配方法中資源對任務(wù)選擇的方法是單純優(yōu)先權(quán)函數(shù)進行資源選擇的有力補充,可以最大程度上排除資源在具有直接先后序關(guān)系的任務(wù)之間不合理轉(zhuǎn)移的情況,同時在資源冗余方面相對MDLS方法也有一定程度的提高。

圖2 MDLS方法資源分配結(jié)果

圖3 G-S方法資源分配結(jié)果

6 結(jié)語

文中從維修任務(wù)維修資源匹配問題著手,基于維修任務(wù)由多個維修工序遵循一定關(guān)系組合形成的基本思想,在建立單維修工序情況下的單維修資源和單類維修資源模塊化編組匹配模型的基礎(chǔ)上,逐一分析建立了順序關(guān)系、并行關(guān)系和條件關(guān)系時維修工序的維修資源匹配模型,構(gòu)建多維修工序維修任務(wù)資源匹配模型,并利用算例進行了檢驗。結(jié)果表明本文方法在任務(wù)預(yù)定執(zhí)行率、資源轉(zhuǎn)移距離、時間延長總計和資源冗余總計四個統(tǒng)計指標中較優(yōu),證明在資源分配中本文方法在滿足時間約束以及克服資源分配局部短視等方面具有優(yōu)勢。

[1] Manimaran G, Murthy G S R. An efficient dynamic scheduling algorithm for multiprocessor real-time systems[J]. IEEE Transactions on Parallel and Distributed Systems,1998,9(3):312-319.

[2] 莫攀飛,李啟元.基于本體框架的海軍裝備保障計劃數(shù)據(jù)模型構(gòu)建[J].艦船電子工程,2015,24(7):34-38.

[3] 李敏.資源約束下多項目調(diào)度問題遺傳算法研究[D].杭州:浙江大學,2008.

[4] Gilber Sih, Edward Lee. A Compile-Time Scheduling Heuristic for Interconnection constrained Heterogeneous Processor Architectures[J]. IEEE Transactions on Parallel and Distributed Systems,1993,4(2):175-187.

[5] Levchuk Y N, Levchuk G M, Pattipati K R. A Systematic Approach to Optimize Organizations Operating in Uncertain Environments: Design Methodology and Applications[C]//Quebec City, QC, Canada: Proceedings of the 7-th International Command & Control Research & Technology Symposium,2002:170-230.

[6] 陳洪輝,趙亮,苪紅,等.作戰(zhàn)任務(wù)和資源間的匹配模型及求解算法研究[J].系統(tǒng)工程與電子技術(shù),2008,30(9):1712-1716.

[7] 鄧向陽,張立民,黃曉冬.一種基于蟻群優(yōu)化的裝備保障任務(wù)調(diào)度方法[J].計算機工程,2013,39(2):284-287.

[8] 張杰勇,姚佩陽,周翔翔,等.基于DLS和GA的作戰(zhàn)任務(wù)-平臺資源匹配方法[J].系統(tǒng)工程與電子技術(shù),2012,34(5):947-954.

[9] 胡欣.基于本體的聯(lián)合作戰(zhàn)計劃表示與校驗研究[D].長沙:國防科學技術(shù)大學,2011.

Maintenance Resource Matching Algorithm Based on Sequential Relationships

CUI Meng GENG Boying

Based on the maintenance task structure, this paper clomifies that the maintenance task is a directed sequence which is made of three types of process relationship. It sets forth the definition of maintenance task. And the maintenance task resource matching is realized as the maintenance capability fulfillment of processes.This paper sets forth the resources matching model for single maintenance process, sequential relationship processes, parallel relationship processes, conditional relationship processes. Finally, the resource matching model is composed for the maintenance task. Simulation result shows that the algorithm has an edge than MDLS in satisfying time constraint and overcoming resource matching shortsighted problem.

maintenance resource, functional logical relationships, directed sequential, matching constraint

2016年6月11日,

2016年7月23日

湖北省自然科學基金項目(編號:2014CKB1013)資助。

崔萌,女,碩士,講師,研究方向:裝備保障仿真。

TP391.9

10.3969/j.issn.1672-9730.2016.12.028