基于改进被囊群算法的云制造分包服务组合研究

唐天兵，陈永发，蒙祖强

(广西大学 计算机与电子信息学院，广西 南宁 530004)

云制造最早由中国学者李伯虎等[1]提出，结合云计算和物联网等新兴技术，将分布于各地的制造资源进行整合，提升制造服务质量，促进制造产业良性发展。云制造平台面向区域、行业或企业，借助先进的信息技术，实现对产品制造全生命周期的相关资源的整合，发布标准、规范、可共享的制造服务。随着相关技术不断完善，云制造正在成为“互联网+制造业”实践的重要形式。另一方面，随着制造业不断发展，大规模制造任务变得越来越普遍，其核心要求大批量、短周期、低成本，但需在短时间内完成大批量任务，只有少数大企业能够完成。由于缺乏竞争，且大企业运营成本偏高，因此制造费用一般较高。在传统制造业中，我国充分借鉴欧美发达国家做法，通过专业的分包运营管理，可有效加快任务进度，减小制造成本，降低项目风险[2]。在云制造环境中，存在大量各种类型的制造服务，更有利于分包任务分配，发挥任务分包的优势，但如何将制造任务分配到不同的制造服务，使效益最大化是一个需要解决的问题。

近年来，分包模式已被广泛应用于解决各类制造业生产问题。苑彬彬[2]针对装备制造业的安全、质量、成本与工期问题，分析分包运营管理的基本概念，探讨现代装备制造企业的项目管理方式，对制造业分包项目运营管理提出改进措施。Wang 等[3]为提高制造效率，降低制造费用，将制造任务分解为内部机器生产和分包商机器生产的作业，并提出以总制造周期和费用最小为目标的调度方案。尽管研究人员对制造业分包模式，以及其他云制造资源优化调度方案[4-7]进行了大量研究，但没有涉及云环境中大规模制造任务问题，主要有两方面原因：一是研究人员对规模经济的片面理解导致大规模制造任务的问题被掩盖，片面地认为生产规模越大，投入的制造资源越优质，生产效率则越高，制造成本也越小；二是通过将大规模任务简单拆分为多个并行执行子任务来减轻问题的影响，导致该问题的研究价值无法显著体现。尽管大规模制造任务问题具有隐蔽性，但是根据成本理论分析，生产成本由固定成本与边际成本构成，当固定成本的增长量大于边际成本的减少量时，规模经济将会变得不经济[8]，即任务规模越大，单位成本将越高。通过简单的任务拆分虽然可以在一定程度上缓解制造周期和成本偏高问题，但如果不能进行合理的任务分配，则无法实现效益最大化，并且可能导致风险蔓延。

本文提出一种云制造分包服务组合方法，通过将大规模制造任务分包，将制造任务进一步拆分为更小的单元，从总承包商的视角，以任务包为维度，优化分包服务组合，旨在解决大规模制造任务执行周期长、成本高的问题。完成一个分包任务，需要经历需求发布、分包方案发布、服务匹配、服务组合4 个阶段。云制造平台中的总包商基于采购方需求，制作并发布分包方案，云制造平台注册的制造服务匹配分包方案。云制造平台根据分包方案要求的功能属性和非功能属性匹配一个或多个制造企业，但是在服务匹配环节中，多个服务组合都能满足分包方案要求，如何选择最优的分包服务组合是个NP-hard 的组合优化问题[9]，一般采用群体智能算法解决。

为高效解决云制造分包服务组合优化问题，本文对Kaur 等[10]提出的被囊群算法 (tunicate swarm algorithm，TSA) 进行改进。被囊群算法是受深海中被囊生物觅食行为启发而提出的群体智能算法，目前已经被用于解决各种优化问题。Sharma 等[11]利用TSA 算法识别光伏组件的参数；Rizk-Allah 等[12]提出了求解大规模非线性优化问题的增强型TSA算法。与此同时，TSA 算法作为近年新提出的群体智能算法，同样存在收敛精度低、寻优性能不足等局限性，目前已提出多种改进TSA 算法。例如，屈迟文等[13]提出信息共享的记忆被囊群算法；史鸿锋等[14]提出精英反向黄金正弦被囊群优化算法。虽然文献[13]和文献[14]的改进被囊群算法对寻优能力都有一定提升，但也存在问题：文献[13]的改进方法过度依赖初始参数，不同的初始参数值对算法性能影响非常大，使算法的适用场景范围缩小；文献[14]的改进算法在每一次迭代过程中每个粒子需要计算两次适应度值，导致算法执行耗时较长。本文针对被囊群算法存在的问题进行改进，提出一种改进被囊群算法 (modified tunicate swarm algorithm，MTSA)，用于求解云制造分包服务组合优化问题。

1 云制造分包服务组合描述

1.1 云制造分包服务组合流程

云制造分包服务组合流程如图1 所示。某制造服务采购方需采购一项或多项制造任务，由于工作量太大，且制造周期和成本控制要求较高，云制造标准平台无法匹配到能独立完成任务的制造服务，则在云制造标准平台发布可分包的制造任务。有意向的总包商制定分包方案，在云制造分包平台进行发布，有意向承接分包任务的制造企业在分包平台提交意向书。分包平台根据分包服务组合评价模型，对各分包服务组合进行评价，向发布分包方案的总包商推荐最优分包服务组合。总包商在分包平台选择分包服务组合，将组合作为整体，向标准平台提交任务意向书。云制造标准平台以任务为维度评价收到的意向书，向采购方推荐候选的服务组合。采购方选择有意向的总包商，在云制造标准平台发出订单，云制造分包平台自动向分包商发出订单，总包商和全部分包商接受并签署订单，则服务调度完成。

图1 云制造分包服务组合流程Figure 1 Composition processes of cloud manufacturing subcontracting services

分包服务组合中的服务为并行执行，分包服务调度模式依靠并行执行和调整单个服务的工作量能够缩短总制造时间。分包模式的云制造服务组合方法能够有效降低制造服务吞吐量要求。对于一般的制造任务，当吞吐量要求较高时，则只能选择较大规模的制造企业，大企业由于运营成本高以及品牌溢价，制造单价偏高，通过降低吞吐量要求，则可选的制造服务数量增多，提升了云制造平台制造成本调节空间。

1.2 云制造分包服务组合问题描述

1) 制造任务。服务采购方在云制造标准平台发布分包任务，Task={Taski|i=1,2,3, ··· ,N}表示分包任务集合，其中N表示任务数，Taski表示第i项任务。

2) 分包方案。有意向承接Taski任务的总包商在云制造分包平台制定并发布分包方案。Taski任务的分包方案集合GCi={, ··· , G Ci p, ··· ,}，其中表示Taski的第p个分包方案，Mi表示Taski的分包方案的数量。分包方案描述了总承包商对分包服务组合的制造周期、成本控制的期望和对分包商资质、生产能力的要求。

3) 分包服务。有意向按照分包方案p承接Taski任务 的 制 造 服 务 集 合MCSi,p={, ··· ,, ··· ，}，其中表示集合中第k个服务，Wip表示MCSi,p中可选服务数量。每一个分包服务都对应一组服务描述信息Q() ={q1(),q2(), ··· ,qj()}，其中qj() 表示Taski任务第p个分包方案下第k个服务第j维服务属性，例如吞吐量、单价、可靠性、可用性等。

4) 分包服务组合。共同完成同一个分包方案的一个或多个分包服务构成一个分包服务组合。分包方案分包数量为n时的服务组合集合CMCSi,p,n=表示集合中第l个组合，Ln表示CMCSi,p,n中的服务组合的数量，Ln=(C为组合符号)。分包方案需要设置最小分包数量nl、最大分包数量nu，则每个分包方案存在个服务组合，分包服务组合问题如图2 所描述。每个分包服务组合包含1 个或多个分包服务，每个分包服务可以属于一个或多个分包服务组合，中的服务集合SMCSi,p,n,l= {, ··· ,, ··· ,}，SMCSi,p,n,l为 集 合MCSi,p的子集，其中表示服务组合中的第r个服务。总包商选择最佳分包服务组合后，将服务组合作为整体在云制造标准平台提交任务Taski的承接意向书。

图2 云制造平台分包服务组合问题描述Figure 2 Descriptions of cloud manufacturing platform subcontracting service composition

在服务组合选择方面，若存在多个分包服务组合都能完成Taski任务，并且从不同维度评价都是最优的，则无法直接选择最佳组合。比如从制造周期维度评价，组合A 是最优的；从成本控制维度评价，组合B 是最优的；从风险控制维度评价，组合C 是最优的。从总包商角度出发，如何选取最佳的分包服务组合，是能否中标Taski任务，实现利润最大化和降低风险的关键。为选择最优服务组合，以总包商视角分析，以时间最短、成本最少、风险最小为目标，制定基于综合制造水平的分包服务组合优化模型。表1 定义了系统模型所用的服务属性符号及描述。

表1 云制造分包服务组合属性符号及描述Table 1 Attribute symbols and descriptions of cloud manufacturing subcontracting service composition

2 云制造分包服务组合优化模型

云制造分包任务最重要的特征是制造产品数量大，分包服务评价指标应该以吞吐量最大化为首要原则，在控制成本的前提下，提高服务质量，降低交付风险，因此对分包服务组合采用基于综合制造水平的评价模型。

2.1 云制造服务组合任务分配

为了保证吞吐量最大化，服务组合中每个制造服务分配的任务量由该服务的吞吐量占总体吞吐量的比重决定。通过式 (2) 计算服务吞吐量占服务组合总体吞吐量的比重，即服务被分配的任务量占总体任务量的比例。

其中，fth(x) 是计算服务x吞吐量函数，x( ωi)表示服务x的属性值。η() 为计算服务的吞吐量占服务组合整体吞吐量的比重的函数，n为服务所属服务组合的服务数量。

2.2 云制造分包服务组合评价指标

1) 制造时间评价。对于一般的制造任务，制造时间主要包括产品的加工时间和完工后的运输时间。云制造分包服务组合制造时间评价模型为：

其中，STime() 是服务组合的制造时间，由组合中制造时间最长的服务决定；Tprocess(x)是计算服务x的加工时间的函数；Ttran(x) 是计算服务x的运输时间的函数；η (x) 表示服务x被分配的制造任务量占全部任务量的比例，通过式 (2) 计算。

2) 制造成本评价。对于一般的制造任务，服务成本主要包括加工成本和运输成本，其评价模型为

其中，SCost() 是服务组合的总制造成本；Cprocess(x) 是计算服务x加工成本的函数；Ctran(x) 是计算服务x运输成本的函数。

3) 持续生产能力评价。云制造服务组合持续生产能力主要从服务可用性、信用度、合格率方面评价，评价模型为

其中，SQuality()是服务组合持续生产能力指标；n为组合中服务数量；Ii,p为分包方案中设置的管理风险系数，取值为(0,1) 之间，Ii,p值越小，代表每增加一个分包需付出的额外管理风险越大，整体Qos 随n的增加下降得越快；fav(x) 是计算服务x可用性的函数；fhi(x) 是计算服务x信用度的函数；fpass(x) 是计算服务x历史任务合格率的函数。

2.3 云制造分包服务组合评价模型

对上述指标标准化，基于综合制造水平的分包服务组合评价目标模型见式 (13)，优化目标是使指标最小化。

其中，为服务组合基于综合制造水平整体评价；Tmax() 为分包方案要求的最长制造时间，Cmax() 为分包方案要求的最大费用预算；分别为分包方案GCi,p设置的制造时间、制造成本、持续生产能力指标权重，各指标权重之和为1。通过采用文献[15]的层次分析法获取指标权重，将时间、成本、持续生产能力作为高层级指标，将业主需求、产品类型、商务策略等因素作为次层级指标，自底向上分析权重。例如业主更关注制造周期，则增加时间指标权重；产品制造工艺复杂，则增加持续生产能力指标权重；总包商希望通过低价策略打开市场，则增加成本指标权重。

在真实场景中，由于分包服务质量、水平参差不齐，因此需对式 (13) 进行先行约束，分包服务组合模型约束条件可描述为

其中，Smin() 为分包方案设定的持续制造能力最低水平。

3 改进被囊群算法

3.1 被囊群算法

被囊群算法寻优过程主要包括喷气推进和群体行为，其中喷气推进需要满足3 个条件：避免个体之间的冲突，向最佳邻居移动，以及向最佳个体位置聚集。被囊群算法具体流程如图3 所示。

图3 被囊群算法流程图Figure 3 Flowchart of TSA

1) 避免个体之间冲突。被囊群在搜索食物过程中，为了避免个体之间的搜索冲突，用式 (15) 计算个体新的位置向量。

其中，A为避免个体冲突计算的新位置向量；c1、c2、c3为 (0,1) 之间的随机数；Amin、Amax表示被囊群进行群体互动的初始速度和从属速度，初始值分别为1 和4。

2) 向最优邻居方向移动。在避免种群中个体冲突后，种群个体向最优邻居方向移动。在种群移动时，需要计算种群个体与最优个体的距离，其计算方式如式 (16) 所示。

其中，表示第i个个体在第t次迭代时向最优个体聚集的位置，表示第t次迭代时的种群中最优个体位置，表示第i个个体在第t次迭代时与种群最优个体的距离。

3) 向最优个体位置聚集。种群中个体确认与最优个体距离及新的位置向量后，被囊群采用式 (17)方式开始向最优个体位置聚集。

4) 群体行为。在被囊群向最优个体位置聚集时，为了从数学上模拟被囊群的群体行为，通过式(18) 定义被囊群的群体行为：

3.2 改进被囊群算法

针对被囊群算法在搜索过程中，仅围绕全局最优个体进行收敛，搜索范围小、种群多样性差，导致搜索精度不高的问题。本文对被囊群算法进行改进。

1) 个体信息共享。被囊群算法中的群体智能行为主要采用式 (18) 方式进行，由于该算法在搜索后期，第t代个体与上一代个体变化比较小时(尽管c1具有部分扰动的作用，但c1的取值为 (0,1)之间的随机数)，其群体智能行为的收效甚微，种群的多样性逐渐退缩。为了充分利用当代个体的信息，引入种群个体信息共享策略，以提高种群多样性，其具体策略如式 (19) 所示。

其中，NA 为种群数量。当i＞1 时，第i个个体与第i-1 个个体进行信息共享；当i=1 时，第i个个体与第NA 个个体信息共享。s的计算方式如式 (20)所示。

其中，t和Tmax分别为当前迭代次数和最大迭代次数。

2) 历史信息共享。被囊群算法在搜索过程中，每次迭代只保留全局最优个体的位置，而没有参考种群个体所携带的历史搜索信息，导致搜索精度不高。为提高搜索精度，充分参考搜索过程中个体携带的历史搜索信息，引入历史信息共享策略。种群在迭代过程中，保留所有个体的历史最优记录，在种群陷入局部最优时，减少向全局最优位置收敛，增加种群个体向种群其他个体历史最优位置探索的行为。

在执行历史信息共享时，当前个体向种群中其他个体最优位置探索过程中，利用式 (21) 高斯变异策略对目标位置进行扰动，增加搜索范围。

执行历史信息共享的个体位置根据式 (22) 更新。

其中，为个体更新后的位置，f() 表示第i个个体的个体最优适应度值，f() 表示第j个个体的个体最优适应度值。

3) 种群状态信息共享。种群迭代开始前，分析当前搜索状态，对种群搜索状态进行量化并共享。

其中，dg 代表种群当前搜索状态，fc 为计数器，fc 初始为0，如果上一次迭代过程中，全局最优适应度值未被更新，则fc 值自增1；如果上一次迭代过程中，全局最优适应度值被更新，则fc 值归0。a为动态策略选择因子，取a=2.5。图4 是当Tmax=500 时，dg 随fc 增加的变化轨迹。当fc 较小时，dg 趋近于1，当fc 逐渐增加时，dg 逐渐减小，并且减小的幅度越来越慢，最终趋向于0.5。dg 越大，表示当前搜索效率越高。

图4 dg 随着fc 增加的变化轨迹Figure 4 The change of dg with the increase of fc

当种群搜索效率高时，种群趋向于执行个体信息共享策略；搜索效率较差时，种群80%的个体执行历史信息共享策略，20%的个体采用式 (24) 执行自由行动，以进一步增强种群多样性。

其中，Lb 是种群边界下限，Ub 是种群边界上限。

3.3 改进被囊群算法求解云制造分包服务组合模型

云制造分包服务组合的评价模型为式 (13)，约束条件为式 (14)，属于离散约束组合优化问题。可以用本文的改进被囊群算法来求解。求解的基本思想是将式 (13) 作为改进被囊群算法的适应度函数。云制造分包平台按照分包方案设置的最小分包数量nl、最大分包数量nu，计算所有满足条件的分包数量的最优服务组合，根据评价结果向总包商推荐最优的分包服务组合。

3.3.1 编码方式

本文参考文献[4]采用实数编码方法，被囊群个体坐标维度与服务组合中的服务数量对应。每个被囊群个体表示一个解，即每一个被囊群个体表示一个分包服务组合方案。由于被囊群坐标是连续值，而对应的制造服务序号是离散值，为了增大服务被搜索到的范围，提高算法准确度，将被囊群个体坐标取四舍五入映射到一个服务序号。图5 是分包方案当分包数量为4 时，分包服务组合编码实例。

3.3.2 算法流程

基于改进被囊群算法求解云制造分包服务组合的流程如图6 所示，具体描述如下。

图6 改进被囊群算法流程图Figure 6 Flowchart of MTSA

步骤1初始化问题维度参数nl、nu、n。根据分包方案设置的分包数量，n初始值为最小分包数。

步骤2种群初始化。设置种群个体数量NA、最大迭代次数Tmax、当前迭代次数t、种群下边界Lb、种群上边界Ub、计数器fc 等参数。随机初始化种群个体。确定当前全局最优种群个体、全局最优适应度。

步骤3当t＜Tmax时，开始种群迭代。根据式(23) 计算参数dg，判断rand＜dg 时，执行步骤4，否则执行步骤5。

步骤4根据式 (19) 更新种群个体位置，结束后执行步骤6。

步骤5当rand ＜ 0.8 时，根据式 (22) 更新个体位置，执行历史信息共享策略，否则根据式 (24)更新个体位置，执行自由行动。

步骤6根据式 (14) 判断更新后的个体位置是否越界，若超越上、下界，则个体位置设置为上、下界的值。种群个体位置更新后，按照式 (13) 计算本次迭代的个体适应度值。

步骤7更新全局最优位置、更新个体最优位置、更新参数fc、t。

步骤8判断是否结束迭代。如果是，则执行下一步，否则执行步骤3。

步骤9判断n是否不大于nu，若是，则n自增1，执行步骤2，否则执行下一步。

步骤10输出全局种群最优位置及适应度，即最优服务组合及最优评价结果。

4 仿真实验

仿真实验在操作系统为64 位Windows11 的电脑上进行。程序采用Matlab R2016a 编写。

4.1 改进被囊群算法性能对比

为验证本文改进被囊群算法 (MTSA) 性能，适应度函数采用分包服务组合评价目标模型函数，选取被囊群算法 (TSA)[10]、文献[13]的信息共享的记忆被囊群算法 (memory TSA with information sharing, IS-MTSA) 以及其他5 个经典的群体智能算法：粒子群优化算法 (particle swarm optimization, PSO)[16]、蝴蝶优化算法 (butterfly optimization algorithm, BOA)[17]、差分进化算法 (differential evolution, DE)[18]、教与学优化算法 (teaching-learning-based optimization,TLBO)[4]、布谷鸟算法 (cuckoo search, CS)[19]作为对比算法。为了保证对比算法的公平性和合理性，所有算法的种群规模均设置NA = 30，各算法的参数均按照相应文献进行设置。本实验设置分包数量为10，即问题求解维度为10，模拟大规模零件制造场景，设采购方将制造任务i设置为分包任务，要求制造200 万个某零件。该任务的分包方案p 要求最长制造周期不超过45 d，最大制造费用不超过500 万，共有300 个制造企业提交方案p 的任务意向书。实验借鉴文献[4]，在一定取值区间内，随机生成服务属性值，表2 为属性取值范围。

表2 云制造分包服务组合属性取值范围Table 2 Attribute value ranges of cloud manufacturing subcontracting service composition

每个算法对分包服务组合评价模型函数独立运行30 次，每次迭代200 次。表3 是从实验结果中得到的最优值、平均值、最差值、执行时间 (执行一次的平均时间) 等4 个指标，从不同维度分析实验结果。

表3 各算法实验结果Table 3 Experimental results of different algorithms

通过表3 可以看出，MTSA 在实验函数上的最优值、平均值、最差值均为最优，表明该算法具有更好的收敛精度和稳定性。MTSA 由于在式 (21) 中执行高斯变异操作消耗时间较长，因此执行时间略长于TSA、ISMTSA、PSO，但差距不大。随着求解问题复杂性的提高，式 (21) 所消耗的时间占整体比重将越来越小，MTSA 与TSA 执行时间的差距将缩小。表4 是设置不同分包数量时TSA 和MTSA 执行时间，当分包数n=50 时，MTSA 执行时间小于TSA 执行时间。图7 是各算法计算云制造分包服务组合的收敛曲线，横轴代表算法迭代次数，纵轴代表迭代过程搜索到的最优适应度值的平均数。从图中可以看出，对比其他算法，本文改进的被囊群算法收敛速度明显较快，在迭代60 次之后搜索到的最优适应度值已优于其他对比算法，并且将优势一直保持到最后。因此，改进的被囊群算法在搜索精度和收敛速度方面与对比算法比较有明显优势，更适合求解云制造分包服务组合优化问题。

表4 不同分包数量时执行时间Table 4 Execution time for different subcontracting quantities 10-4 s

图7 各算法的收敛曲线Figure 7 Convergence curves of different algorithm

4.2 云制造分包服务组合评价模型验证

将本文的方案与文献[4]、文献[5]和文献[6]所提方案进行对比。所选对比方案针对云环境中资源配置问题分别提供了3 种不同方法，实验分别应用本文方案和对比方案解决资源配置问题。首先，比较本文方案在不同分包数量时根据式 (13) 求解的综合制造水平差异，搜索最优分包服务组合。然后，通过方案对比，验证本文方案在制造时间和制造成本方面的优势。

为方便实验观察，本文方案设置分包数量分别为1、3，5、7、9、11、13、15。文献[4]、文献[5]和文献[6]提供的方案分别设为对比方案1、对比方案2 和对比方案3，参数按照相应文献设置。实验设置种群规模NA=30，所有方案均独立运行10 次，每次迭代500 次。

表5 为本文方案不同分包数量的服务组合指标明细，展示了不同分包数量下搜索到的最优分包服务组合的制造时间、制造成本、持续生产能力和综合制造水平。通过表5 可知，当未分包 (分包数量为1) 时，制造时间为22.2 d，成本为122.2 万元，持续生产能力指标为93.36%，虽然持续生产能力较强，但制造时间和成本明显较高。随着分包数量的增加，完成制造任务的时间和成本逐渐减少。但由于过多的分包量导致生产的不确定性风险增加，相应的持续生产能力在不断减弱。从表5 可以看出，分包数量为3 时，制造时间为14.4 d，成本为58.56 万元，持续生产能力为73.52%，各项数据均表现较好，综合制造水平最优。

表5 分包服务组合指标明细Table 5 Details of subcontracting service composition indicators

表6 是各方案求解的制造时间和成本，其中本文方案数据来自分包数量为3 时的制造时间和成本。通过对比可知，本文方案求解的最优服务组合在制造时间和制造成本方面均优于对比方案。

表6 各方案的制造时间和制造成本Table 6 Manufacturing time and cost of each scheme

5 结束语

云制造服务调度是云制造平台的关键环节，合理的服务调度能提高制造效率、降低制造成本、控制整体风险。针对云制造环境中大规模制造任务的制造周期长、成本高的问题，提出基于改进被囊群算法的云制造分包服务组合优化方法。综合考虑服务的功能与非功能属性，采用基于综合制造水平的分包服务组合评价模型计算服务Qos。为了找到一种更有效地求解云制造分包服务组合模型的算法，提出一种改进被囊群算法，引入信息共享策略，指导种群跳出局部最优，提高了搜索精度。实验验证了改进被囊群算法的搜索性能优势和云制造分包服务组合对解决大规模制造任务周期长、成本高问题的有效性和可行性。本文在对分包服务组合优化时，没有考虑到任务计划出现偏差时，如何动态调整服务组合，下一步工作将集中于云制造分包服务组合监控及动态调整模型的构建。