基于序列关系的维修资源匹配算法研究*

崔 萌 耿伯英

(海军工程大学电子工程学院 武汉 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