基于序列關系的維修資源匹配算法研究*

崔 萌 耿伯英

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

基于序列關系的維修資源匹配算法研究*

崔 萌 耿伯英

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

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

維修資源; 邏輯關系; 有向序列; 匹配約束

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

Class Number TP391.9

1 引言

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

2 維修任務形式化表達

根據維修工作的實際情況,系統裝備維修時,可能會同時安排多項維修任務,而每項維修任務又由多道維修工序組成,維修工序間執行邏輯關系的不同,將對維修資源的運用和需求數量產生較大的影響。

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

維修工序間執行邏輯關聯主要由時間邏輯關聯、功能邏輯關聯確定。確定維修工序發生的時間邏輯先后關系后,工序間根據功能邏輯約束自發關聯,工序間時間邏輯關聯是包含在維修任務概念屬性中的隱性約束,在表述維修任務序列時只需向維修工序結點添加時間屬性,就可表述工序間的時間邏輯關聯。功能邏輯關聯是工序間執行順序邏輯關系的描述[9],邏輯功能關聯的全面分類、準確的形式化表達以及有效的數據模型構建是表述維修任務序列的基礎[2]。

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

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

3 維修資源與維修能力的統一表達

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

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

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

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

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

4 多維修工序維修任務資源匹配模型

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

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

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

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

2) 單維修資源選擇約束:在多個維修資源所具備的維修保障能力均能滿足維修工序Ti對維修保障能力的需RCapTi的情況下,選擇可選維修資源優先權最高的資源以滿足維修工序對資源/能力的需求。

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

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

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

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

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

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

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

5 算例

圖1 維修任務序列圖

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

表1 任務預定開始和執行時間

表中任務發生時間ETi為24小時制,執行時間ETi以小時(h)為單位。

表2 任務與資源關系屬性

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

表3 任務距離表

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

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

圖中trans表示資源在該時間段內處于轉移狀態,trans開始時間點表示資源向任務轉移的最晚開始時間,Ti表示時間段內任務的執行;圖2中資源連續使用情況都采用雙線表示的方法,這也更加清晰的表達條件關系不同選擇下資源轉移關系。

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

圖2 MDLS方法資源分配結果

圖3 G-S方法資源分配結果

6 結語

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

[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] 莫攀飛,李啟元.基于本體框架的海軍裝備保障計劃數據模型構建[J].艦船電子工程,2015,24(7):34-38.

[3] 李敏.資源約束下多項目調度問題遺傳算法研究[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] 陳洪輝,趙亮,苪紅,等.作戰任務和資源間的匹配模型及求解算法研究[J].系統工程與電子技術,2008,30(9):1712-1716.

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

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

[9] 胡欣.基于本體的聯合作戰計劃表示與校驗研究[D].長沙:國防科學技術大學,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