基于分层任务网络的云制造任务分解方法

刘明周 王 强 凌 琳

合肥工业大学机械与汽车工程学院，合肥，230009

基于分层任务网络的云制造任务分解方法

刘明周 王 强 凌 琳

合肥工业大学机械与汽车工程学院，合肥，230009

提出了一种基于顺序任务分解的云制造任务分解算法。首先给出云制造任务描述模型以及任务约束结构的相关定义，对制造任务粒度分析方法、制造任务内聚性度量方法和制造任务相关性度量方法进行了研究。然后，采用递归分解算法对任务进行优化分解，并在分解过程中考虑任务的资源匹配问题。最后，以某变速箱试制任务分解为实例验证了所提方法的可行性和有效性。

云制造；任务分解；任务粒度；分层任务网络

0 引言

合理的制造任务分解与规划是云制造服务平台实现高效资源协同和共享的关键。目前，国内外学者对任务分解和规划方法的研究主要集中在任务流程建模以及任务相关关系分析两个方面。

常见的任务流程建模方法有图论法[1-2]、设计结构矩阵(design structure matrix, DSM)法[3]和分层任务网络(hierarchical task network, HTN)法[4-5]。任务流程建模方法很少考虑子任务的相关关系，任务相关关系是任务分解的重要依据，通过合理的分析规划能够有效提高任务执行的效率。安波等[6]通过构建扩散任务相关性模型，结合粒子群聚类优化分解算法，实现对扩散任务的有效分解；包北方等[7]针对产品定制协同开发任务分解缺乏综合定量分析的问题，提出一种综合考虑任务粒度、任务耦合度、任务均衡度的任务分解系统模型；GERASOULIS等[8]在建立任务相关性模型的基础上，运用聚类算法得到具有合适粒度大小的任务分解方案。

上述方法在解决云制造环境下的制造任务分解问题时，存在任务分解与制造资源匹配脱节的问题，另外，云制造任务的多样性要求在任务分解过程中需要有领域知识作为支撑。由此，云制造任务分解过程中，不仅需要考虑任务间的平衡性与任务粒度均衡性，还要考虑资源的匹配性与领域知识的完备性。基于此，本文设计了一种基于顺序任务分解(ordered task decomposition，OTD)的云制造任务递归分解算法。

1 云制造任务关联特性分析

1.1 云制造任务约束结构

云制造任务执行的过程可以看作是一系列制造服务按照一定的时序和逻辑关系组合完成对应制造任务活动的过程，是制造服务与任务活动对象在时间、信息和实物流上的有机集合。任务活动对象在不同制造服务间的信息传递、实物流交互、时序约束等构成了复杂约束关系，并以此复杂关系为基础，完成整体制造任务的执行。

本文将任务活动的约束结构定义为一个四元组(T，C，D，H)，其中，T表示与该活动约束结构相关的单元集合即任务活动集合；C={(m，rs)∈T×D(T)}表示由多个单元确定的约束控制结构的集合，(m，rs)表征约束中控制结构内各单元的输入输出关系，其中，m为输出单元即后序制造任务，rs为输入单元集合；D表示与该活动约束结构相关的单元集合之间的信息关联矩阵；H表示与该活动约束结构相关的单元集合之间的物流关联矩阵。

常见的任务活动约束结构主要有串行结构、并行结构、选择结构和循环结构。

(1)串行结构。表示一组顺序执行的任务，如图1a所示，输出单元为t2，输入单元为t1，那么该输入输出单元之间的控制约束关系可表示为(t2，t1)。

(2)并行结构。某一任务有一个以上的前序任务，且前序任务间相互独立，不存在信息依赖关系，即t2、t3、…、tN之间不存在任何信息交互和实物流交互。如图1b所示，输入单元为t2、t3、…、tN，输出单元为tN+1，那么该控制约束关系可表示为(tN+1，{t2，t3，…，tN})。

(3)循环结构。某任务活动完成后需要返回之前完成的某一活动，如图1c所示，输入单元为tN，输出单元为t2，那么该控制约束关系可表示为(tN，-t2，W)，W为循环的次数。

(4)分支结构。依据一定的条件选择执行的路径，但任务完成的路径不唯一，具体任务路径按一定概率选择，如图1d所示，输入单元为t2、t3、…、tN，输出单元为tN+1，那么该控制约束关系可表示为(tN+1，{t2‖t3‖…‖tN}，P)，P为各子任务发生的概率集合。

(a)串行结构

(b)并行结构

(c)循环结构

(d)分支结构图1 任务约束结构Fig.1 Constraint structure of task

云制造模式下，企业业务需求和制造资源的多样性、异构性以及各业务主体信息化水平的差异性，导致对制造资源服务和制造任务需求的描述呈现模糊性和不一致性,因此，对制造过程中涉及的活动对象进行统一的语义描述是云制造应用过程的关键环节。网络服务本体语言(Web ontology language for services，OWL-S)既有较强的语义表达能力，能提供完备、可判断的推理机制，又是一种具有显式语义、无歧义的机器可理解的标记语言，可用来描述Web服务的属性和功能。此外，OWL-S过程模型定义了一组过程及其执行顺序，其中包括Sequence、Split、Split+Join、Unordered、Choice、If-Then-Else、Iterate、Repeat-Until等几种控制流，可以有效实现对制造任务约束结构的表达，故本文采用OWL-S对制造任务进行描述。

1.2 制造任务粒度分析与控制

任务分解的层级及子任务的数量和粒度控制是云制造任务分解的关键，直接影响云制造任务协同完成的质量、执行进度和成本。子任务粒度过小、层级过深，任务间的关联关系复杂，势必会增加任务管理的难度，造成信息交互、物流以及管理成本的大幅攀升。任务活动过少、粒度过大，会导致任务内部复杂度高，影响整体制造任务的执行效率。因此，任务粒度控制对云制造任务分解来说具有重要的现实意义。

任务粒度是任务聚合程度的量化水平，反映了整体制造任务的规模和层级，与任务数量成反比，其数学模型如下：

ST=V/NT

(1)

式中，ST为任务粒度，ST>0；NT为任务数量，NT>0；V为任务粒度系数，由任务内聚程度决定，V>0。

1.3 制造任务内聚性度量方法

任务关联系数是任务内部各活动单元之间的关联程度的量化指标。假设在任务约束结构(T，C，D，H)中，存在有效约束控制元t。该任务约束结构的任务关联系数λ(t)定义如下：

λ(t)=

(2)

其中，|t|为有效约束控制元的数量；m、n为输出活动单元；qs为输入活动单元集，({m}∪rs) ∩({n}∪qs)≠∅表示不同约束控制元的输入输出活动单元之间存在非空交集；{m}、{n}表示约束控制元中所有输入单元的集合；{m}∪rs、{n}∪qs表示约束控制元中所有活动单元的集合。任务关联系数反映了某约束控制子集与相邻约束控制元之间活动的关联水平。一个约束控制元中的输入输出单元在其他控制元中出现得越多，则约束控制元之间的关联性越强。

任务重用系数是指在一个任务约束结构中，被重用的活动单元数与该约束控制结构中所有活动单元数的比值，量化反映了该约束结构中活动单元被重用的水平，具体定义如下：

(3)

A=|{v∈U|∃(m,rs)∈t,(n,qs)∈t,

v∈({m}∪rs)∩({n}∪qs),(m,rs)≠(n,qs)}|

B=|{v∈U|∃(m,rs)∈t,v∈({m}∪rs)}|

任务内聚系数w(t)是任务关联系数和任务重用系数的乘积，即

w(t)=λ(t)μ(t)

(4)

它综合表征了任务约束结构的内聚程度。云制造整体任务Tc的内聚系数V为各个子任务内聚系数的均值。

1.4 制造任务相关性度量方法

云制造任务种类繁多，有设计任务、制造加工任务、物流任务和测试任务等，各任务活动间不可避免地存在信息流和物料流的交互。在任务分解时应该尽量保持任务活动间的独立性，以利于后续的各个任务活动能够相对独立地进行。因此，本文引入相关度的概念，分别从子任务间信息交互和实物流传递两方面来判定任务活动之间相关性的大小。

信息相关度用来反映任务与任务之间的信息依赖关系，本文采用模糊设计矩阵法来构建云制造任务之间的信息关联矩阵，即

(5)

其中，aij(i，j=1，2，…，p) 为第i个任务和第j个任务之间的信息相关度，p为所有约束子集中的有效任务数量。aij量化表征了任务之间在沟通协作、信息传递中的频次和复杂程度，aij=0表示第i个任务和第j个任务之间没有任何信息交互，属于独立不相关任务；aij=1表示第i个任务和第j个任务之间具有较高的信息交互量，这时应将两个任务尽可能地合并以降低信息交互成本。aij的取值范围为[0，1]，一般采用专家评价法确定该值[9]。

物流相关度是子任务之间在物流转移频次、数量、距离等方面的综合度量。物流相关度的判定方式与信息相关度类似，可表示为

(6)

其中，bij表示任务i与任务j之间的物料转移相关程度，量化表征了任务之间的实物流动重要程度和密集程度，取值范围为[0，1]，一般采用专家评价法确定[9]。

设计类制造任务中，产品设计涉及大量文件传递及沟通协调工作，但在此过程中很少有实体物流产生，故信息相关度较高，物流相关度较低。制造加工类、测试类和物流类制造任务的物料转移活动较多，故物流相关度较高，可见制造任务类型的不同对物流相关度的影响较大。

任务相关度是制造任务间关联关系的综合度量，则任务活动i和j之间的任务相关度为

rij=waij+(1-w)bij

(7)

其中，w为信息相关度在任务间综合相关关系度量中的权值，反映了信息相关度对综合相关度的影响。不同的任务类型和不同任务层次中，w的取值也会有所不同，需要根据实际任务情况判定。在任务分解过程中，一般会设定相关度阈值rmax，需要注意的是，rmax的取值与具体任务类型及任务层级有关，层级较少时，为保证任务能够顺利分解，rmax应取较大的值，层级较多时，rmax应取较小的值，以保证原子任务能够有效组合。

2 云制造任务分解算法

2.1 HTN规划方法

HTN规划是基于分层抽象和领域知识的智能规划求解方法，其基本步骤是：根据预先给定的目标任务，按照递归的方式将复合任务不断分解为更小粒度任务，同时在分解过程中进行相关约束和冲突校验，直至形成具有严格时序关系和约束关系的复杂任务活动网络，从而形成任务规划问题的可行解。

HTN规划问题可描述为三元组Q=(s0，w0，D)，其中，s0是规划问题的初始状态；w0是初始任务网络；D是HTN规划领域，由操作集和方法集组成。

规划领域可表示为D=(O，G)，O代表操作集合，G代表方法集合。原子任务只存在一个操作算子，可以描述为o=(op，opre，oeff)，op、opre和oeff分别表示操作对应的原子任务、操作前提条件和操作执行后的效果。分解方法是分解复合任务的规则，可表示为二元组g=f(e，d)，其中，e表示复合任务，d表示复合任务e分解后的任务网络。

任务活动网络tNet=((n1∶e1)，(n2∶e2)，…，(nm∶em)，l)，其中，ni为任务ei的唯一标识符，ni∈N；l为约束条件，如时序约束、状态约束和值约束等。

规划解是HTN规划问题的可行解，可表示为π=〈o1，o2，…，on〉，其中，o1、o2、…、on是完成初始任务w0的操作。

常规HTN规划方法具有领域无关性，因此，在解决特定的领域规划问题时需要引入领域知识，如产品设计任务需要考虑产品结构要求、功能要求等知识，制造加工任务则需要考虑工艺要求、资源约束等知识。领域知识在引入HTN规划方法时，通常以操作集合和方法集合表现，通过拓展操作和方法的内涵，实现制造领域知识的引入。

操作是描述任务执行的过程，在操作算子中引入k元素，将领域知识的描述加入到opre和oeff，通过k完成领域知识的调用，如调用领域知识库、集成领域算法等，从而能够有效地将领域知识引入到HTN规划中，新操作算子可表示为o*=(op，opre，k，oeff)。

方法g的作用是将复合任务分解为多个子任务。复合任务在分解时可能有多种分解模式，因此在构建方法g时需要融入领域知识。将d改写为((p1，d1)，(p2，d2)，…，(pn，dn))的序对形式，新的方法可表示为g*=f(e，(p1，d1)，(p2，d2)，…，(pn，dn))，(pi，di)，表示在前提条件(领域知识的载体)pi下，通过方法g将复合任务e分解为di。

云制造任务分解中，任务类型多样，涉及多领域知识，且任务活动间约束结构较为复杂，存在并行、选择和循环等复杂约束结构关系，通过在操作中引入k元素，以及在方法g中引入(oprei，di)，在di中定义序对之间的约束结构关系，将领域知识引入方法g，从而实现不同类型云制造任务的分解。

2.2 基于HTN的云制造任务分解算法

HTN的任务分解方式可分为三类：顺序任务分解、无序任务分解(unordered task decomposition，UTD)和部分有序任务分解算法(partially ordered task decomposition，POTD)。由于云制造任务一般按照层次性原则自顶而下进行分解，故本文采用OTD算法对任务进行分解。经典OTD算法[10]首先以初始任务网络为起点，运用任务分解方法g*，按照先后顺序对任务网络中的各任务活动(子任务)进行递归分解。分解完成后，判定当前任务规划能否满足任务执行的需求，若满足任务执行的条件，则生成一个可执行计划。相比传统的任务分解方法而言，OTD算法降低了任务分解的难度及不确定性，从而极大提高了任务分解的效率，具体的算法求解过程如图2所示，其中q(s0,w0，Os,Ms)表示某一制造任务分解问题，Os为操作集合，Ms为分解方法的集合。

图2 基于OTD的任务分解算法解算流程Fig.2 Decomposition algorithm of cloud manufacturing task based on OTD

3 实例验证

以国内某变速箱制造企业DTF630自动变速箱样机试制任务为例，对本文提出的基于HTN的云制造任务分解算法进行应用。自动变速箱结构复杂，其样机试制涉及226种零件的外协加工任务，需要由多个企业协同完成。变速箱样机试制与批量生产不同。样机试制阶段，零部件外形尺寸以及工艺参数需要与其他零件进行匹配，因此样机试制过程中的各项子任务有严格的时序关系。另外，负责零件试制的外协厂家需要满足一定QoS约束条件(服务质量、服务成本、服务时间、服务延时率、服务匹配度、服务纠纷率和服务信誉度等)，表1所示为部分试制任务的QoS约束条件。因此，根据所提方法对该制造任务进行分解。

表1 部分试制任务QoS约束条件

初始任务网络w0=({u0}，L)，u0为初始任务节点，u0中只包含一个任务活动t01，即DTF630样机试制任务，L为该任务的相关约束条件集，如任务完成成本、周期、价格以及执行任务的制造服务QoS等约束条件。假设分解后的子任务均有与之匹配的制造服务，另外根据专家经验，设定最大任务粒度系数不超过0.02，为简明起见，省略了参数项，采用OTD算法递归分解该任务的实施过程如下：

(1)变速箱试制任务并不能由单个制造服务提供商独立完成。因此，基于层次原则，按照产品BOM结构对自动变速箱样机试制初始任务w0进行分解，得到任务分网络w1=((n11∶e11)，(n12∶e12)，…，(n18∶e18)，L1)，子任务t分别是：①壳体及附件试制任务e11；②齿轮传动装置试制任务e12；③差速器总成试制任务e13；④同步器装置试制任务e14；⑤换挡执行装置试制任务e15；⑥驻车制动装置试制任务e16；⑦液压模块总成试制任务e17；⑧电控单元试制任务e18。

(2)对新任务网络w1进行相关性分析、内聚性分析以及粒度分析，由于任务网络w1的任务粒度过大，需要对w1进行进一步的细化分解。以e17为例，液压模块总成试制任务e17由阀体、开关电磁阀、压力控制阀、流量传感器和隔板等组成零件的试制组成，零件结构、功能以及制造工艺差别较大，需要进一步细化。

(3)选择一个可转化为复合任务的简单任务ec，任取一个方法g*∈θ(θ为tc的分解方法集合)对ec进行分解，这里选择液压模块总成试制任务e17进行分解，得到对应的子任务网络d21=((n21∶e21)，(n22∶e22)，…，(n28∶e28)，L21)，分解方法g*采用按BOM结构分解的方法，其中，阀体试制任务为e21，电磁阀试制任务为e22，流量传感器试制任务为e23，蓄能器、开关阀弹簧试制任务为e24，泄压阀堵头、冷却滑阀堵头总成试制任务为e25，隔板试制任务为e26，从而形成新任务网络w2。由于在w2中依然存在e11、e12等大粒度任务，故不满足相关性及粒度约束，需要进行进一步分解。

(4)重复步骤(2)和步骤(3)，由于篇幅所限，本文给出最终完成分解的任务网络图，如图3所示，图中数字代表分解后的子任务序号。

图3 分解后的任务网络图Fig.3 Network of decomposed task

可以得出8个有效子任务，其活动约束结构为Ta={1，2，…，5}，Ca={(4，{1，2，3})，(5，{4})}，Tb={5，11，12，13}，Cb={(11，{5})，(12，{5})，(13，{5})}，Tc={4，6，7，8}，Cc={(8，{4，6，7})}，Td={12，14，15，16，17}，Cd={(14，{12})，(17，{14，15，16})}，Te={8，9，10，18}，Ce={(18，{8，9，10})}，Tf={18，19，20，21，22}，Cf={(20，{18})，(21，{18})，(22，{19，20})}，Tg={22，23，24，26}，Cg={(26，{22，23，24})}，Th={17，25，26，27}，Ch={(26，{17})，(27，{25，26})}，各子任务的分解图见图4。

(5)根据式(2)～式(4)，分别计算相应任务集的内聚系数，如表2所示。

由式(1)可计算出任务粒度：

该分解方案的任务粒度在任务内聚度阈值范围之内，因此，进入制造服务匹配阶段，筛选候选制造服务集。若此时的任务粒度不在任务内聚度阈值范围之内，则需要对任务网络进行相关性分析，根据任务活动之间信息交互、物流交互以及功能相似度分别构造信息关联矩阵D和物流关联矩阵H，将信息交互以及物流交互较多的任务活动进行合并，从而增大任务集的内聚系数，降低任务集之间的相关性，提高任务执行效率。

(a) (b)

(c) (d)

(e) (f)

(g) (h)图4 合适任务粒度分解集Fig.4 Suitable task granularity decomposition set

任务序号活动关联系数λ(t)活动重用系数μ(t)任务内聚系数w(t)a1．0000．200．200b1．0000．250．250c000d1．0000．200．200e000f0．3330．200．066g000h0．5000．250．125

任务活动网络符合任务粒度约束条件后，需要为任务活动网络中各子任务匹配符合要求的制造服务。在匹配过程中主要考虑服务延时率、服务中标率、服务完成率、服务匹配度、服务纠纷率和服务信誉度等QoS约束条件，用户可根据实际需求来调整筛选的参数，以扩大或缩小候选制造服务的规模，最终形成候选制造服务集，为云制造资源优化配置提供数据支撑。

4 结语

任务分解的目标在于将复杂的多层次、多粒度制造任务细化为粒度合适、便于协同执行的子任务。本文给出了云制造任务描述模型及任务约束结构的相关定义，设计了基于分层任务网络的云制造任务递归分解算法，并给出了制造任务粒度分析方法、制造任务内聚性度量方法以及制造任务相关性度量方法。该方法不但考虑了任务相关性和内聚性，还将制造任务与制造资源的匹配性以及任务分解的领域知识引入任务分解过程，从任务流程建模与规划、任务相关关系分析以及制造资源匹配等方面对任务分解方法进行优化，有效提高了任务分解效率，降低后序制造资源优化配置问题的复杂性。

[1]BORENSTEIND.ADirectedAcyclicGraphRepresentationofRoutingManufacturingFlexibility[J].EuropeanJournalofOperationalResearch，2000，127(1)：78-93.

[2]BRIR.ParallelSimulationAlgorithmforMaintenanceOptimizationBasedonDirectedAcyclicGraph[J].ReliabilityEngineering&SystemSafety，2008，93(6)：874-884.

[3]BROWNINGTR.ApplyingtheDesignStructureMatrixtoSystemDecompositionandIntegrationProblems:aReviewandNewDirections[J].IEEETransactionsonEngineeringManagement，2001，48(3)：292-306.

[4]GEORGIEVSKII，AIELLOM.HTNPlanning:Overview,Comparison,andBeyond[J].ArtificialIntelligence，2015，222：124-156.

[5]RAHMANMMH，HORIGUCHIS.HTN:aNewHierarchicalInterconnectionNetworkforMassivelyParallelComputers[J].IEEETransactionsonInformationandSystems，2003，86(9)：1479-1486.

[6] 安波，廖文和，郭宇，等.基于相关性的扩散制造任务规划方法研究[J].中国机械工程，2011，22(23)：2839-2844.ANBo，LIAOWenhe，GUOYu，etal.StudyonExtendedManufacturingTaskPlanningMethodBasedonCorrelation[J].ChinaMechanicalEngineering，2011，22(23)：2839-2844.

[7] 包北方，杨育，李斐，等.产品定制协同开发任务分解模型[J].计算机集成制造系统，2014，20(7)：1537-1545.BAOBeifang，YANGYu，LIFei，etal.DecompositionModelinProductCustomizationCollaborativeDevelopmentTask[J].ComputerIntegratedManufacturingSystems，2014，20(7)：1537-1545.

[8]GERASOULISA，YANGT.OntheGranularityand

ClusteringofDirectedAcyclicTaskGraphs[J].IEEETransactionsonParallel&DistributedSystems，1993，4(6)：686-701.

[9] 秦寿康. 综合评价原理与应用[M]. 北京:电子工业出版社, 2003:24-45.QINKangshou.PrincipleandApplicationofComprehensiveEvaluationMethods[M].Beijing:PublishingHouseofElectronicsIndustry，2003:24-45.

[10]MUC,LIY.AnIntrusionResponseDecision-makingModelBasedonHierarchicalTaskNetworkPlanning[J].ExpertSystemswithApplications, 2010, 37(3):2465-2472.

(编辑 张 洋)

Cloud Manufacturing Task Decomposition Method Based on HTN

LIU Mingzhou WANG Qiang LING Lin

School of Machinery and Automobile Engineering,Hefei University of Technology,Hefei，230009

A cloud manufacturing task decomposition algorithm was proposed herein on the basis of sequential task decomposition. Firstly, a descriptive model of manufacturing tasks and the related definitions of task constraint structures were provided were carried out. Then the researches of manufacturing task granularity analysis method, cohesion measurement method were carried out, and correlation measuring method. Then, recursive decomposition algorithm was adopted to carry out the tasks of optimization decomposition consistently, considering the task resource matching problem during the decomposition processes. Finally, feasibility and effectiveness of the proposed method was verified by an example of a gearbox test-manufacturing task decomposition.

cloud manufacturing； task decomposition； task granularity； hierarchical task network(HTN)

蒋清海，男，1986年生。南京理工大学机械工程学院博士研究生。主要研究方向为农业机械装备。发表论文3篇。E-mail:jiangqinghai101@126.com。武 凯，男，1972年生。南京理工大学机械工程学院教授。孙 宇，男，1964年生。南京理工大学机械工程学院教授、博士研究生导师。杨 栋，男，1991年生。南京理工大学机械工程学院博士研究生。

2016-04-27

TH166

10.3969/j.issn.1004-132X.2017.08.008