面向能力的层次网络计划模型构建方法

周竞涛，王明微，杨海成，敬石开

（1.西北工业大学 现代设计与集成制造技术教育部重点实验室，陕西 西安 710072；2.中国航天科技集团公司，北京 100048；3.北京理工大学 机械与车辆学院，北京 100081）

0 引言

与传统的项目管理［1-6］不同，云制造的项目管理是一种以制造能力为基本调度单元的管理机制［7］。云制造任务通过有计划地动态调用和释放云制造平台所聚集的制造能力，来逐步完成制造目标。为了实现基于制造能力的计划调度，云制造平台需要将用户提供的以活动为基本单元的任务计划转化为以能力为基本单元的任务计划，建立面向能力的网络计划模型，克服传统的以活动为管理单元的计划管理粒度粗放、不能及时捕获制造能力以及能力约束关系对计划（包括跨项目的多个计划）执行的影响等问题［7］，从而实现面向能力的项目计划监控和调度，建立面向制造能力的细粒度项目管理机制的基础。

目前，云制造领域的相关研究侧重于如何通过建立可行的服务组合规划来满足云制造的任务需求。例如：范韬提出面向单一制造任务时通过扩展语义信息和层次任务网（Semantic information and Hierarchical Task Network，HTN）来建立和评估多个云制造服务组合规划方案的方法［8］；刘波在面向云制造多任务请求模式时，从服务质量（Quality of Service，QoS）的角度研究了服务组合与优化的问题［9］；魏乐［10］研究了在云服务出现退出、失效、QoS调整下的云组合服务的自适应调整问题，通过识别异常的影响域和选择合适的服务来实现组合方案的调整。从云制造项目管理的角度看，这些研究实质上都是对如何建立满足特定云制造项目需求的服务规划的研究，可以看作是对云制造项目计划编制和调整的研究。显然，这些研究的前提均假设云制造项目的计划是直接以服务组合规划的方式来体现的。

与以上研究不同，本文认为在实际应用过程中，为了更便于用户使用，云制造项目的初始计划仍然是以传统的活动计划来体现的，希望从项目管理的角度探讨如何将传统的活动计划展现的项目过程转化为对能力（或者服务）调用的项目过程，从而为将成熟的传统项目监控与调度技术应用到云制造项目管理中建立逻辑基础。

本文在文献［7］定义的能力层次计划的基础上，讨论如何将以活动为基本单元的云制造任务计划转化为以能力为基本单元的能力层次计划。为使研究具有普遍性，本文假设云制造任务建立的活动计划允许分解为子计划，从而形成一个多级网络计划［11］，以支持各种可能的复杂计划情况。

1 云制造能力的描述与获取

从制造资源的共享角度看，使用价值体现在其能够对外提供的某种能力［7］。将这种能力称为制造能力，并在文献［7］中定义如下：

定义1 制造能力c=（product，method，resource，condition，task），即该制造能力c针对某类制造对象（product），通过一定的制造方法（method）和使用相关的制造资源（resouce），在一定条件下（condition）完成一系列制造任务（task）。详细说明请参见文献［7］。

在云制造中，制造资源的特定制造能力可以被虚拟化为具有该能力的云制造服务，在文献［7］的基础上，将云制造服务定义如下：

定义2 云制造服务（Cloud Manufacturing Service），cms=（SO，A，Mso）。

其中：

SO为服务对象，是描述一些操作的接口。由于云制造服务的能力本身可能需要人员参与，操作接口的实现会根据能力提供方式的不同而不同，例如对于需要人主导的服务（如设计服务），其接口就是实现对相关的任务承担者发送服务请求，而对服务的执行情况则是承担者通过SO的反馈接口来人工反馈执行的状态，而不是自动执行。但对于软件即服务（Software as a Service，SaaS）化类软件服务，该接口则是提供软件的调用入口，自动启动对应的服务。该主题涉及的具体情况不是本文的核心，这里不再赘述。

A是对制造服务所包含的制造能力c的语义描述，A：=SO→2C，c∈C，C为制造能力的集合。

Mso是SO与制造资源之间的映射，实现制造服务对制造资源（或者其他制造服务）在能力上的封装、发布和调用。

这样，就可以采用Web服务相关描述规范和通信协议实现对制造资源的能力进行服务化封装，服务对象SO即为通过Web 服务描述语言（Web Service Description Language，WSDL）定义的一组操作的集合，以及操作的具体实现方法。这些操作可以被分布式系统中的其他组件（服务请求者）通过简单对象访问协议（Simple Object Access Protocol，SOAP）消息调用，制造能力采用基于Web服务本体描述语言（Web Ontology Language for Service，OWL-S）的Profile进行描述。

因此制造能力描述的获取，就是在云制造服务的调用过程中对服务中的Profile部分进行解析，并将其放入对应的能力池中。

需要指出的是，本文所讨论的能力是指已经被服务化的制造资源的能力。

2 以活动为基本单元的多级网络计划模型

云制造用户建立的以活动为基本单元的多级网络计划与传统的多级活动网络模型没有本质区别，故采用类似的定义。

定义3 活动。称a=｛AID，AAttr，AD，Ain，Aout，AF，BeginTime，EndTime，DurTime，Level｝，∀a∈A为一个活动，A为活动的集合。

其中：AID为活动的唯一标识；AAttr为活动的属性集合；AD称为配置函数，AD：2Ain∪AF→2Aout；Ain为输入参数的集合，Aout为输出参数的集合；AF称为能力槽，AF：=2F是关于活动需求能力的公理性描述，F为云制造平台中聚集的所有能力的集合，例如三维模型构建活动的AF可以用公理描述为？x∧hasProperty［Capability］∧hasValue［襟翼设计］；BeginTime表示活动的开始时间；EndTime表示活动的结束时间；DurTime表示活动的设计持续时间；Level表示活动所属计划的层次。

定义4 以活动为基本单元的多级网络计划模型PPM。PPM可以分解为由n个网络计划P0i与m个活动a0j和开始节点S0、结束节点E0构成的0级网络计划，即

其中每一个P0i还可进一步分解为由ni个网络计划P1ij与mi个活动a1ik和开始节点S1i、结束节点E1i构成的1级网络计划，即

式中：PPM为0级任务，即总任务；P0i为1级任务；P1ij为2级任务。

按以上方式对任务计划进行逐层细分，直至任务被完全分解为只包含活动而不包含任何子网络计划的末级网络计划。

3 以能力为基本单元的层次网络计划模型

多级活动网络计划具有管理上分层次、编制上模块化的特点，通常是在一个主网络计划中内嵌一个或多个子网络计划。根据活动的复杂程度和使用目的的不同，可分为零级网络计划、一级网络计划与二级网络计划几种。能力网络计划同样具有以上特点，即能力在管理上分层次，并且能力与能力之间具有一定关系。下面给出能力层次网络计划的相关定义。

定义5 能力实例。称六元组r=（ID，VR，Slot，BeginTime，EndTime，Level）为能力c在调用其计划中的一个能力实例。

其中：①ID为能力实例的唯一标识。②设Attr为能力c的参数属性。若对于任何一个c.Attr，均存在一个赋值函数VR：AttrN→AttrV，代表能力c实例化的赋值过程，AttrN为能力c的参数属性名集合，AttrV为属性值集合。例如，襟翼设计能力具有结构、空气动力等设计约束属性，当调用该能力时（生成能力实例），必须给“结构设计”和“空气动力设计”属性赋值，该值就是对结构和空气动力设计的具体要求。③Slot称为能力关系槽，代表能力之间的关系，即该能力有效发挥作用所需要的其他能力。关系槽描述的是能力间的依赖关系，体现了云制造服务［7，12］对能力的组合，关于资源、能力与云制造服务之间关系的定义，请参见第1 章和文献［7］的论述。并不是所有能力都需要能力槽，独立行使功能的能力无需引用其他能力。④BeginTime表示能力实例被调用的起始时间。⑤EndTime表示能力实例终止调用的结束时间。⑥Level描述了使用该能力实例r的计划在网络计划中所处的层次。需要指出的是，尽管同一能力可以被不同层次计划使用，但这时不同计划使用的是同一能力的不同实例。

定义6 能力实例层次模型。称满足如下条件的所有能力实例构成能力实例层次模型RLM（R）：对于能力实例集合R中的任意两个能力ri与rj，如果ri.Level=rj.Level，则称能力实例集合R构成层次为Level的能力实例层次模型RLM（R）。

定义7 能力实例—活动关系模型。称满足下述条件的能力实例ri与活动集合A之间构成能力实例—活动关系RA（ri，A），

其中u=f（ai，ri）为活动能力实例引用关系，即活动ai的执行需要引用能力ri。该模型以能力实例ri为核心，获得与ri关联的活动集合A。

一个活动的执行需要引用相关的能力，以使活动顺利完成；反之，一个能力也可能被多个活动在不同的时刻调用。由于在一个活动执行过程中对能力的引用具有时序关系，可知在活动执行时，能力实例之间同样存在时序约束关系。

定义8 活动—能力实例关系模型。称满足下述条件的活动ai与能力实例集合R之间构成活动—能力实例关系AR（ai，R），

其中：R为活动ai执行时所需的能力集合，u=f（ai，ri）为活动ai对能力ri的引用。该模型以活动ai为核心，获得活动ai执行期间所需的能力实例集合R。

在给出能力实例之间的时序约束关系之前，需要将活动分割为具有串行关系的元活动的集合。把在活动执行期间只需要引用一类能力的活动称为元活动。

定义9元活动。称满足下述条件的活动aij为元活动：①活动aij执行时所需的能力实例集合为R，即满足活动能力实例约束关系AR（aij，R）；②能力实例集合R的数量为1，即｜R｜=1。由元活动定义可知元活动同样满足活动能力引用关系，但是在活动执行过程中所需能力的种类只有一个。

由活动—能力实例关系模型与元活动的定义可知，活动ai可以分为具有偏序关系的元活动ail的集合。

定义10 活动分割。给定活动ai，其活动—能力实例关系模型为AR（ai，R），R为能力实例集合，根据能力被引用的时间顺序对活动进行分割，即（aij，rij），rij∈R，其中活 动ai（j-1）与aij间满足时序约束，能力ri（j-1）与rij满足时序约束，即能力rij在活动ai执行期间与元活动aij之间一一对应。

定义11 能力实例节点网络计划简称为能力网络计划。对于给定的网络计划，其对应的活动ai及其对应的子网络计划P（ai），根据能力被引用的时序关系对活动进行分割，用分割后的活动集合替代原活动，并用能力实例节点替代每个节点，形成能力实例网络计划。

4 能力层次网络计划模型的生成

根据以上定义，能力层次网络计划模型生成过程如图1所示，主要包括如下步骤：

步骤1 构建活动—能力实例关系模型。对活动多级网络计划模型进行解析，获得各活动执行过程中所要引用的能力实例，构建活动—能力实例关系模型。

步骤2 活动分割。由活动—能力实例关系模型对各活动进行分割，将每个活动分割为多个元活动，建立元活动与对应能力实例节点以及元活动之间的时序关系。

步骤3 构建能力实例—活动关系模型。由活动—能力实例关系模型构建能力实例—活动关系模型。

步骤4 构建能力计划层次网络。

4.1 活动—能力实例关系模型的构建

用属性有向图描述活动—能力实例关系模型。

定义12 属性有向图。属性有向图为一个四元组G=（V，E，α，β）。其中：V是一个有限非空集合，其元素称为节点；E⊆V×V是一个以不同节点的有序对作为元素的有限集合，其元素称为边；α：V→WV是一个从节点集合到其属性集合的映射，其中WV是节点的属性集合；β：E→WE是一个从边集合到其属性集合的映射，其中WE是边的属性集合。

这样，活动多级网络计划可以转化为表达活动能力实例关系的属性有向图G。具体步骤如下：

步骤1 对活动多级网络计划进行预处理，获得其活动集合A=｛ai｝，1≤i≤m，其中m为活动个数。

步骤2 遍历活动集合A中的每个元素ai，同时创建一个与活动ai对应的属性有向图顶点vi，对应地将该活动的属性与活动所需引用的能力实例集合R作为该顶点的属性，并且构建活动—能力实例关系模型AR（ai，R）。

步骤3 对活动集合A中的每两个活动ai与aj，如果活动ai与aj之间存在时序约束，则表示活动ai与aj之间存在有向边，则构建顶点vi与vj之间的边e（vi，vj），并且将边的属性作为边e（vi，vj）的属性。

由定义3可知，活动的属性主要包括活动所属哪一级、开始时间、结束时间、活动的持续时间等。活动的有向边主要有两种：具有时序约束关系的活动之间具有有向边，具有层次约束关系的活动之间存在有向边。边的属性主要是这种时序约束关系。

4.2 活动分割

在云制造用户建立的以活动为基本单元的多级网络计划中，每一个活动都是通过绑定一个或多个能力（表现为云制造服务，参见文献［7］）来完成活动所规定的任务，即活动与能力实例之间是1∶n的关系，如图2所示。

图2中，活动ai调用三种类型的能力实例r1，r2和r3，活动ai+1调用能力实例r4和r5，其中ai与活动ai+1具有时序约束关系。但转换成能力层次网络计划中的能力实例节点时，却导致能力实例r1，r2和r3均对应于同一个活动ai、能力实例r4和r5均对应于同一活动ai+1的情况，从而造成时序关系转换的混乱，无法确切得出哪一个能力实例节点能够代表该活动。

为此，本文提出将活动进行分割，根据该活动调用能力的使用次序，将活动分割成若干个元活动，每一个元活动与调用的某一类能力对应。

在进行活动分割的过程中，分割的元活动集合之间的连接包括并联和串联两种。并联关系指该活动调用的能力具有并行关系，串联关系指该活动调用的能力具有串行关系，例如航天某关键部件的加工（某一活动ai）需要串行调用毛料检查、校正、数控铣、校正和划线等活动所需的能力来完成，因此把该活动ai分割成五个元活动：毛料检查元活动ai1、校正元活动ai2、数控铣元活动ai3、校正元活动ai4与划线元活动ai5。

如图3所示，活动ai在执行时所需的能力R=｛r1，r2，r3，r4｝，在活动执行过程中按照串行时间顺序对能力进行引用，因此按照元活动与活动分割的定义对活动ai进行分割，可以获得ai1，ai2，ai3，ai4共4个元活动，分别与能力r1，r2，r3和r4一一对应。

在能力实例网络计划中，每一个节点代表某一类型能力的一个实例rij，对应一个活动。转换之后，一个被分割的子网络计划作为一个整体被细分成一个子网络计划，只是被分割的子网络计划中每个元活动节点与原网络计划不同，该元活动是依据调用的能力进行分割的。根据定义3～定义6，若活动ai（j-1）与aij间满足时序约束，则对应的能力ri（j-1）与rij满足同样的时序关系，该时序关系可以通过对应活动节点与能力节点之间的BeginTime，End-Time属性的赋值获得。

通过活动分割，可以有效地保证活动与能力1∶1的调用关系，为后续能力层次网络计划的转变和分析打下基础。

4.3 能力实例—活动关系模型的构建

在上述获得的活动—能力实例关系模型AR（ai，R）的基础上，构建以能力为核心的能力实例—活动关系模型，即ARS=｛AR（ai，R）｝→RAS=｛RA（ri，A）｝。由于活动ai的执行需要引用多种类型的能力，在构建能力层次网络计划的过程中需要分别构建能力实例节点，获得与能力实例对应的活动集合。同时，设置活动—能力实例关系模型AR（ai，R）占用标识集合M，用来记录活动—能力实例关系模型AR（ai，R）是否被处理。

由活动—能力实例关系模型构建能力实例—活动关系模型的步骤如下：

步骤1 设置活动—能力实例关系模型集合ARS=｛AR（ai，R）｝中的每个活动—能力实例关系模型AR（ai，R），设置占用标识M（AR（ai，R））=0。

步骤2 取集合ARS中占用标识M（AR（ai，R））=0的元素AR（ai，R），并设置M（AR（ai，R））=1。

步骤3 遍历能力集合R=｛r1，r2，…｝中的每个元素ri：

（1）构建一个与能力ri对应的源顶点vi，对应元素ri的属性作为顶点vi的属性。

（2）如果顶点集合V中不存在与顶点vi属性相同的顶点，则将顶点加入顶点集合V中，同时将活动ai作为能力vi的依附活动，即vi←ai。

（3）如果顶点集合V中存在与顶点vi属性相同的顶点vj，则将活动ai作为能力vj的依附活动，即vj←ai。

步骤4 如果集合ARS中存在占用标识M（AR（ai，R））=0的元素AR（ai，R），则转步骤2，否则转步骤5。

步骤5 输出能力实例—活动关系模型集合RAS=｛RA（ri，A）｝。

4.4 能力实例层次关系的构建

能力计划中能力实例之间的层次关系形成一棵树，采用层次图描述。

定义13 层次图。层次图是由六元组gh=（Vh，Eh，ηh，θh，αh，βh）表示的一棵树，其中：Vh为树的节点集合；Eh⊂Vh×Vh为树的边集合，其元素为有序节点对，由父节点指向子节点；ηh：Vh→G为一个从节点集合到属性图集合的映射，对每一个节点v∈Vh，存在ηh（v）∈G，表征节点v对应的属性图，称为节点的属性图；θh：Eh→G为一个从边集合到属性图集合的映射，对每一条边e（u，v）∈Eh，存在θh（e）∈subgraph（ηh（u）），表征节点v对应的属性图与其父节点u对应的属性图之间的关系，称为边的属性图；αh：Vh→WVh为一个从节点集合到其属性集合的映射，其中WVh为节点的属性集合；βh：Eh→WEh为一个从边集合到其属性集合的映射，其中WEh为边的属性集合。

文中标记depth（gh）为层次图gh的深度；root（gh）为层次图gh的根节点；｜gh｜为层次图中所有节点对应属性图的模的和，称为层次图gh的规模；level（v）为节点v的层次；parent（v）为节点v的父节点。

定义14 能力层次图。能力层次图是一个表征能力层次网络计划模型的层次图gh=（Vh，Eh，ηh，θh，αh，βh）。其中：节点v∈Vh对应能力层次网络计划模型中不同层次下的能力网络计划；边e（u，v）∈Eh表征能力层次网络计划模型中不同层次能力网络计划u，v间的依赖关系；节点v的属性图ηh（v）∈ηh记录节点v对应的网络计划内所包含的能力节点；边e（u，v）∈Eh的属性图θh（e）∈θh记录相邻层次关联网络计划u，v间的依赖关系；αh和βh记录不同层次网络计划及网络计划之间关联关系的属性。

根据能力实例—活动关系模型RAS=｛RA（ri，A）｝建立能力层次关系，其步骤如下：

步骤1 遍历能力实例—活动关系模型集合RAS中的每个能力实例—活动关系模型RA（ri，A）：

（1）令能力ri.level的赋值等于对应活动ai.level的取值。

（2）创建一个与能力ri相对应的节点vi，如果层次图节点集合V中不存在节点vj，使得节点vi与vj满足ηh（vj）∩vi≠∅，则将顶点vi加入节点集合V中；否则将顶点vi加入ηh（vj）。

步骤2 遍历层次图gh节点集合V中的任意一个节点vi，其直接父节点记作parent（vi）。

遍历层次图gh节点集合V中的任意一个节点vj（i≠j），如果parent（vi）=vj，则构建节点vi与vj之间的依赖关系，将边e（vj，vi）加入边集合Eh。

步骤3 输出能力层次图gh，完成活动网络计划到能力网络计划的转化。

5 实例验证

本文所提方法在国家863计划“云制造服务模式与共性关键技术研究”中得到了实现。该方法以中国航天科技集团云制造服务平台为基础，以航天五院空间站总体设计云制造任务为例，开展了基本技术验证。以敏感器布局设计为例，云制造服务平台通过将制造资源实体和各种知识经验以“服务”的方式进行抽象、封装和共享，把服务作为各种业务活动功能的实现载体。利用云制造服务平台任务项目管理工具，首先将基于活动的网络计划中的最底层活动进行分割，使分割出来的元活动与所需的制造服务（即能力）的数量为1∶1的关系，如图4所示。针对每个活动，利用服务匹配引擎在云制造服务平台中匹配并绑定合适的服务（即能力），包括硬件类服务（AH 场强天线、功率放大器等设备提供的服务）、软件类服务（统一建模语言（Unified Modeling Language，UML）、CATIA（computer aided tri-dimensional interface application）、SINDA 等软件提供的服务）以及其他类型的服务，生成一系列制造服务（能力）节点，如图5所示。最后，根据能力实例节点之间的关联关系，构建出最终的面向能力的层次网络计划模型，如图6所示。

面向能力的层次网路计划模型能够清晰地描述服务（能力）之间的隶属关系，以及能力实例之间的关联和计划时序关系，将项目的活动计划转化为具有时间序列要求的能力计划，为后续云制造项目实现基于能力的监控和调度提供基础。

6 结束语

因为在云制造平台中，能力是以服务的方式发布出来的，活动对能力的需求最终体现为活动对对应服务的绑定，所以在云制造平台中，通过活动网络计划到能力网络计划的转化就将活动计划转化为服务调用计划，而对能力计划的执行与监控，就转化为对服务计划的执行与监控，本文所提算法是云制造平台服务执行引擎的关键技术。以此为基础，下一步需要进一步深入研究面向能力的计划执行、监控和调度技术。

［1］LI Junting，WANG Runxiao，YANG Yuntao.A new CCPM（Critical Chain Project Management）scheduling algorithm based on resource conflict solution［J］.Journal of Northwestern Polytechnical University，2010，28（4）：547-552（in Chinese）.［李俊亭，王润孝，杨云涛.基于资源冲突调度的关键链项目进度研究［J］.西北工业大学学报，2010，28（4）：547-552.］

［2］VAN DE VONDER S，DEMEULEMEESTER E L，HERRO-ELEN W S.A classification of predictive-reactive project scheduling procedures［J］.Journal of Scheduling，2007，10（3）：195-207.

［3］CHENG Xu，WU Cheng.Solving multi-mode project rescheduling problem with PSO algorithm［J］.Computer Integrated Manufacturing Systems，2009，15（1）：97-101（in Chinese）.［程 序，吴 澄.粒子群优化算法求解多模式项目再调度问题［J］.计算机集成制造系统，2009，15（1）：97-101.］

［4］HERROELEN W，LEUS R.On the merits and pit falls of critical chain scheduling［J］.Journal of Operations Management，2001，19（5）：559-577.

［5］LEACH L P.Critical chain project management［M］.2nd ed.London，UK：Artech House Inc.，2005.

［6］ASHTIANI B，JALALI G R，ARYANEZHAD M B，et al.A new approach for buffer sizing in critical chain scheduling［C］／／Proceedings of the 2007IEEE International Conference on Industrial Engineering and Engineering Management.Washington，D.C.，USA：IEEE，2007：1037-1041.

［7］ZHOU Jingtao，WANG Mingwei，YANG Haicheng，et al.Capability driven project monitoring and management mechanism for cloud manufacturing［J］.Computer Integrated Manufacturing Sysytems，2012，18（7）：1518-1525（in Chinese）.［周竞涛，王明微，杨海成，等.能力驱动的云制造项目监控机制研究［J］.计算机集成制造系统，2012，18（7）：1518-1525.］

［8］FAN Tao.Research on manufacturing cloud services composition based on extended HTN［D］.Chongqing：Chongqing Uni-versity，2012（in Chinese）.［范 韬.基于扩展HTN 的制造云服务组合研究［D］.重庆：重庆大学，2012.］

［9］LIU Bo.Study on multi-task oriented services composition and optimization in cloud manufacturing ［D］.Chongqing：Chongqing University，2012（in Chinese）.［刘 波.云制造环境中面向多任务的服务组合与优化技术研究［D］.重庆：重庆大学，2012.］

［10］WEI Le，ZHAO Qiuyun，SHU Hongping.Adaptive adjustment of composite cloud service based on QoS for cloud manufacturing environment［J］.Journal of Lanzhou University：Natural Sciences，2012，48（4）：98-104（in Chinese）.［魏乐，赵秋云，舒红平.云制造环境下基于QoS 的组合云服务自适应调整［J］.兰州大学学报：自然科学版，2012，48（4）：98-104.］

［11］JING Shikai，SU Qing，YANG Haicheng.Collaborative planning and controlling for aerospace multi-project［M］.Beijing：China Science and Technology Press，2010（in Chinese）.［敬石开，苏 青，杨海成.航天多型号协同计划编制与进度控制［M］.北京：中国科学技术出版社，2010.］

［12］WU Lei，MENG Xiangxu，LIU Shijun.Resource service encapsulation in manufacturing grid［J］.Computer Integrated Manufacturing Systems，2008，14（9）：1837-1844（in Chinese）.［武 蕾，孟祥旭，刘士军.制造网格中资源服务化封装方法研究［J］.计算机集成制造系统，2008，14（9）：1837-1844.］