谢程龙 石宇强

(西南科技大学制造科学与工程学院 四川绵阳 621010)

云制造[1]是一种面向服务的、高效低耗和基于知识的网络化、敏捷化制造模式[2]，能够有效整合服务资源，更快地响应市场需求，降低服务成本，提高服务效率。随着云制造任务的日益复杂，使得单一的云制造服务已经难以满足需求者的任务需求，因此云平台通过云制造服务资源组合来满足复杂的任务需求[3]。云制造服务资源组合优化是云制造中的关键技术之一，云制造任务分解为多个子任务，每个子任务匹配得到相应的服务资源集合，研究如何选择服务资源，形成合适的服务组合方案来执行任务具有重要意义。

国内外文献大多数以服务质量(Quality of Service，QoS)作为评价指标来进行云制造组合优化。Ding等[4]建立多层次制造服务组合评价模型，其中考虑的主要指标是时间、成本和信誉。李永湘等[5]将服务可靠性、可信性、组合复杂度、协同度、执行时间、执行费用相结合来构建QoS评价模型。Yuan等[6]结合时间、可组合性、质量、可用性、可靠性、成本等目标，提出服务组合的QoS指标体系，使用改进的模糊综合评估法确定QoS评估中每个指标的权重。陈友玲等[7]构建面向云制造的多供应商协同生产任务分配优化模型。Zhao等[8]为了更准确地从复杂的服务网络中找到个性化的制造服务组合，将组合优化与协同过滤相结合，通过使用具有服务质量约束的组合优化模型来选择最佳服务组合。Ren等[9]针对制造服务的社会协作特点，提取出5类社会关系来计算协同效应，然后建立一种基于最大化整体协同效应的服务组合优化模型。Wu等[10]提出一种从经济、环境和社会等方面评估云制造可持续性的综合方法，从而建立组合优化模型。因为云制造组合优化问题是NP难问题，许多学者使用遗传算法[11-12]、粒子群算法[13]、人工蜂群算法[14]等求解云制造服务组合优化问题。

上述研究在解决云制造组合优化问题时大多是关注任务需求，其中大多考虑的是成本、时间、质量等QoS指标，但是对于服务资源执行任务的历史执行情况及其时效性考虑较少，使得服务资源对任务的执行能力是否可信或者可靠不得而知，具有不确定性。当执行能力可信度低的服务资源执行子任务时可能会出现更多突发问题，例如设备故障使得交货期延长，成功执行子任务的概率将降低，最终可能会导致整个任务失败，不但影响需求方利益同时也对云平台利益及声誉造成影响。因此，有必要同时考虑服务资源的QoS指标以及历史执行情况来解决考虑执行能力的云制造服务组合优化问题。

1 问题描述

云平台将需求方任务按规则分解为若干子任务，ST={STi|i=1,2,…n}表示分解后的子任务集合，n表示子任务数，STi表示第i项子任务。Si={Sij|j=1,2,…mi}表示STi的候选服务资源集合，mi表示Si中的服务资源数，Sij表示Si中的第j个服务资源。

需求方关注的是任务需求[11]，即成本、时间、合格率等QoS指标，不同服务资源的QoS指标可能不同。云平台更加关注任务是否可以顺利完成，即云制造服务资源的执行能力是否可信。服务资源执行能力是否可信可以通过其历史执行情况来判断，而云制造服务资源的历史执行情况会随时间变化，具有不确定性。若在云制造服务资源组合优化决策过程中仅考虑成本、时间、合格率等QoS指标，忽略云制造服务资源的历史执行情况，对服务方任务执行能力考虑不足，可能导致任务执行失败。因此，应综合考虑需求方所关注的成本、时间、合格率等QoS指标和云平台所关注的服务资源历史执行情况信息，进行服务资源组合优化，使组合方案达到最优。

2 组合优化模型

云制造需求方主要关注任务需求，即完成任务所需的成本、时间、合格率均达到最优。云平台更多关注服务资源执行能力是否可信，而可靠性和可维护性能够客观反映服务资源在执行任务时的真实情况。可靠性是指服务资源成功执行任务次数与执行任务总次数之比[3]；可维护性是指服务资源执行任务中成功处理意外的次数与意外发生的次数之比[15]。当服务资源可靠性和可维护性越大时，执行任务的稳定性越好，执行能力越可信。因此，本文以服务成本、时间、合格率、可靠性、可维护性为决策目标建立组合优化数学模型，并且考虑服务资源历史执行情况信息的时效性，建立时间段权重衰减函数。

决策变量如下：

(1)

式中Xij为决策变量。

2.1 时间段权重

服务资源在不同时间段的历史执行情况可能不同，考虑到服务资源历史执行情况的时效性，建立时间段权重线性衰减函数为每个时间段赋予权重。越靠近当前时间点的时间段权重越大，越远则时间段权重越小。H表示总时间间隔段数，即能对执行情况进行评价的时间段数。权重衰减函数公式如下：

(2)

式中：h表示时间段，假设云制造服务资源在每个时间段内均有执行任务；φh表示时间段h的权重。在该衰减函数中，云平台可以根据自己需要对最大间隔数H和最远时间段权重φH进行设置，其中H≥1，0≤φH≤1。

2.2 优化目标

总服务成本(C)决策目标如下：

(3)

式中：C表示服务组合方案的总服务成本；Cij表示Sij对STi的服务成本。

总服务时间(T)决策目标如下：

(4)

式中：T表示服务组合方案的总服务时间；Tij表示Sij对STi的服务时间。

合格率(Q)决策目标如下[16]：

(5)

式中：Q表示服务组合方案的平均合格率；Qij表示Sij对STi的合格率。

可靠性(SR)目标是使服务组合方案的平均可靠性最大。首先利用时间段权重，确定各服务资源可靠性，然后基于标准差[17]对可靠性进行奖惩修正。

可靠性决策目标如下:

(6)

(7)

(8)

可维护性(SM)目标是使服务组合方案的平均可维护性最大。首先利用时间段权重，确定各服务资源可维护性，然后对可维护性进行奖惩修正。可维护性决策目标如下:

(9)

(10)

(11)

2.3 约束条件

组合优化模型约束条件如下：

(12)

式中：每个子任务由一个服务资源服务。

(13)

式中：Cmax表示可接受的最大总服务成本；Tmax表示可接受的最长总服务时间；Qmin表示可接受的最低合格率；SRmin表示可接受的最小可靠性；SMmin表示可接受的最小可维护性。

2.4 总目标

将各目标进行归一化[7]，总目标最小的服务资源组合方案则为最优组合。总目标公式如下：

minF=ω1·T*+ω2·C*+ω3·Q*+

ω4·SR*+ω5·SM*

(14)

(15)

式中：T*，C*，Q*，SR*，SM*分别表示归一化后的服务时间、成本、合格率、可靠性、可维护性目标；ωe表示各子目标的权重值，E=5。

3 JADE算法求解

JADE算法[19]是DE算法[20]的变体，其优势在于通过使用带有外部归档的变异策略(DE/current-to-pbest/1 with archive)以及通过自适应方式对变异概率μF和交叉概率μCR进行更新来优化算法性能。本文在JADE算法的基础上使用反向学习种群初始化并引入DE/rand/1变异策略。

3.1 种群初始化

首先产生初始种群，再产生反向种群[21]：

(16)

3.2 变异策略

针对个体变异概率Fi，标准JADE算法采用的是柯西分布生成，本文中Fi的生成方式调整为正态分布生成，具体公式如下：

Fi=randni(μF,0.1)

(17)

μF=(1-c)·μF+c·meanA(SF)

(18)

式中：Fi表示个体i的变异概率；μF为变异概率；Fi根据平均值为μF、标准差为0.1的正态分布产生；式(18)表示变异概率μF的更新方式，与交叉概率μCR更新方式相同；SF表示成功变异的个体对应的Fi组成的集合；meanA(SF)表示对SF集合中的参数取平均；c=0.1。

本文中将DE/rand/1策略和DE/current-to-pbest/1 with archive策略相结合来进行变异，具体公式如下：

(19)

3.3 算法流程

算法流程如图1所示。具体步骤如下：

Step 1:设置种群规模NP，个体维数Dim，个体取值范围Xmax，Xmin，当前迭代数g，最大迭代数Gmax，初始化变异概率μF，交叉概率μCR，初始化外部存档集合A=∅等参数；基于反向学习的种群初始化；

Step 2:判断是否满足g>Gmax，若满足，则输出最优解；否则转入Step 3；

Step 3:设置个体成功交叉所对应的交叉概率CRi组成的集合SCR=∅，成功变异所对应的变异概率Fi组成的集合SF=∅；

Step 4:为种群中个体i产生交叉概率CRi、变异概率Fi；

Step 5:为种群中个体选择变异策略来进行变异操作；

Step 6:对种群中个体进行交叉操作；

Step 7:对种群中个体进行选择操作和存档操作，更新A，SCR，SF；

Step 8:更新交叉概率μCR和变异概率μF，g=g+1,转到Step 2。

图1 算法流程图Fig.1 Algorithm flowchart

4 实验仿真

假设某任务由云平台分解为8项子任务，表示为{ST1,ST2,…ST8}，各子任务的候选服务资源均为8个，子任务按顺序执行，为各子任务选择服务资源，形成最优组合方案。假设各服务资源成本取值范围[1,6]万元、时间取值范围[3,12]天、合格率取值范围[90%，99%]、各时间段可靠性取值范围[0.80，1]、各时间段可维护性取值范围[0.70,1]。设置两组实验，在实验一中，只考虑时间、成本、合格率目标，权重均为1/3；在实验二中，考虑时间、成本、合格率、可靠性、可维护性目标，权重均为0.2。部分云制造服务资源的QoS指标信息和各时段历史执行情况信息分别如表1、表2所示。

表1 部分服务资源QoS指标信息Table 1 QoS indicator information of some service resources

表2 部分服务资源历史执行情况信息Table 2 Historical performance information of some service resources

模型参数设置：服务资源可靠性波动阈值λSR=0.05；修正后的可靠性范围0.8≤SRij≤1；服务资源可维护性波动阈值λSM=0.05；修正后的可维护性范围0.7≤SMij≤1。时间段最小权重φH=0.2，总间隔数H=5。约束设置：总成本C≤20万元；总时间T≤45 d；合格率Q≥95%；可靠性SR≥90%；可维护性SM≥82%。

算法参数设置：种群规模NP=50、最大迭代次数Gmax=100、运行50次；JADE算法与本文改进的JADE算法初始交叉概率μCR=0.3，初始变异概率μF=0.5，适应度值占优比例p=0.1；不同变异策略种群比例q=0.3；粒子群(PSO)算法速度更新参数c1=0.5，c2=0.5，速度最大值Vmax=5，最小值Vmin=-5。将本文改进JADE算法与PSO算法、JADE算法进行对比，运行50次后，两组实验平均解迭代过程如图2、图3所示，算法结果对比如表3、表4所示。

图3 实验二平均解迭代过程Fig.3 Experiment 2 average solution iteration

表3 实验一运行结果对比Table 3 Comparison of experiment 1 running results

表4 实验二运行结果对比Table 4 Comparison of experiment 2 running results

从图2、图3可以看出，采用反向学习的初始化种群，在迭代初期获得的解更优，证明反向学习的有效性。同样可以看出，本文改进的JADE算法相对于JADE算法收敛性更好。从表3、表4中可以看出，独立运行50次后，本文改进JADE算法每次运行均能寻得相同最优解，而PSO算法适应度平均值大于其他两种算法。在求得最优解的平均迭代数方面，本文改进的JADE算法在实验一、二中分别比JADE算法少7代和6代，因此本文改进的JADE算法的收敛性较好。

两组实验最优组合方案的子目标值如表5所示，实验一组合方案为[S13,S22,S36,S45,S54,S63,S78,S87]，实验二组合方案为[S15,S27,S36,S44,S51,S66,S72,S86]。对两组实验进行比较，当实验一组合方案按实验二中考虑的5目标并且各目标权重均为0.2的情况下进行计算时，可靠性为0.906 5，可维护性为0.823，适应度值为0.487 67，适应度值大于实验二最优解。可靠性和可维护性能够客观反映服务资源在执行任务时的真实情况，即可靠性和可维护性越大时，其执行任务的稳定性越好，执行能力越可信。实验二服务资源组合方案的可靠性和可维护性优于实验一，则实验二服务资源组合方案执行能力更可信，执行任务时稳定性更好。虽然实验一服务资源组合方案的服务成本、时间、合格率优于实验二，但是实验一服务资源组合方案未按承诺完成任务的风险更高，一旦未按承诺完成任务，使得任务失败将造成更大的损失。因此，为降低服务资源组合方案未按承诺完成任务的风险，选择执行能力更可信的服务资源组合方案是有必要的。

表5 最优服务组合子目标值Table 5 Optimal service group target value

在不考虑对服务资源可靠性和可维护性进行奖惩修正的情况下，实验二最优组合方案为[S15,S27,S36,S44,S53,S66,S72,S86]，与考虑修正情况下的最优组合方案主要区别在于子任务ST5对于服务资源的选择，服务资源S51,S53的可靠性和可维护性标准差如表6所示。从表6可以看出服务资源S51可靠性和可维护性标准差均低于服务资源S53，说明服务资源S51的可靠性和可维护性的波动相对于服务资源S53较小。通过对服务资源的可靠性和可维护性进行奖惩修正后，最终选择的服务资源组合方案为[S15,S27,S36,S44,S51,S66,S72,S86]。

表6 S51，S53的可靠性和可维护性标准差Table 6 Standard deviation for reliability and maintainability Of S51 and S53

5 结论

本文针对云制造服务资源组合优化中服务资源执行能力存在不确定性等问题，建立一种考虑需求方所关注的QoS指标和云平台所关注的服务资源执行能力的组合优化模型。结果表明考虑服务资源执行能力的组合优化方法所选择的组合方案在执行任务时的执行能力更可信，且改进的JADE算法在两组实验中收敛性相比原算法更好。在下一步的研究中，将考虑面向多任务以及多任务之间存在优先级关系的云制造服务组合优化，运用多目标优化算法进行最优组合方案的选择。