时序约束下面向混合任务的制造云服务组合优化*

刘 志，龚本刚，唐 娟，桂云苗

(安徽工程大学 管理工程学院, 安徽 芜湖 241000)

时序约束下面向混合任务的制造云服务组合优化*

刘 志，龚本刚，唐 娟，桂云苗

(安徽工程大学 管理工程学院, 安徽 芜湖 241000)

针对面向混合任务的制造云服务组合问题，建立了优化模型并提出求解算法。首先对该问题流程进行了描述，分为混合任务分解，候选云服务推荐和云服务组合优化三个步骤；其次，以整体服务质量最优为目标建立该问题的优化模型。根据问题的特点，使用改进遗传算法对其进行了求解，同时在这一算法中采用基于扩展子任务排序的双层编码和POX交叉算子。最后，通过在服务资源丰富和受限两种情况下的仿真实例验证了优化模型和算法的可行性和有效性。

云制造；服务组合；服务质量；时序约束；混合任务

0 引言

随着国际化市场竞争加剧与信息技术的快速发展，制造模式正经历着由原先依赖企业内部制造资源向借助信息技术和网络技术充分利用外部制造资源的变化。以应用服务提供商(Application Service Provider, ASP)、制造网格[1](Manufacturing Grid, MGrid)等为代表的网络化制造模式取得成效，但因提供的资源服务类型、数量、能力和使用方式有限[2]，使得基于网络化制造的信息共享不畅、资源利用率不高、产品设计中知识重用及创新力不足，制约了其应用的推广和发展。为此，李伯虎在融合先进制造模式与技术及云计算、物联网、虚拟化、语义Web和服务计算等信息技术的基础上，提出了一种面向服务、高效低耗、基于知识的网络化智能制造新模式——云制造。云制造将制造资源和制造能力虚拟化、服务化，构建一个资源、能力的共享协同与按需使用的制造服务云体系[3-6]。

在实际应用中，制造云服务的需求日趋多样化和复杂化，使得功能相对单一的制造云服务已经无法满足应用需求，因此，将多个制造云服务组合成一个功能更强大的服务成为了一种必然选择[5]。然而，由于云制造系统中存在大量具有相同制造功能和不同服务质量的制造云服务，使得服务组合成为一种典型的NP-hard问题[7]。

云制造系统中同时收到的多个任务可分为异类型、同类型和混合型三种[5]：异类型是指各制造任务的所有子任务序列不同；同类型是指各任务之间有完全相同的子任务序列；混合型是指各制造任务之间有部分相同的子任务序列，共享部分候选制造云服务集合，其中混合型任务最符合实际情况也最为复杂。同时，制造任务对制造云服务的使用时间较长[7]，任务之间存在时序约束和共享候选云服务问题，使得云服务状态在服务组合执行过程中实时变化，而现有研究主要针对系统中空闲云服务资源，较少考虑已分配任务的云服务在执行空闲时间段可再次分配任务的情况，导致候选云服务未能得到充分的利用。因此，本文针对面向混合任务的制造云服务组合问题(Hybrid-task oriented manufacturing cloud service composition, HTO-MCSC)，在充分考虑时序约束和云服务实时状态变化的前提下，构建云服务组合优化模型和求解算法，以充分利用候选云服务，提高服务组合效率和质量。

1 HTO-MCSC问题

1.1 HTO-MCSC问题描述

云制造系统同时接受多个不同类型制造任务请求时，其服务组合过程复杂多变，为了便于分析和优化，进行以下约束来简化HTO-MCSC问题：

(1)制造任务分解得到的原子任务有着一定的时序约束，并按时序关系顺序执行；

(2)各制造云服务(包括硬资源和软资源)，在完成指定的子任务后，经短暂调整后能够重新被释放，并可再次使用，调整时间记入服务执行时间；

(3)已分配任务的云服务在执行未开始前的空闲时间段，能够执行其他制造任务并尽可能早执行。

时序约束下HTO-MCSC的流程可以描述如下：

1)混合任务分解

云制造系统收到由多个不同类型制造任务执行请求组成的混合任务集T={T1,T2,…,Ti, …,Tm}，任意制造任务Ti(i=1,2,…,m)分别具有相应的服务质量需求，可用服务质量约束向量Ci表示，Ci={Ci1,Ci2,…,Cij,…,Cil},其中l表示服务质量约束数量，Cij(j=1,2,…,l)为第j个服务质量约束指标。制造任务按照其子任务序列和产品BOM逐层分解，得到一系列关联的、存在于系统中的云制造原子任务为原子云任务链，Ti分解的原子云任务链Ti={ATi1,ATi2,…,ATij, …,ATin}，其中n表示该任务链的原子数量，ATij为Ti分解的第j个原子任务。

2) 云服务推荐

3) 时序约束下云服务组合优化

将各制造企业在云制造平台提供的云服务，根据原子任务链的时序关系，按照一定顺序组合形成的一个整体服务链，称之为云制造服务链。在该服务链中，每个节点都是由制造服务的时序约束关系对应的任务来确定。云制造系统中任务与云服务之间的组合是一个多目标优化问题，对于服务质量的不同方面需要做出平衡，不同服务质量属性具有各自的权重，可用向量Wi={Wi1,Wi2,…,Wih}来表示。HTO-MCSC问题的优化目标是为每个制造任务都分配最合适的制造服务，确定每个服务的最佳编排顺序和服务开始时间，使整个系统的服务质量达到最佳。

1.2 HTO-MCSC优化数学模型

在构建HTO-MCSC优化数学模型之前，首先明确两个相关概念及其运算过程。

(1) 服务质量QoS的集成和预处理

假设服务组合优化目标采用的标准是：目标函数数值越大，性能越佳。但服务质量QoS的属性有正属性和负属性之分，其中，正属性是指数值越大、性能越佳的属性，负属性则相反；同时每种属性的量纲也不同，因此，需对云制造服务的QoS进行预处理。系统选择时间T、成本C、合格率P和可靠性R作为QoS属性，其中，T和C是负属性，P和R为正属性，可靠性R使用服务被成功执行的次数Nc与服务总请求执行次数的K的比值Nc/K表示。此时，服务质量约束向量Ci包含时间T、成本C、合格率P和可靠性R四个方面，分别用Cit、Cic、Cie和Cir表示，则Ci={Cit,Cic,Cie,Cir}。

(1) 表1 服务质量属性的集成

对于任意任务Ti的服务质量QoSi可采用简单加权法[9]进行预处理，具体见公式(2)～(5)，预处理后的各服务质量不仅方向一致，同时具有统一量纲。

(2)

(3)

(4)

(5)

(2) 整体服务质量TQoS

(6)

服务组合优化目标为整体服务质量最佳，HTO-MCSC优化问题的数学模型可构建如公式(7)所示。

(7)

2 改进遗传算法求解HTO-MCSC优化问题

某汽车零部件区域云制造系统中，零部件L具有两种不同的型号A和B，其中型号A的原子任务链为“分装—总装—测试”，型号B的原子任务链为“分装—总装”。系统中有8个候选制造服务，在t1时刻，系统同时接受到由2个A和1个B组成的制造任务集{T1，T2，T4}(此时为资源丰富情况)；在t2时刻，系统同时接受到由3个A和2个B组成的制造任务集{T1，T2，T3，T4，T5}(此时为资源受限情况)；t1时刻与t2时刻任务相互独立。所有制造任务分解及对应的候选服务质量QoS如表2所示，要求为两种情况下的所有制造任务分配服务。本文使用改进遗传算法对HTO-MCSC优化问题进行求解，资源丰富和受限两种情况下，改进的遗传算法同样适用，为便于说明，算法中的编解码和交叉变异操作仅分析较为复杂的资源受限情况。

表2 制造任务分解及候选服务QoS

任务原子任务候选服务和服务质量QoSCS5CS6CS7CS8T1AT11————AT12(7,2,0.99,0.95)(5,8,0.97,0.99)—AT13——(3,5,0.95,0.96)(6,5,0.96,0.99)T2AT21————AT22(5,2,0.96,0.95)(4,8,0.97,0.99)——AT23——(4,5,0.95,0.96)(7,5,0.96,0.99)T3AT31————AT32(6,2,0.99,0.96)(8,8,0.97,0.99)——AT33——(7,6,0.95,0.96)(8,6,0.97,0.97)T4AT41————AT42(5,7,0.99,0.95)(6,7,0.97,0.93)——T5AT51————AT52(8,7,0.99,0.95)(9,7,0.99,0.96)——

2.1 编码与解码

编码与解码是指染色体和服务组合方案之间进行相互转换。根据HTO-MCSC问题的特点，采用一种扩展的基于子任务排序的双层编码，上层是基于子任务排序的编码，它是用来确定子任务的执行顺序；下层是基于服务分配的编码，该编码中的服务按每个子任务顺序进行排列，它是用来给每个子任务分配合适的服务。结合这两层编码，可以得到HTO-MCSC问题的一个可行解，图1为针对表2中混合制造任务的一个编码实例。

本文将一个插入式贪婪解码过程扩展到制造云服务组合优化中，以确定解码后能生成活性组合方案，插入式贪婪解码算法描述如下：首先按照子任务的执行顺序进行解码，然后将每个子任务分配到其对应的制造云服务上，并尽可能早的进行服务执行，按照这种方式编码，直到所有子任务都分配在最合适的制造云服务。

图1 扩展的基于子任务排序的编码

2.2 交叉与变异操作

交叉是将种群中个体中的某些基因随机进行交接，以产生新的基因组合，交叉的目的是将优良的基因进行组合，以使子代较好地继承优良的父代基因。对于两层编码分别采用不同的交叉操作。对于基于子任务排序上层编码部分，采用POX (Precedence Operation Crossover)交叉算子[10]进行操作；POX交叉算法中P1和P2代表两个父代染色体，C1和C2代表交叉后生成的子代染色体。POX交叉操作过程如图2所示，具体流程如下：

(1) 随机将所有的任务集合划分为两个非空的子集J1和J2；

(2) 复制P1包含在J1的任务到C1，P2包含在J2的任务到C2，并保留它们的位置不变；

(3) 复制P2包含在J2的任务到C1，P1包含在J1的任务到C2，并保留它们的位置不变。

图2 POX交叉操作

变异操作的目的是改善算法的局部搜索能力，有助于维持进化群体的多样性，防止算法过早陷入局部最优。针对扩展的基于子任务排序的编码特点，对于两部分编码分别采用不同的变异操作。针对基于子任务排序编码部分，采用是插入变异操作：首先在此编码部分随机选择一个子任务，将它随机地插入到另一个子任务的前面，同时保持所有基于服务分配编码不变。针对基于服务分配编码部分，随机选择两个位置上的服务基因，然后在该位上子任务的可选服务集合中随机选择其他服务进行替代。

2.3 适应度函数

(8)

2.4 改进遗传算法步骤

智能优化算法是解决NP问题的有效方法，本文使用遗传算法作为基本算法对HTO-MCSC问题进行优化计算，但是遗传算法存在收敛速度慢，容易陷入局部最优的缺陷，因此，需要对遗传算法进行改进。本文设计了一种改进遗传算法，其具体求解流程图可以表示如图3所示。

该算法融入了粒子群算法的“极值”概念，即在遗传算法进行交叉算法时设置一个个体极值染色体和一个全局极值染色体，在染色体进行交叉运算时以一定概率按照个体极值和全局极值进行更新，即首先求出所有染色体的适应度作为其第一代个体极值，然后在个体极值中寻找最大的作为全局极值，在循环迭代过程中，算子按照一定概率与个体极值和全局极值进行交叉运算。

图3 改进遗传算法的求解流程图

3 仿真分析

以表2中的实例数据为实验对象，使用Matlab7.0编写服务资源丰富和受限两种情况下的仿真验证程序。用户在云制造系统中提交制造任务时，需同时给出服务质量约束条件和服务质量重要度评分，评分结果经处理后可得到各服务质量权重，其结果如表3所示。针对算例，设定遗传算法的初始种群规模为50，交叉概率为0.8，迭代次数为200代，资源丰富和受限两种情况下的仿真结果分别如图4和图5所示。

表3 各制造任务约束条件和服务质量权重

通过仿真结果发现，在服务资源丰富情况下，所有制造任务在无需等待下都得到了完成，总执行时间为13天；在服务资源受限的情况下，总运行时间为18天，部分制造服务以连续运用的方式进行服务组合以满足所有任务请求，例如CS1、CS3和CS7等运用2次。

图4 资源丰富下的制造云服务组合优化结果

4 结束语

针对时序约束下面向混合任务的制造云服务组合HTO-MCSC问题，论文在描述其流程的基础上建立了多目标优化数学模型，并使用改进遗传算法进行求解，特别是提出一个扩展的基于子任务排序的双层编码方式，并通过仿真实例验证了优化模型和算法的可行性和有效性，这对云制造系统的运行具有一定的实际指导意义。

本文在一定程度上解决了云制造服务组合的静态优化问题，但是，在实际组合过程中，系统将面临各种不确定因素的干扰。下一步将对各种不确定因素进行详细分析，构建制造云服务组合的动态优化机制，以提高服务组合的鲁棒性和自适应性。

[1] TAO F, ZHAO D M, HU Y F, et al. Resource service composition and its optimal-selection based on particle swarm optimization in manufacturing grid system[J]. IEEE Transactions on Industrial Informatics, 2008, 4(4):315-327.

[2] 贺东京，宋晓，王琪，等. 基于云服务的复杂产品协同设计方法[J]. 计算机集成制造系统，2011，17(3)：533-539.

[3] 李伯虎，张霖，王时龙，等. 云制造——面向服务的网络化制造新模式[J]. 计算机集成制造系统，2010，16(1)：1-8.

[4] 李伯虎，张霖，任磊，等. 云制造——面向服务的网络化制造新模式[J]. 计算机集成制造系统，2010，16(1)：1-16.

[5] 刘卫宁，刘波，孙棣华. 面向多任务的制造云服务组合研究[J]. 计算机集成制造系统，2013，19(3)：199 -209.

[6] 陶飞，张霖，郭华，等. 云制造特征及云服务组合关键问题研究[J]. 计算机集成制造系统, 2011, 17(3): 477-486.

[7] 杨晨. 基于QoS的多目标服务组合算法[J]. 计算机工程与设计，2011，32(4)：1322-1325.

[8] ZENG L, BENATALLAH B, NGU A HH, et al. QoS-aware middleware for Web Services Composition[J]. IEEE Transactions on Software Engineering, 2004, 30(5): 311-327.

[9] ZHANG L Z, GUO H, TAO F, et al. Flexible management of resource service composition in cloud manufacturing[C]// IEEE International Conference on Industrial Engineering and Engineering Management. Washington, D.C.,USA: IEEE Computer Society, 2010: 2278-2282.

[10] 张超勇，饶运清，刘向军，等. 基于POX交叉的遗传算法求解Job Shop调度问题[J]. 中国机械工程，2004，15(24)：2149-2153.

(编辑 赵蓉)

Hybrid-task Oriented Manufacturing Cloud Service Composition Optimization with Time-sequence Constraint

LIU Zhi, GONG Ben-gang, TANG Juan，GUI Yun-miao

(School of Management Engineering, Anhui Polytechnic University, Wuhu Anhui 241000, China)

Aiming at the Hybrid-task oriented manufacturing cloud service composition (HTO-MCSC) problem, an optimization model and a solution algorithm are established and proposed. Initially, the procedure of this problem is described, which includes hybrid task decomposition, manufacturing cloud service recommendation and cloud service composition optimization. Secondly, the optimization model is established by aimed at the optimal integrated quality of service. According to the characteristics of the problem, the improved genetic algorithm is used to solve it and meanwhile the double coding and Precedence Operation Crossover (POX) operator, which are based on the extension the sub-task sorting, are adopted in this algorithm. At last, two simulation examples verified the feasibility and effectiveness of the optimization model and algorithm both under resources abundant and limited circumstances.

cloud manufacturing; service composition; quality of service; time-sequence constraint; hybrid task

1001-2265(2014)06-0138-05

10.13462/j.cnki.mmtamt.2014.06.038

2013-10-14；

2013-11-18

国家自然科学基金资助项目(71171002，71371012); 教育部人文社会科学研究项目(13YJA630021); 安徽高校省级自然科学研究项目(KJ2013B033); 安徽高校省级人文社会科学研究项目(SK2013B066)

刘志(1985—)，男，安徽肥西人，安徽工程大学讲师，主要从事CIMS、制造过程优化与控制、生产系统建模与仿真等研究，(E-mail)liuzhi0551@126.com。

TH166；TG65

A