一种基于多约束关系的任务分解方法

霍永华,昌汉明，曹　毅

(1.中国电子科技集团公司第五十四研究所,河北 石家庄 050081；

2.西安电子科技大学，陕西 西安 710071;

3.总参信息化部石家庄地区军事代表室，河北 石家庄 050000)



一种基于多约束关系的任务分解方法

霍永华1,昌汉明2，曹毅3

(1.中国电子科技集团公司第五十四研究所,河北 石家庄 050081；

2.西安电子科技大学，陕西 西安 710071;

3.总参信息化部石家庄地区军事代表室，河北 石家庄 050000)

摘要：针对任务分解和分配的实时性和快速性，研究基于多约束关系的任务分解。首先对任务进行初始化标识，定义任务的唯一标识、开始时间、生命周期及任务重要度。其次定义任务间的约束关系，包括同步、串行、父子关系以及同步下受时序和资源约束等，确定任务之间的相互联系，为执行任务分解做好准备。然后，研究一种基于任务分解树的算法：依据任务间约束关系通过任务分解树的方法实现对任务的分解。最后附实例验证。

关键词：任务重要度；同步关系；串行关系；父子关系；任务分解树

0引言

针对抗震救灾坏境中宏观任务的下达，任务的分解细化过程，研究一种任务的分解机制[1-3]。该机制首先依据任务的具体状况定义任务的唯一标识、开始时间、生命周期及任务重要度，实现对任务的初始化标识。其次定义任务间的约束关系[4-6]，包括同步、串行、父子关系以及同步下受时序和资源约束等，确定任务之间的相互联系，为执行任务分解做好准备。然后，研究一种基于任务分解树的算法：建立一棵空的任务树，将任务节点放入任务队列中，依据任务间的约束关系从任务队列中提取并放入任务树的适当位置，直至任务队列为空，这样最终依据任务间约束关系通过任务分解树的方法实现对任务的分解。

1任务的四要素

任务可以分为复杂任务和简单子任务，为了更好地完成某个目标，其对应的任务应该进行分解和调度，以保障更好更快地完成。

定义每一个任务为一个四元组[7,8]G=(ID,Begin,Time,I)

① 其中ID代表每一个任务的名字，不同的任务具有不同的ID，且不可相同；

② Begin代表任务的开始时间，因为任务的分解与调度中常有时序约束，所以要考虑不同任务的开始时间；

③ Time代表任务的持续时间；

④ I代表任务的重要度。所谓重要度指当遇到突发情况时，每个节点的紧急情况可能各不相同，重要的节点应优先考虑处理，不同的任务可能具有不同的重要度。

2任务的关系约束

定义如下几种关系约束：

① 同步执行任务集 P={T1，T2，T3}，即任务T1、T2、T3可以同步地执行，主要是对于同层的节点，如图1所示。

图1　并行任务示意图　图2　串行任务示意图

③ 父子关系任务集 F={T5，T6，T7}，即任务T5可以进一步分解为T6、T7。表示T5是T6和T7的父节点，父子关系任务集中，父节点可能全面的包含子任务或是部分包含，全面包含指的是子任务全部完成，父任务才可执行，用集合表示为：T={T5，A{T6，T7}}，如图3所示。而部分包含指的是完成部分子任务后即可开始执行父任务，用集合表示为T={T5，O{T6，T7}}，如图4所示。用方框置于外侧是表示这是一个任务分解模块，T5是由T6和T7组成的。

图3　全包含父子关系　　图4　部分包含父子　示意图　关系示意图

综合分析上述情况可以把任务分解表示在一个大的集合内。

根据上述定义可以得出任务分解树，如图5所示。

图5　任务分解树示意图

其中T1对T3有时序或资源方面的约束，在图中用T1-3来表示这种约束关系。T3、T4、T5是串行执行的。T6、T7全包含于T5。针对不同任务节点的重要度，可以对任务分解图进一步优化，节点的重要度可以开始时由更高层级直接指定，若没有指定，则依据节点重要性的算法来衡量。假设图5中高层级指定了T3的重要度高于T2，则在出现紧急情况时优先考虑T3。若没有指定，以节点重要性的角度去考虑，T3节点的度数高于T2，所以T3重要度大于T2(以节点的度来衡量重要性)，根据以上两种情况，可以把任务分解树优化。

3基于任务树的任务分解

在进行任务调度时，首先要考虑节点间的时序约束，其次当在进行任务调度出现紧急情况时，同层中左边节点的重要度大于右边，所以优先处理左边节点出现的情况，这种任务分解树看上去直观，且考虑的更加全面。

基于任务树的任务分解算法[9,10]步骤如图5所示。

步骤1：初始化任务树节点置为空，把每项任务定义为任务树中的节点，并把节点间的相互约束关系置于节点关系表中；

步骤2：为每个节点分配唯一的ID，初始化任务的开始时间Begin和预估执行时间Time，根据需要判断是否初始化重要度I，若需要则给定相应等级，否则置为空；

步骤3：设置一个队列，把所有任务节点置于队列中，首先输出代表源节点的节点S；

步骤4：从队列中依次输出每个任务节点；

步骤5：输出的节点是否需要进一步分解，若是则符合父子约束关系，在任务分解树中生成该节点的子节点，其层次为父节点加一，并由父节点指向子节点。若不是则跳转到7；

步骤6：判断父节点是全包含还是部分包含，若是全包含则所有子任务执行完成才认为父节点完成，是部分包含则部分子任务完成，父任务就认为完成；

步骤7：以节点任务表中的约束判断输出的节点是否符合同步执行约束，若是则任务分解树中节点间层次相同并假设层次为n，且由n-1层节点同时指向它们。若不是则跳转到步骤8；

步骤8：以节点任务表中的约束判断输出的节点是否符合串行执行约束，若是则任务分解树中任务节点的层次逐步递增，且层次低的节点指向层次高的节点，若不是则跳转到步骤9；

步骤9：按节点重要性算法计算未置初值的任务节点的重要度，判断是否需要优化，若是则跳转到步骤10，不是则跳转到步骤11；

步骤10：同层中把没有时序约束且重要度高的节点i(包括它的子节点)不断左移，直到其左侧节点对i有约束则停止，所有节点优化完跳到步骤11；

步骤11：重复执行步骤3，直到队列中节点为空，生成任务分解树。

4实例验证

假设某次抗震救灾补给灾区运输车加油，由于搭建基地就只有一个，所以每个运输车按串行补给，总补给任务称为S，假设有n辆运输车，表示为B1、B2…Bn则n辆车之间的关系为串行关系，也就是当第1辆车加油完毕后，第2辆车才能加油。

步骤1：对任务进行初始化标识，定义唯一标识为S，任务分为两类，即运输油A和加油B，开始时间为ts，生命周期为T，任务重要度为非常重要；

步骤2：定义任务间的约束关系，只有运输油到的情况下，才能加油。因此对运输油任务A对加油任务B有时序约束。在运输加油任务中，由于加油基地只有一个，所以只能一个一个进行加油，因此加油任务A为同步关系；运输油任务B可以并行进行；

步骤3：建立一棵空的任务树S，将任务节点(任务A和任务B)放入任务队列中，依据两个任务间的约束关系(任务A对任务B有时序约束)，从任务队列中提取并放入任务树的适当位置，任务分解树如图6所示。

图6　抗震救灾运输车加油任务分解图

5结束语

为保证抗震救灾环境下任务的执行，提出了救灾网络任务分解方法。文中提出的几种约束关系，考虑到了任务和任务间，总任务和子任务间的关系。而重要度的提出也是考虑到作战任务的特殊性，所谓重要度是指任务节点分主次，当出现紧急情况时优先考虑重要度高的任务，这可以保证在救灾环境下作战任务能最大限度地不受其他因素的影响。

参考文献

[1]肖增良,乐晓波.基于与或依赖图的多Agent系统任务分解算法[J].计算机工程与设计,2009，40(2):267-272.

[2]钟琪.基于启发式算法的任务分解策略[J].煤炭技术，2010,30(12)：25-29.

[3]秦娜,乐晓波,刘武.基于 Petri 网模型的 JSP 粒子群优化调度[J].计算机应用,2008,28(8):2167-2169.

[4]White J E.Mobile Agents In：Bradshaw，Jeffrey eds.Software Agents，Menlo Pork [M]. California:Press / The MIT Press，1996.

[5]Lange D B.Mobile Objects and Mobile agents：The Future of Distributed Computing[C]∥Proc of the European Conf on Object Oriented Programming’98.Brussels，1998:49-52.

[6]杨学会,王精业.基于任务分解的作战仿真研究[J].系统仿真学报,2006,18(10):18-21.

[7]刘波,罗军舟.大规模网络管理中的任务分解与调度[J].通信学报,2010,42(6):48-51.

[8]刘波,罗军舟.网络管理中多agent的半在线调度算法[J].计算机研究与发展,2006，27(3)：65-72.

[9]王红霞,刘治国,潘成胜．分布式网络管理中的任务管理与任务调度的研究[J]．沈阳工业学院学报，2009,30(11):15-19.

[10]金黎黎,孔令富．协同设计环境中任务分解与调度的研究[J].计算机工程与设计，2009，25(2)：22-25.

Task Decomposition Method Based on Multiple Constraint Relations

HUO Yong-hua1,CHANG Han-ming2,CAO Yi3

(1.The 54th Research Institute of CETC,Shijiazhuang Hebei 050081,China;

2.Xidian University,Xi’an Shaanxi 710071,China;

3.Military Representative Office of Information Technology Department of General Staff Headquarters Stationed in Shijiazhuang,

Shijiazhuang Hebei 050081,China)

Abstract：In view of timeliness and quickness of task decomposition,this paper studies the task decomposition based on multiple constraint relations.Firstly the initialization identifier is defined on task,including unique identification and start time and life cycle and importance of missions.Secondly the constraint relations between tasks are defined,including synchronous relations and serial relations,father and son relations,time and resource constraints in synchronization,the inter-relationship between tasks are determined for preparation for task decomposition.Lastly an algorithm based on task decomposition tree is studied,which uses task decomposition tree to implement task decomposition according to constraint relations between tasks.Finally this algorithm is verified by an instance.

Key words：importance of Missions;synchronous relations;serial relations;father and son relations;task decomposition tree

作者简介：霍永华(1977 —)，女，高级工程师，主要研究方向：通信网络管理。昌汉明(1989— )，男，硕士研究生，主要研究方向：通信网络管理。

基金项目：国防基础科研计划基金项目资助

收稿日期：2015-09-08

中图分类号：TP393

文献标识码：A

文章编号：1003-3114(2016)01-35-3

doi:10.3969/j.issn.1003-3114.2016.01.09

引用格式：霍永华,昌汉明，曹毅.一种基于多约束关系的任务分解方法[J].无线电通信技术,2016,42(1):35-37.