当前, 制造业信息化正处于转型升级阶段.客户需求趋于多样化和个性化, 迫使企业由生产型向服务型转变升级^[1], 以便能够快速响应客户需求, 缩短产品开发周期, 降低研发成本, 保持市场业务敏捷性.云制造的提出, 为这种转变提供了有力支持.云制造是一种根据用户需求组织网上制造资源并提供各类按需制造服务的网络化制造新模式, 旨在应对用户不确定、动态变化的需求, 真正实现资源按需分配和使用^{[2, 3]}.云平台按需提供服务, 用户按需使用资源, 这种按需供给架构是云制造模式区别于其他网络化制造模式的核心特征.

云制造模式下, 制造需求映射成制造任务, 制造资源映射成制造服务, 制造任务通过寻租找到匹配的制造服务, 从而实现对物理制造资源的调度.制造服务通常需要以服务组合的形式来完成复杂多样的制造任务^[4].然而, 制造任务和制造服务都处于动态多变的环境中.一方面, 云制造是用户参与的制造新模式, 用户的需求贯穿于产品的全生命周期.在任何一个阶段, 用户的需求(包括功能性需求和非功能性需求)都可能发生改变, 需求的多变性很可能使制造任务无法顺利执行, 如何快速响应需求的变化, 成了亟待解决的问题.另一方面, 制造服务组合过程需要考虑资源的实际服务能力和可用性^[5], 由于制造资源的动态性, 使制造服务处于动态的环境中, 包括新的服务加入, 旧的服务演化(例如, 服务接口变化)或者消亡; 对于正在被调用的服务, 也有可能发生异常(例如, 服务失效、QoS异常).如何有效管理海量的制造服务, 提高服务系统的自适应能力, 保证服务组合的可靠性和可信性, 是云制造由理论走向成熟的重要保证.

制造任务和制造服务的动态多变对云制造系统的管理带来了严峻的挑战.目前, 对云制造环境下服务组合自适应方法缺乏深入的研究, 未形成成熟的解决方案.因此, 本文运用复杂网络相关理论, 构建制造任务-制造服务动态匹配网络理论模型, 基于此提出了制造服务组合自适应方法, 为制造任务和制造服务的动态管理提供了理论依据, 其主要贡献包括:

●  第一, 提出了动态匹配网络理论模型, 上层为制造任务网络, 下层为制造服务网络, 用于表达制造服务之间的调用关系、制造任务之间的执行关系、制造服务与制造任务之间的动态匹配关系以及各制造任务节点和制造服务节点的时间状态属性;

●  第二, 提出了一种基于动态QoS和负载的制造服务动态调度算法, 该算法通过负载队列模型对动态QoS进行评估, 以负载和动态QoS为优化目标, 将最优制造服务组合问题转化为制造服务网络中最短路径的搜索, 实现制造服务的在线分步组合;

●  第三, 提出了一种变更驱动的制造服务组合动态调整方法, 能够根据不同类型的制造服务变更和制造任务变更实时更新制造任务网络和制造服务网络, 并通过动态调度算法实现服务组合的自动调整.

本文第1节介绍相关研究.第2节给出研究问题的相关描述.第3节介绍制造任务-制造服务动态匹配网络的构建.第4节介绍基于制造任务-制造服务动态匹配网络的制造服务组合自适应方法.第5节通过实验仿真分析验证方法的可行性和有效性.第6节对全文进行总结.

1 相关研究

针对动态多变的运行环境, 不同的研究者从不同的角度提出了相应的服务组合自适应方法.Chafle等人针对执行过程中服务的失效和QoS的变化, 设计了一种服务组合和执行的自适应方法, 通过为服务组合提供多个备选方案提高对动态环境的应变能力^[6].Zeng等人提出了基于整数规划的重规划(global-replanning)的思想用于应对服务组合运行时出现的异常, 保证QoS的最优性^[7].但是重规划会带来额外的开销, 为此, Dai等人提出了一种服务组合自愈(self-healing)方法, 通过性能预测减少重选取的次数, 提升自适应性能^[8].尚宗敏等人认为:当服务发生异常时, 可以采用向前恢复或向后恢复的策略对异常进行处理, 向前恢复是指选择合适的服务替换异常服务, 向后恢复是指对已执行的服务进行补偿, 提高服务组合执行的可靠性和一致性^[9].张明卫等人提出了一种基于EQ规则的服务组合自适应方法, 通过对服务组合运行环境进行建模分析, 能够准确预测出备选服务的QoS, 提高服务组合的稳定性^[10].但是该方法依赖于初始数据的积累和对日志的定期挖掘, 本质上是一种离线QoS预测方法.吕晨等人基于服务依赖图提出了一种基于事件驱动机制的复合服务自适应方法, 可实时处理多种不同类型的动态服务, 自动地对复合服务进行检查和更新^[11].该方法只是对服务的动态变化做出自适应的更新, 没有对用户需求变化提供相应的策略且没有考虑负载因素.朱勇等人则考虑了负载对QoS的影响, 提出一种负载等级模型的动态QoS评估方法, 实现服务的动态的选择.该方法的优势在于服务的在线选取, 能够克服服务设计阶段就确定组合方案带来的负载适应性不足的问题^[12].然而仅仅考虑了服务QoS状态的变化, 并没有对任务和服务的变更进行研究, 而且服务队列的生成算法没有考虑服务之间的依赖关系, 具有局限性.

以上Web服务组合自适应方法并不能很好地运用于制造服务组合:第一, 其自身方法不够完善, 并没有提出一个系统的方法同时考虑需求和服务变更; 第二, 相比传统Web服务的运行环境, 云制造环境的复杂性和不确定性^[13]更加突出; 第三, 制造资源的种类更加复杂多样, 加之某些硬制造资源(例如机床)且具有独占性^[14], 即一个制造服务只能被一个任务占用.因此, 制造服务组合的自适应问题也已成为研究热点^[15-22].目前, 研究主要集中在两个方面.

(1)   在制造服务组合规划阶段, 通过提升组合服务方案的柔性来提高其动态适应能力.Guo等人对制造服务组合的柔性度量方法进行研究, 包括制造任务柔性、制造服务柔性、QoS柔性、制造服务关系柔性和工作流柔性, 并验证了具有柔性的制造服务组合具有更高的执行成功率^[15].苏凯凯等人也提出了制造服务组合柔性指标, 包括应对制造任务变化的能力、应对制造服务变化的能力和服务评价这3个柔性指标, 并通过双层规划模型对制造资源进行优化配置^[16].Liu等人构建了面向制造资源的CPS框架, 通过及时感知制造资源的服务能力, 并通过目标效能与实际效能的偏差触发自适应机制, 实现制造资源重新组合^{[17, 18]}.然而, 这些研究都基于一个前提, 即制造服务组合是预先规划好的, 致使制造服务组合的动态环境适应性不足(例如负载适应性差等).

(2)   在制造服务组合执行阶段, 通过合适的策略对制造服务组合进行动态调整.Mourtzis等人提出了一种事件驱动的自适应框架, 通过云制造车间的实时监控实现工艺规划的动态调整^[19].马文龙等人构建了云制造服务组合异常处理模型, 将异常分为任务需求变化、任务挂起、服务过载、服务故障、服务退出、QoS异常等6大类, 通过模型对不同类型的异常进行捕获, 并给出了相应的调整方法^[20].邰丽君等人根据制造环境下的扰动事件, 提出了一种遗传蚁群算法动态资源优化调度技术, 能够应对制造环境的动态变化^[21].李京生等人针对车间生产中频发的突发事件, 建立了快速响应机制, 提出了基于时间容忍度最小化和移动处理方式的动态方案调整技术^[22].当前的自适应方法对于服务之间的交互关系、任务之间的执行关系、服务与任务之间的匹配关系考虑不足, 导致各服务组合之间是孤立的, 自适应策略很可能会失败.事实上, 云制造平台是一个复杂系统, 需要新的方法对任务和服务进行管理.

2 问题描述 2.1 基本概念

定义1(制造服务节点负载). 制造服务节点负载(L)是指当前制造服务处理的制造任务个数.制造服务最大负载(L_max)是指能够承受的最大制造任务个数, 一旦超过最大负载, 服务将拒绝任务请求.随着制造任务的到来和执行完成, 制造服务节点的负载是随时间不断变化的.

定义2(制造服务质量). 制造服务质量(quality of service, 简称QoS)是指制造服务的非功能属性, 是服务组合的重要依据.常用的QoS指标分为两类:消极指标和积极指标^[23].消极指标包含响应时间、成本等, 在服务组合中需要最小化; 积极指标包括可靠性、可信度等, 在服务组合中需要最大化.在制造服务的QoS会受到执行环境(例如负载情况)的影响, 也是动态变化的.

2.2 问题场景

本节给出了一个制造服务组合的问题场景, 如图 1所示.对于一个制造任务序列T₁→T₂→T₃, 需要从C₁, C₂, C₃这3个服务类中分别挑选出一个合适的服务来构建服务组合.每个服务类中包含若干个功能相同或相似但QoS不同的服务.图 2中, 箭头表示各制造服务间的潜在调用关系, 例如, S₁和S₄存在潜在调用关系, 可以进行服务组合; S₃和S₄不存在潜在调用关系, 不能进行服务组合.

根据服务之间的潜在调用关系, 可以选择不同的服务组合方案来执行任务.例如, S₁→S₄→S₈是一个满足用户需求的服务组合方案.假设某时刻t, 用户需求发生变更需要调整正处于执行状态的制造任务T₂, 导致制造服务S₄无法满足要求, 需要重新选取制造服务.本例中, 只能选取S₅替代S₄, 由于S₅与S₈之间不存在潜在调用关系, 致使S₈也需要被替换.可见, 传统的服务组合方法需要对多个服务同时进行替换, 付出的代价较高, 很难适应动态环境的变化.考虑另外一种情况:当服务S₁发生异常而失效时, 需要把S₁的制造任务迁移到其他服务节点, 如S₂.此时, S₂的负载增加, 执行性能可能受到影响, 进而影响其所在服务组合的执行, 导致实际的QoS下降(例如执行时间增加); 因此, 服务组合的调整策略需要考虑负载以及QoS的动态变化.

下面给出本文所讨论问题的描述:在多个制造业务流程交互的复杂环境下, 考虑服务之间的交互关系、任务之间的执行关系、服务与任务之间的匹配关系, 基于动态QoS和动态负载实现最优制造服务组合的构建; 当变更发生时, 以制造任务和制造服务的动态变化为驱动, 进行自动调整, 保证各个制造任务的顺利执行且满足QoS需求.

3 动态匹配网络

近年来, 复杂网络以其强大的学科交叉能力受到了越来越多研究者的青睐.已有研究表明, 由Web服务构建的关系网络具有“小世界”和“无标度”特性^[24-26].云制造系统中, 海量的制造服务交互形成复杂的关系网络.作为研究复杂系统的工具, 复杂网络已被用于解决云制造的供需匹配问题, 取得了一些进展, 为后续的研究提供了一个新的视角^{[27, 28]}.把制造任务和制造服务作为网络中的节点, 任务与任务的执行关系、服务与服务的调用关系、任务与服务间的匹配关系作为边, 构建云制造模式下的制造任务-制造服务网络.本文借鉴了文献[27]的建模思想, 以其任务-服务超网络为参考, 并对其进行了改进, 提出了一个适用于服务组合自适应的动态匹配网络模型.为了便于阐述, 下面给出动态匹配网络的一些基本概念.

3.1 制造任务网络

定义3(原子制造任务). 原子制造任务(atomic manufacturing task, 简称AMT)是指不可再分的细粒度制造任务, 能够通过调用一个原子制造服务执行完成, 记为T.一般情况下, 企业的制造任务都是粗粒度的, 记为T^c, 云制造平台可以通过一定的策略将其分解成一系列具有执行序列关系的原子制造任务.

定义4(制造任务执行边). 制造任务执行边(manufacturing task executive edge, 简称MTEE)表示由同一个粗粒度制造任务T^c分解得到的各原子制造任务之间的执行序列关系, 为加权有向边, 记为${E^T} = \{ w_{ij}^T\} $, 其中, $w_{ij}^T = 1$表示制造任务T_i和制造任务T_j之间存在执行序列关系.

制造任务的基本执行关系可以分为顺序、并发、选择和循环这4种结构^[29].事实上, 基于制造任务之间的执行关系, 不同粗粒度的制造任务可以表示为相互独立的制造任务子网络^[27], 记为G_i={T_i, E_i}.

定义5(制造任务网络).  制造任务网络(manufacturing task network, 简称MTN)可以表示为由各相互独立的制造任务子网络组成的有向无环网络, 记为Net^T={G₁, G₂, G_i, ..., G_n}, 其中, n表示不同的制造任务子网.

定义6(制造任务社团).  制造任务社团(manufacturing task community, 简称MTC)是指由相同或相似的原子制造任务组成的任务类, 可以根据任务之间的相似度聚类得到, 记为${C^T} = \{ T_1^C, T_2^C, ..., T_n^C\} $, 其中, n表示不同的原子制造任务.

制造任务网络是由众多制造任务子网构成的, 是管理企业复杂制造业务流程的网络模型.每一个制造任务子网G_i都代表了企业用户的一套制造业务流程, 是由企业当下的业务需求映射得到, 并随着时间不断演化.对于云制造平台中的企业用户, 其制造业务流程是长期存在的, 但何时需要执行具有随机性.当执行时, 需要调用相应的制造服务来完成.总之, 制造任务网络展示了任务之间的执行拓扑关系, 即网络的静态结构属性; 同时, 用于记录了制造任务的执行状态, 即动态执行属性.不同的时刻, 原子制造任务处于不同的执行状态(T_status), 分为已执行(T_status=0)、待执行(T_status=1)、正执行(T_status=2)和未执行(T_status=3)这4种状态.

3.2 制造服务网络

定义7(原子制造服务). 原子制造服务(atomic manufacturing service, 简称AMS)是指可以被独立调用且功能不可再分的细粒度制造服务, 记为S.

云制造平台中, 制造服务来自于不同的提供商, 服务粒度具有多样性.制造服务既可以由具有单一功能的制造资源映射而成, 也可以由具有复杂功能的制造资源映射而成.对于前者, 我们称之为细粒度制造服务, 即原子制造服务; 对于后者, 我们称之为粗粒度制造服务, 记为S^c.本文把粗粒度制造服务S^c分解成由多个原子制造服务组合而成的复合服务, 因此, 制造服务网络中只存在原子制造服务.

定义8(制造服务依赖边). 制造服务依赖边(manufacturing service dependency edge, 简称MSDE)是指根据原子制造服务之间的潜在调用关系得到加权有向边, 记为${E^S} = \{ w_{ij}^S\} $, 其中, $w_{ij}^S = 1$表示制造服务S_i和制造服务S_j之间存在潜在调用关系.原子制造服务之间的潜在调用关系与服务之间的接口依赖、兼容性、服务提供者之间合作情况等都有关系.

定义9(制造服务网络). 制造服务网络(manufacturing service network, 简称MSN)可以表示为由原子制造服务和制造服务依赖边组成的有向无环网络, 记为Net^S={S, E^S}.

定义10(制造服务社团). 制造服务社团(manufacturing service community, 简称MSC)是指由一群功能相同或相似但QoS不同的原子制造服务组成的服务类, 可以根据服务之间的功能相似度聚类得到, 记为${C^S} = \{ S_1^C, $ $S_2^C, ..., S_n^C\} $, 其中, n表示不同的原子制造服务.因此, 每一个制造服务社团包含了用于执行特定任务类的所有服务.换言之, 制造任务社团和制造服务社团是一一对应的.

制造服务网络是对制造服务进行统一管理的全局依赖网络模型.每一个网络节点代表一个原子制造服务, 不同的制造服务节点之间通过调用关系构建有向依赖边.通过制造服务网络, 可以对来自不同服务提供者的制造服务进行动态调度, 为用户提供个性化的动态服务组合方案.制造服务网络不仅展示了制造服务之间的潜在调用关系, 即静态结构属性, 同时也记录了制造服务节点的调用状态, 制造服务的状态(S_status)可分为未被调用(S_status=0)和正在被调用(S_status=1)两种, 具体体现为制造服务节点负载的变化.

3.3 动态匹配网络

定义11(网络层间动态匹配边). 网络层间动态匹配边(Inter-network dynamic matching edge, 简称INDME)是指连接制造任务网络和制造服务网络的加权无向边, 表示原子制造任务T和原子制造服务S之间的动态匹配关系, 记为${E^{TS}} = \{ w_{ij}^{TS}\} $, 其中, $w_{ij}^{TS} = 1$表示制造任务T_i与制造服务S_j处于动态绑定状态, 即制造任务T_i正在调用制造服务S_j.当制造任务T_i正在调用制造服务S_j时, 在制造任务T_i与和被调用的制造服务S_j之间产生一条动态匹配边; 当制造任务T_i完成时, 匹配边消失, 表现了网络的时变特性.

定义12(动态匹配网络). 动态匹配网络(dynamic matching network, 简称DMN)是由制造任务网络和制造服务网络的动态匹配关系形成的双层网络, 记为Net^TS={Net^T, Net^S, E^TS}.其中, T代表原子制造任务, S代表原子制造服务, Net^TS表示动态匹配网络, Net^T表示制造任务网络, Net^S表示制造服务网络, E^TS制造任务网络和制造服务网络之间的动态匹配边.

本文提出的动态匹配网络(dynamic matching network, 简称DMN)是对文献[27]提出的供需匹配网络(supply-demand matching hyper network, 简称SDMHN)的继承和扩展, 存在以下主要区别:第一, 在动态匹配网络DMN中, 层间匹配边随着任务的执行和完成而动态出现和消失, 体现了制造任务与制造服务之间的动态匹配关系, 而SDMHN实际上是静态匹配网络, 层间边表示每个制造任务与每个制造服务之间的可匹配关系, 体现了超边的静态连接特性; 第二, 在DMN中, 制造服务网络是一个有向网络, 主要是对服务之间的潜在调用关系进行建模, 是一个全局的依赖关系网络, 用于制造服务组合的搜索和构建, 这与SDMHN中的无向加权服务网络也有所区别; 第三, 在任务-服务匹配规则上, 在DMN中, 只存在2种动态匹配关系, 即一对一、多对一, 这是由于在动态匹配网络中, 制造任务都是原子制造任务, 即一个原子制造任务调用一个原子制造服务就能完成, 而一个制造服务可以同时被多个制造任务调用, SDMHN表示的是可匹配关系, 存在4种基本可匹配关系, 即一对一、一对多、多对一、多对多.

总之, 动态匹配网络体现了制造任务和制造服务之间匹配关系的时间特性, 同时记录了节点的时间状态属性(制造任务的执行状态和制造服务的负载状态), 更能体现网络的动态特性和时变特性, 适用于动态环境下的制造服务组合.

4 制造服务组合自适应方法

根据上节的描述, 制造服务组合自适应可表述为以下3个阶段:首先, 根据制造任务和制造服务分别构建制造任务网络和制造服务网络, 基于制造服务动态调度算法形成t₁时刻的动态匹配网络; 其次, 通过对制造任务和制造服务的监控获取变更, 并对变更进行预处理, 动态更新制造任务网络和制造服务网络; 最后, 调用制造服务动态调度算法, 实现层间匹配边的更新, 完成服务组合的自动调整, 形成t₂时刻的动态匹配网络.图 3为制造服务组合自适应方法的基本原理.

图 3中, 制造服务组合自适应方法包含两大核心模块:变更获取与预处理模块和制造服务动态调度模块, 下面将对这两大模块进行详细阐述.

4.1 变更获取与预处理

通过对制造任务和制造服务的监控, 实时获取其动态变化, 并对不同类型的变更(指原子变更)进行预处理, 然后从网络拓扑结构(以邻接矩阵存储)和节点状态(以向量存储)两方面更新制造任务网络和制造服务网络, 并确定待执行的制造任务, 为下一步制造服务的动态调度做准备.需要指出的是, 制造任务与制造服务节点状态的变更会互相影响.

制造任务变更从类型上分为制造任务的增加(T_add)、删除(T_delete)和修改(T_modify).由于制造任务网络是由一系列制造任务子网构成, 通过对一个或者多个制造任务子网的更新, 实现整个制造任务网络的更新, 且每个制造任务子网的更新是独立的, 制造任务子网更新算法见算法1, 其更新具体过程为:确定当前正在执行的制造任务T_i之后(第1行~第5行), 开始处理不同类型的制造任务变更.首先, 处理制造任务的增加, 若增加任务节点T_j在当前执行任务T_i之前, 更改T_i为未执行状态, T_j为待执行状态, T_i调用的服务节点S_i的负载L_i减1;否则, 直接在制造任务子网中增加节点和相应的执行边(第6行~第16行).其次, 处理制造任务的删除, 若需要删除的制造任务T_j处于执行状态(T_j=T_i), 则T_i调用的服务节点S_i的负载L_i减1, 其后续节点T_i+1变为待执行状态; 否则, 直接在制造任务网络中删除相应的任务节点和执行边(第17行~第23行).然后处理制造任务的修改, 若需要修改的制造任务T_j处于执行状态(T_j=T_i), 则首先删除原有制造任务, 然后将修改后的制造任务当作新增的任务加入制造任务网络, 并将其状态改为待执行状态, T_i调用的服务节点S_i的负载L_i减1;否则直接删除原有制造任务, 然后将修改后的制造任务当作新增的任务处理(第24行~第32行).最后, 得到更新后的制造任务子网和受影响的制造服务节点负载(第33行).

算法1.制造任务子网更新.

输入:制造任务子网结构矩阵A, 制造任务状态向量T_status, 任务数量u, 变更任务T_j.

输出:更新后的制造任务子网结构矩阵A₁, 更新后的制造任务状态向量T_status1, 更新后的受影响的制造服务节点负载L_i.

1.  FOR k₁=1 to u do

2.    IF T_status[k₁]=2

3.      i←k₁

4.    ENDIF

5.  ENDFOR

6.  IF manufacturing task T_j∈T_add THEN

7.    A₁=addTnode(A, T_j)

8.    IF i < j THEN

9.      T_status[j]←3

10.    ELSE

11.      T_status[i]←0

12.      T_status[j]←1

13.      L_i←L_i-1

14.    ENDIF

15.    T_status1←T_status

16.ELSE IF manufacturing task T_j∈T_delete THEN

17.  A₁=deleteTnode(A, T_j)

18.    IF i=j

19.      L_i=L_i-1

20.    ENDIF

21.      T_status1←T_status

22.ELSE IF manufacturing task T_j∈T_modify THEN

23.    IF i=j

24.      tempA=deleteTnode(A, T_i)

25.      L_i=L_i-1

26.      A₁=addTnode(tempA, T_j)

27.      T_status[i]←1

28.    ELSE

29.      A₁=deleteTnode(A, T_i)

30.    ENDIF

31.    T_status1←T_status

32.END IF

33.Return A₁, T_status1, L_i

对于制造服务变更, 从类型上分为新服务加入(S_add)、服务失效(S_failure)、服务演化(S_evolve), 制造服务网络更新算法见算法2.类似制造任务的处理方式, 首先处理新服务S_j的加入, 在制造服务网络中增加相应的服务节点和依赖关系边(第1行~第4行).其次, 处理服务失效S_j:若失效服务S_j处于调用状态, 由于一个制造服务可以被多个制造任务子网中的任务同时绑定, 所以首先在制造服务网络中删除相应的服务节点和依赖边, 然后将其所对应的制造任务或者制造任务集CT_i更改为待执行状态; 否则, 直接删除服务节点和依赖边(第5行~第18行).然后处理服务演化(假设处于执行状态的服务不发生演化), 这里主要考虑接口变化和QoS变化(不包括因负载导致的QoS波动), 首先删除原有的服务, 然后将演化后的服务按新服务加入处理(第19行~第22行).最后, 得到更新后的制造服务网络和受影响的制造任务状态(第23行).

算法2.制造服务网络更新.

输入:制造服务网络结构矩阵B, 制造服务状态向量S_status, 受影响的制造任务数量num, 变更服务S_j.

输出:更新后的制造服务网络结构矩阵B₁, 更新后制造服务状态向量S_status1, 更新后的受影响制造任务集状态CT_status.

1.  IF manufacturing service S_j∈S_add THEN

2.    B₁=addSnode(B, S_j)

3.    S_status[j]=0

4.    S_status1←S_status

5.  ELSE IF manufacturing service S_j∈S_failure THEN

6.    B₁=deleteSnode(B, S_j)

7.    IF S_status[j]=1

8.      FOR k=1 to num do

9.        G_k=getG(CT_i[k])

10.        FOR u=1 to u_k do

11.          IF T_status[u]=2

12.            T_status[u]←1

13.          ENDIF

14.        ENDFOR

15.        CT_status[k]←T_status[u]

16.      ENDFOR

17.    ENDIF

18.    S_status1←S_status

19.ELSE IF manufacturing service S_j∈S_evolve THEN

20.    tempB=deleteSnode(B, original S_j)

21.    B₁=addSnode(tempB, evolved S_j)

22.ENDIF

23.Return B₁, S_status1, CT_status

4.2 制造服务动态调度

制造服务动态调度模块主要包含两个功能:第一, 基于负载和动态QoS完成动态匹配边的构建; 第二, 根据变更对动态匹配边进行自动更新.

4.2.1 基本原理

采用传统的服务组合方法(本文称之为静态调度方法), 即根据制造需求构建制造任务流程, 再基于任务流程制定满足QoS需求的制造服务组合策略, 然后根据组合策略一步步执行, 很难适应动态多变的运行环境.因此, 本文提出了一种制造服务动态调度方法.制造服务动态调度不同于传统的静态调度方法, 其本质是制造服务的在线分步组合, 两者执行过程如图 4(a)和图 4(b)所示.

图 4(a)为制造服务静态调度方法, 根据任务序列(T₁→T₂→T₃), 确定当前最优的服务组合方案(S₁→S₃→S₇), 然后按照绑定的组合方案一步步执行, t₁时刻调用服务S₁, t₂时刻调用服务S₃, t₃时刻调用服务S₆, 直到最后一个任务(T₃)执行完成.图 4(b)为制造服务动态调度方法, 其基本原理是根据当前环境动态绑定服务, 是一个分步服务组合过程.t₁时刻根据任务序列的第一个任务(T₁), 调用服务S₁; t₂时刻根据当前运行环境调用绑定服务S₄; t₃时刻调用服务S₆.

4.2.2 动态负载

制造需求方总是希望在调用成本一定的条件下获取QoS最优的服务或服务组合, 导致优质的制造服务被频繁地调用且负载量往往较高.实际情况下, 制造服务的负载能力是有限的, 这决定了整个制造服务网络的的负载能力也是有限的.合理的负载分布可以改善制造服务网络承载能力, 提高网络节点的利用率, 使制造资源利用最大化, 这也是云制造的重要理念之一.

为更好地衡量制造服务的负载情况, 本节提出了一种负载队列模型.每一个制造服务节点需要维护两个队列, 即任务执行队列和任务等待队列, 如图 5所示.

任务执行队列表示制造服务节点正在并行处理的制造任务, 记为Q_e, 采用先进先出的执行方式, 即任务先到先处理; 任务等待队列表示处于等待执行的制造任务, 记为Q_w.只有当任务执行队列处于空闲状态时, 任务等待队列中的任务才能进入执行状态.实际情况下, 受到制造资源自身条件的限制, 任务执行队列和任务等待队列的长度都是有限的, 其容量分别记为Cap_e和Cap_w, 则L_max=Cap_e+Cap_w.因此, 对于某一时刻的制造服务网络, 其所能承受的总负载量是一定的.

4.2.3 动态QoS评估

制造服务的动态调度以QoS作为重要依据, 由于制造服务的QoS指标多样性, 例如响应时间、成本、可靠性等, 且单位和范围差别较大, 为了以全局最优的角度评估QoS的属性值, 通常需要将QoS值进行归一化处理, 即QoS效用^[7], 计算方法如公式(1)或公式(2).

$U({S_{ji}}) = \sum\limits_{k = 1}^r {\frac{{Q_{j, k}^{\max } - {q_k}({S_{ji}})}}{{Q_k^{\max } - Q_k^{\min }}}} \cdot {w_k}$

(1)

$U({S_{ji}}) = \sum\limits_{k = 1}^r {\frac{{{q_k}({S_{ji}}) - Q_{j, k}^{\min }}}{{Q_k^{\max } - Q_k^{\min }}}} \cdot {w_k}$

(2)

其中, w_k为QoS的各项属性值的权重, 表示用户对各属性的偏好程度; $Q_{j, k}^{\max }$表示制造服务社团C_j中QoS第k维属性最大值; $Q_{j, k}^{\min }$表示制造服务社团C_j中QoS第k维属性最小值; $Q_k^{\max }$表示所有服务社团中QoS第k维属性最大值; $Q_k^{\min }$表示所有服务社团中QoS第k维属性的最小值; q_k(S_ji)表示候选服务S_ji中QoS第k维属性值.为方便后文阐述, 本文选用公式(2)进行计算.

制造服务的服务质量具有动态性, 不同的时刻, 由于制造服务所处的环境不同, 其QoS会发生波动.例如, 低价的制造服务往往具有更高的任务数量, 从而导致较长的任务排队时间^[29].本文采用负载队列模型对QoS进行动态评估, 并选取两个典型QoS指标:响应时间和成本.其中, 成本不受负载状态影响, 在服务调用过程中是不变的; 响应时间包括等待时间和服务时间^[30], 随着负载的增加, 等待时间增大, 从而使响应时间变大, 具体计算公式如公式(3).

$ \left\{ {\begin{array}{*{20}{l}} {\Delta {t_r} = \Delta {t_s} + \Delta {t_w}}\\ {\Delta {t_w} = (y + 1) \cdot \Delta {t_s} + {t_x}}\\ {x = {L_Q}\% {C_e}{\rm{ }}({\% _{{\rm{取余}}}})}\\ {y = [({L_Q} - 1)/C], {\rm{ }}{L_Q} \ge 1{\rm{ }}({{[]}_{{\rm{取整}}}})} \end{array}} \right. $

(3)

其中, Δt_r表示服务的响应时间; Δt_s表示制造服务的服务时间, 其值由制造资源的执行性能决定, 为常数; Δt_w表示当前任务的等待时间; t_x表示制造任务执行队列中T_xe执行完成需要的时间, L_Q表示任务排队队列的任务个数.

由上可知, 通过负载队列模型可以评估不同负载状态下的响应时间, 进而实现制造服务动态QoS评估.

4.2.4 制造服务动态调度优化模型与算法

制造服务的动态调度有两个优化目标:第一, 从用户的角度, 云制造平台需要为用户提供QoS最优的制造服务或服务组合; 第二, 从云制造平台管理的角度, 在多用户环境下, 通过合理调度资源, 优化负载队列, 实现各制造服务节点负载均衡.下面给出制造服务动态调度的优化模型, 为便于描述, 我们假设当前制造任务流程需要调用的服务社团数量为N, 每个服务社团所含的服务个数为n.因此, 建立制造服务动态调度基本数学模型如公式(4):

$\left\{ {\begin{array}{*{20}{l}} {{\text{Object Min}}\left( {{W_1} \cdot \sum\limits_{j = 1}^N {\sum\limits_{i = 1}^n {U({S_{ji}})} } + {W_2} \cdot \sum\limits_{j = 1}^N {\sum\limits_{i = 1}^n {L({S_{ji}})} } } \right) \cdot {x_{ji}}} \\ {{\text{Subject to }}\sum\limits_{j = 1}^N {\sum\limits_{i = 1}^n {{q_k}({S_{ji}}) \cdot {x_{ji}} \leqslant Con{s_k}} } , 1 \leqslant k \leqslant r} \\ {\sum\limits_{i = 1}^n {{x_{ji}}} = 1, {x_{ji}} = \{ 0, 1\} } \end{array}} \right.$

(4)

其中, r表示服务的QoS属性个数; k表示第k维属性; U(S_ji)表示制造服务S_ji的效用函数值(由于本文选用的是消极QoS指标, 且采用公式(2)进行计算, 故对QoS效用进行最小化优化); L(S_ji)表示制造服务S_ji的当前负载; Cons_k表示第k维属性的约束值; x_ji为决策变量, x_ji=1表示制造服务S_ji被选中, x_ji=0表示制造服务S_ji未被选中; W₁和W₂为权重, 且W₁+W₂=1.

本文借助复杂网络最短路径路由策略^[31]思想对上述模型进行求解.寻找全局最优的服务组合可以转化为从制造服务网络中搜寻一条代价最小的服务组合路径, 这里的代价函数即为公式(4)中需要优化的目标函数.我们假设在制造服务网络中, 每个制造服务节点都具有接收、执行、转发任务的功能, 当一个任务执行完成时, 自动为下一个任务寻找合适的制造服务, 直至最后一个任务执行完成.该过程的具体算法实现见算法3, 具体原理如下.

●  首先, 由制造任务子网中任务执行状态(T_status)确定制造任务序列T=(T_m, T_m+1, …, T_n), 其中, T_m为待执行制造任务, T_m+1~T_n为未执行制造任务, 并根据T选择需要调用的制造服务社团C^S=(C_m, C_m+1, …, C_n)(第1行、第2行);

●  其次, 获取需要调用的服务社团中各个服务S_ji的负载L_ji, 并根据负载队列模型对制造服务的QoS进行动态评估, 更新服务组合代价矩阵MatrixC(第3行~第10行);

●  然后, 基于最短路径算法从制造服务网络中选出满足制造任务约束Cons_n-m的代价最小的服务组合SC=(S_ji, S_j+1,i, …, S_ni)(第11行~第13行);

●  最后, 将制造任务T_m与制造服务S_ji动态绑定(第14行).

算法3.制造服务动态调度.

输入:制造任务执行状态T_status, 制造任务约束Cons_n-m, 服务组合代价矩阵MatrixC.

输出:最优制造服务S_ji.

1.  T=getExetask(T_status)

2.  C^S=getComunity(T)

3.  FOR j=m to n do

4.    len=getLength(C_j)

5.    FOR i=1 to len do

6.      L_ji=getLoad(S_ji)

7.      QoS_ji=updateQoS(L_ji)

8.    END FOR

9.  END FOR

10.MatrixC=updateMatrix(L_ji, QoS_ji)

11.MinPath=minPath(MatrixC, Cons_n-m)

12.SC←MinPath

13.S_ji←SC[1]

14.Return S_ji

5 实验与分析

云制造模式下, 制造服务涵盖了产品全生命周期的各个阶段, 是包含设计服务在内的大制造概念^[32].为了验证本文制造服务组合自适应方法的有效性, 以课题组开发的电梯云制造平台为基础, 目前, 该平台中部署了面向电梯企业设计人员的电梯设计服务, 包含计算服务、分析服务和知识服务:计算服务主要用于零部件的结构设计和选型校核; 分析服务主要用于零部件的静力分析和动力学分析; 知识服务主要用于一些设计标准和设计参数的查询.在电梯设计研发过程中, 设计人员通过云制造平台调用所需的设计服务, 完成设计任务.本节以电梯核心子系统曳引系统的设计服务组合为例, 对服务组合自适应优化算法进行验证.图 6为一个完整的垂直梯曳引系统设计业务流程, 共包含16个设计任务:(1)曳引方案设计; (2)曳引机功率计算; (3)曳引机速度校核; (4)曳引机扭矩校核; (5)主轴负荷应力分析; (6)曳引轮与钢丝绳直径比压校核; (7)曳引轮等效数量查询; (8)导向轮等效数量计算; (9)滑轮等效数量计算; (10)曳引钢丝绳安全系数计算; (11)曳引钢丝绳破断载荷校核; (12)曳引绳轮包角计算; (13)摩擦系数查询; (14)当量摩擦系数计算; (15)轿厢两侧拉力计算; (16)曳引条件校核.

要完成这16个设计任务, 需要从相应的16个服务社团中调用合适的设计服务, 每个服务社团包含若干个功能相同或相似但QoS不同的设计服务.例如, 设计任务2需要调用计算服务; 设计任务4需要调用分析服务; 设计任务7需要调用知识服务.图 6是一个顺序和并发组成的混合结构, 可以使用文献[29]的方法转化为如图 7所示的顺序结构.例如, T₃可以看成任务3~任务5的合并, 只需对QoS指标进行重新计算, 具体计算方法可参看文献[29], 这里不再赘述.值得一提的是, 转换后的顺序结构验证方便, 且并不会影响实验效果.

5.1 实验环境配置

实验环境为一台ThinkPad SL400 CPU/4G/32位/Win7.所有仿真实验均采用Matlab2014a完成求解, 具体实验参数见表 1.

仿真实验始终设置3种对比执行算法:算法1为本文算法, 按制造服务动态调度算法进行服务组合, 变更发生时进行自动调整(TPMSCSAA); 算法2按制造服务静态调度算法进行服务组合(不失一般性, 采用文献[6]提出的经典全局优化算法), 变更发生时采取重规划(global-replanning); 算法3采用文献[12]的动态选择算法进行服务组合, 由于其本身算法不包含自适应, 故变更发生时按其算法进行重选取(LADSSM-replanning).仿真实验每1s取一次样, 共执行50s, 实验数据均是执行100次的平均值.

5.2 实验结果与分析

为了方便分析, 本文提出了制造任务执行成功率、制造服务社团负载均衡度、全局负载队列优化能力和制造服务组合平均QoS效用这4个评价指标.

(1) 制造任务执行成功率(R_mtsr)

制造任务的执行成功率是指满足端到端的QoS约束的已执行完成的制造任务所占的比例, 按公式(5)计算:

$ {R_{mtsr}} = {N_s}/{N_f} $

(5)

其中, N_s表示满足端到端QoS约束的制造任务数量, N_f表示所有已完成的满足功能性需求的制造任务数量.制造任务执行完成的判断依据是该制造任务子网中最后一个任务执行完成.

该指标体现了制造服务组合算法对动态环境的适应能力.图 8为3种算法在不同任务到达速率下(取m=20, n=50)的制造任务执行成功率.

由图 8可知, 在制造任务到达速率较低(λ=10)时, 3种算法的执行成功率差距较小, 因为此时各制造服务节点的负载对QoS的影响较小.随着制造任务平均到达速率的增加, 负载不断增加, TPMSCSAA算法的执行成功率下降速度最慢, 明显优于其余两种算法.在负载较高(λ > 80)时, 执行成功率还能保持在75%以上, 且优于其余两种算法60%以上.可见, 本文算法对动态环境具有很好地适应能力.主要原因在于TPMSCSAA算法考虑了制造服务网络中的服务的依赖关系以及制造服务节点的负载状态.而LADSSM-Replanning算法虽然对服务组合实行了在线优化, 却忽略了服务之间的潜在调用关系; 传统的Global-Replanning算法没有考虑服务节点的负载状态及其对QoS的影响, 导致了执行成功率下降明显, 动态适应性不足.

(2) 制造服务社团负载均衡度(S_l)

制造服务社团负载均衡度表示同一个制造服务社团内各服务节点的负载偏差情况, 具体按公式(6)计算:

${S_l} = \sqrt {\frac{1}{n}\sum\limits_{j = 1}^n {{{\left( {L(j, t) - \frac{1}{n}\sum\limits_{j = 1}^n {L(j, t)} } \right)}^2}} } $

(6)

其中, L(j, t)表示t时刻制造服务节点的负载, n表示服务社团内服务的个数.

该指标体现了制造服务组合算法对负载均衡的局部优化能力, 即对同一类制造资源的合理利用程度.图 9为不同任务平均到达率的制造服务社团类负载均衡度(限于篇幅, 仅展示C₂, C₆这两个制造服务社团的负载均衡度, 其余类似, 取m=20, n=50;λ=30, 60, 90req/s).

由图 9可知, TPMSCSAA算法对负载的局部优化能力最佳, 其次为LADSSM-Replanning算法, Global- Replanning算法最差.在低负载下(图 9(a)和图 9(b)), TPMSCSAA算法和LADSSM-Replanning算法在运行一段时间后, 负载均衡度能保持在相对平稳的状态, 说明两种算法都对负载具备适应能力.但总体来说, TPMSCSAA算法优于LADSSM-Replanning算法, 因为前者对制造服务网络中的负载队列和服务的动态QoS同时进行了优化, 而后者仅仅通过基于负载等级的QoS进行服务的动态选取, 因此负载的优化效果相对较差.随着负载的增加, 在中等负载(图 9(c)和图 9(d))和高负载(图 9(e)和图 9(f)), TPMSCSAA算法优势更为明显, 且负载均衡度能够始终处于稳定, 图中维持在1上下, 说明本文算法更有利于制造资源的合理使用.因为此时负载对QoS产生的影响逐渐增大, 在保证QoS满足要求的前提下, TPMSCSAA算法通过选择次优的服务来减少负载对QoS的影响.

(3) 全局负载队列优化能力(GA_LQ)

全局负载队列优化能力表示对制造服务网络中各服务节点负载队列的优化程度.本文采用全局负载排队队列长度G_Qw和拥塞服务节点数量N_congest这两个指标进行评估.全局负载排队队列长度用于评估任务等待队列中制造任务的数量, 该值越小, 表示任务全局等待的时间较小, 任务执行的效率较高, t时刻的负载队列排队长度按公式(7)进行计算(其中, num表示制造服务总数, Q_w表示任务等待队列长度):

${G_{{Q_w}}}(t) = \sum\limits_{i = 1}^{num} {{Q_w}(i, t)} $

(7)

拥塞服务节点数量用于评估制造服务网络中处于满载状态的节点个数.当服务节点处于满载状态时, 其不再接受任何任务请求.因此, 满载节点越多, 网络的可用节点数量就越少, 可用性越差.具体按公式(8)进行计算:

${N_{congest}}(t) = \sum\limits_{i = 1}^{num} {a(i, t)} , {\text{ where }}a(i, t) = \left\{ {\begin{array}{*{20}{l}} {1, {\text{ if }}L(i) = {l_{\max }}} \\ {0, {\text{ if }}L(i) < {l_{\max }}} \end{array}} \right.$

(8)

图 10为不同时刻(取m=20, n=50;λ=30, 60, 90req/s)下的全局负载排队队列长度和拥塞服务节点数目.

由图 10(a)、图 10(c)、图 10(e)可知, TPMSCSAA算法对全局排队队列的优化能力远远高于其余两种算法, 在较短的时间内就能使负载排队队列保持稳定的状态, 即使在制造任务量较大(λ=90)的情况下, TPMSCSAA算法还能使负载排队队列长度稳态值保持在35上下, 而Global-Replanning算法和LADSSM-Replanning的稳态值分别为1150和550左右.可见:本文算法能使服务网络的总体任务等待数量较小, 从而降低了负载对QoS(响应时间)的影响, 提高了服务网络的执行效率和制造任务的执行成功率.同时, 由图 10(b)、图 10(d)、图 10(f)可知, TPMSCSAA算法能够有效避免服务节点的拥塞, 通过对负载队列的优化, 减少对优质QoS服务的过度调用, 在服务网络负载容量一定的情况下, 使资源的可用性大幅度提高.

(4) 制造服务组合平均QoS效用(AU_QoS)

平均QoS效用是指对于所有执行成功的制造任务所对应的制造服务组合的QoS效用的平均值, 按公式(9)进行计算:

$A{U_{QoS}} = \frac{{\sum\limits_{i = 1}^{{N_s}} {U{{(SC)}_i}} }}{{{N_s}}}$

(9)

其中, N_s表示满足端到端QoS约束的制造任务数量; U(i)代表制造服务组合的QoS效用, 其值按公式(10)计算:

$U(SC) = \sum\limits_{k = 1}^r {\frac{{{q_k}(SC) - QSC_k^{\min }}}{{QSC_k^{\max } - QSC_k^{\min }}}} \cdot {w_k}$

(10)

其中, q_k(SC)表示服务组合中第k维属性值, $QSC_k^{\max }$表示所有执行成功的制造服务组合中QoS第k维属性最大值, $QSC_k^{\min }$表示所有执行成功的制造服务组合中QoS第k维属性的最小值.由于本文选取的是消极指标, 按公式(10)计算得到的服务组合QoS值越小, 代表QoS优化效果越好.因此, AU_QoS的值越小越好.该指标体现了制造服务组合算法对QoS的优化能力.图 11为3种算法在不同制造任务到达速率下的平均QoS效用值.

由图 11可知, 随着制造任务平均到达速率的增加, Global-Replaning算法和LADSSM-Replanning算法上升速度较快, 在λ > 40之后, 表现出相同的变化趋势, 制造服务组合的平均QoS产生大幅度的波动; 而TPMSCSAA算法由于对负载进行了优化, 制造服务组合的平均QoS上升缓慢, 随后(λ > 70)逐渐趋于平稳.在负载较高(λ > 90)时, TPMSCSAA算法会略高于其余两种算法.原因在于在满足端到端QoS约束, 保证全局制造任务的执行成功率的前提下, TPMSCSAA算法选择了较次优的制造服务.

6 结论及未来的工作

本文以复杂网络的视角, 研究了云制造系统中制造任务与制造服务的动态管理, 构建了动态匹配网络理论模型, 基于此, 提出了一种三阶段的制造服务组合自适应方法(TPMSCSAA).该方法能够通过负载队列模型对QoS进行动态评估, 以负载和动态QoS为优化目标, 将最优制造服务组合问题转化为制造服务网络中最短路径的搜索, 实现制造服务的动态调度.同时, 根据实时获取的制造任务变更和制造服务变更动态更新制造任务网络和制造服务网络, 然后基于动态调度算法实现制造服务组合的自动调整.通过对电梯设计服务组合的验证, 从制造任务执行成功率、制造服务社团负载均衡度、全局负载队列优化能力和制造服务组合平均QoS效用证明了TPMSCSAA对动态环境具有很好的自适应能力.值得一提的是, TPMSCSAA不仅可以运用于像电梯设计服务之类的软制造资源, 也可以运用于机床加工等具有独占性的硬制造资源, 只需将服务执行队列的容量设置为1即可.此外, 对于服务时间较长(几天乃至数月)的制造业务流程, 制造资源的变动更加频繁, TPMSCSAA可以根据动态环境在线分步组合, 更具灵活性.

未来的工作将对以下几方面作深入研究:(1)由于本文动态QoS模型只考虑响应时间和成本, 下一步将研究其他QoS指标, 如可靠性、可信度与负载之间的关系, 提升动态QoS模型的通用性; (2)进一步研究服务网络中统计特性(如节点的度、介数等)对服务组合的影响, 对自适应方法进行优化.