考虑稀缺服务与质量损失云制造服务组合问题

2022-01-06王红涛

计算机集成制造系统 2021年12期

胡杨，吴锋+，王红涛

(1.西安交通大学管理学院，陕西西安 710049；2.西安交通大学过程控制与效率工程教育部重点实验室，陕西西安 710049；3.中国重型机械研究院股份有限公司，陕西西安 710032)

0 引言

云制造(Cloud Manufacturing, CMfg)是航天二院李伯虎院士及北京航空航天大学张霖、陶飞教授团队提出的一种有前途的面向服务的制造范式[1]，以现收现付(pay as you go)模式提供可靠、按需供应和可扩展的制造服务或能力[2]。在云制造业务流程中，制造服务被制造服务提供商(Manufacturing Service Provider, MSP)封装并发布到云制造平台上[3]。客户提交的粗粒度的制造任务将被分解为多个细粒度的制造任务[4]，然后由云制造平台方进行服务组合过程[5-6]。云制造的服务组合主要执行如下内容：针对每个制造任务，选择对应的、合格的制造服务，并将选中的制造服务进行组合，形成一个复合的制造服务。复合制造服务的好坏主要由服务质量(Quality of Service，QoS)指标进行衡量，QoS中包含多个属性，如生产成本、执行时间、服务可靠性、服务可得性等。最优的服务组合结果通常拥有优秀的QoS属性值，如最佳质量、最低价格、最高可靠性等[7]。

本质上，云制造的服务组合可以看作是云制造调度过程的支撑技术，其目的是根据一定的组合规则，在制造任务(Manufacturing Task, MT)和制造服务(Manufacturing Service, MS)之间进行合理的配置[8]。因此，全面模拟更接近真实制造实践的操作条件对服务组合绩效至关重要。虽然到目前为止，学者们对云制造服务组合已经进行了大量研究，但现有方法还不够全面，无法涵盖真实生产情况下云制造中的各种操作条件[5]。

目前，一般研究中假定，每个制造任务的制造服务集中包含大量的、相互独立的可用制造服务，而且相应的制造服务提供商有无限的能力来执行制造任务[6-7，9]。然而，拥有关键制造服务(如专业人员、先进技术或机器)是稀缺的[10]。假设有数个制造任务同时与某个制造服务提供商提供的稀缺制造服务组合，这种情况下，如果服务提供商的任务处理能力有限(如同时只能执行一个制造任务)，则这些制造任务就需要排队等待，直到前一个制造任务执行完成。因此，若忽略制造服务的稀缺性，则完成所有云平台上制造任务所需的最终完工时间将被错误地估计。

同时，云制造的制造任务主要涉及生产有形产品和零部件等[11]，这需要各制造服务提供商在线下执行。对于线下的制造过程，不同的人、机器、材料、方法、测量和环境(5M1E)所造成的误差会导致差异[12]，生产出来的产品质量不可避免地受到这种变化的影响，从而导致质量的损失[13]。自然，云制造过程同样受到质量变化的影响，即云制造产品在云制造过程中也会遭受质量损失，特别是在针对复杂重型装备如大型挤压机、轨道交通载具、船舶等的制造项目中尤其如此。目前，少有云制造相关研究考虑到制造过程中的产品质量损失问题。

此外，在线下生产过程中，所有半成品或材料需要在制造服务提供商之间进行物流运输。对于云制造等先进制造模式，在执行制造任务时始终强调可持续性[9, 14]。云制造过程中涉及的制造和物流活动都对可持续性的3个方面，即经济(成本和价格)、环境(温室气体排放)和社会(客户满意度)产生影响。物流在经济和环境绩效方面都占有相当大的比重[15-17]。然而，尽管云制造可持续性与云制造物流有着深刻的关联，但大多数服务组合模型在揭示物流与可持续性之间的相互作用方面存在不足。

综上所述，在云制造服务组合的过程中，制造服务稀缺性、产品质量损失和可持续性是3个不可忽略的条件，它们之间存在潜在的相互关系，应纳入云制造服务组合模型。目前的研究并未重视这些条件，从而产生了不完整、不全面的服务组合模型。本文针对云制造服务组合问题，建立了一个双目标非线性整数规划模型，该模型考虑了制造服务提供商任务处理能力、产品质量损失和可持续性。考虑到该问题的复杂性，本文提出一套解决该服务组合问题的新方法。给定多个复杂制造项目，该模型改进了总完工时间的估计方法。此外，模型中考虑物流成本和物流排放，以及云制造过程中的产品质量损失。然后，在基于帕累托包络的选择算法(Pareto Envelope based Selection Algorithm-2,PESA2)的基础上，提出了一种基于距离的自适应PESA2算法(Distance-based Adaptive PESA2,DA-PESA2)，该算法能最大限度地提高QoS和可持续性的评价结果。最后，通过数值实验验证了提出的服务组合模型和DA-PESA2算法的有效性。

1 相关研究进展

当前，已有大量关于云制造服务组合的文献。本章简要回顾产品质量损失、云制造可持续性和云制造多目标服务组合算法方面的相关工作。

在云制造中，质量指对云制造过程中获得的产品总质量的评估，是QoS属性之一[18-19]。经典的质量损失函数及其适应生产实际的改进版本被广泛应用于生产场景中。这些质量损失的表现形式与时间密切相关。例如，文献[13]将质量损失定义为制造缺陷造成的额外成本，其中与不可检测缺陷相关的保修成本中建模的小型缺陷被假设为一个时间依赖变量。文献[20]假设生产出的合格产品有质量风险，而该质量风险会产生潜在损失成本。同时，受设备老化影响，生产出的产品的合格率可以表示为一个关于时间连续的递减函数。文献[21]建立了基于风险时间敏感性的产品质量损失模型，以确定最佳维修计划，其中每个操作处理的产品质量随退化时间的变化而变化。

同时，云制造的成功很大程度上依赖于物流。物流可持续绩效通常从经济、环境和社会3个方面进行评价[22]。然而，多数关于云制造物流的研究都主要集中在经济(如物流成本)和环境(如物流温室气体排放)两方面[23-24]。文献[15]最初通过添加云制造物流因子来扩展服务组合研究范围，以更好地进行服务组合实践。此外，由于道路状况直接影响云制造物流决策，需要更多地关注实时路况，如物流路线、速度限制、地理位置等。文献[9]提出了云制造中唯一同时优化服务质量和可持续性绩效3个方面的实例，但模型中没有考虑物流因素。

云制造中的服务组合被证明是一个NP-hard[7]多目标组合优化问题[25]。文献[26]提出基于X列表和应用服务提供商(Application Service Provider，ASP)的网络化制造模式，但与云制造相比，这些网络化模式缺乏有效的商业化模式；文献[27]建立了目标为时间最短、成本最低及时间—成本综合最优的网络制造资源优化配置模型，并通过改进的蚁群算法对资源服务进行组合；文献[28]在云制造环境下建立了以时间最短、成本最低、可靠性最高为目标的异地设备资源优选模型，并通过改进后的遗传算法、层次分析法等组合方法进行求解。双目标或多目标问题通常涉及到相互冲突的目标，如风险与不确定度[29]、服务质量与生态考量[9]等。目前的研究主要是通过设计搜索策略或保持种群多样性来修改经典的元启发式算法[29]。

综上所述，仍然可以发现一些研究的局限性：

(1)首先，当前大多数有关云制造服务组合的模型都假设与每个制造服务相匹配的制造服务是足量且丰富的，同时假设制造服务提供商的任务处理能力也是无限的。这些假设在部分高端制造服务稀缺的情况下显然不能成立。

(2)现有文献忽视了对云制造生产过程中会发生的产品质量损失，而在生产系统中，产品发生质量的损失对最终的产品交付和产品性能都会产生重要影响，因此在云制造服务组合模型中建模产品质量损失至关重要。

(3)现有探讨云制造可持续性并将其融入服务组合模型的工作并不多。作为一种智能时代的网络化协同制造新模式，云制造势必要追求其在经济、环境与社会层面要达成的目标。

(4)在进行数值试验或模型构建阶段，多数研究倾向于关注可分为若干子任务的单个制造任务，而不是多个具有复杂结构的制造项目，这使得云制造服务组合的实验部分较为理想化，不能贴近实际的制造环境。

2 问题描述

客户向云制造平台提交制造服务需求，然后云制造平台运营商将服务请求转换为一组制造项目。制造项目被分解为多个制造任务MTi(i∈{1,2,…,NT}),NT是所有制造任务的总量。对于每个制造任务, 云制造平台方搜索提供符合其功能要求的合格制造服务，形成制造服务集合，以满足这些制造任务。服务集合中的每个制造服务是由MSPj(j∈{1,2,…,NS})提供的制造服务，其中NS是所有制造服务提供商的数量。其目标是通过为每个制造任务选择制造服务提供商，并确定制造任务的执行顺序来最大化服务组合中的服务质量和可持续性评价。

在建立云制造服务组合模型前，首先给出下列假设：

(1)考虑到制造服务提供商的任务处理能力有限，假设每个制造服务提供商同时至多执行一项制造任务；

(2)每个制造服务提供商在云制造平台上发布多项制造服务，即每个制造服务提供商可以执行多种制造任务；

(3)每个制造项目中的每项制造任务必须被执行；

(4)每项制造任务必须在同制造项目中的其他前序制造任务执行完成后，以及在同制造服务提供商处排在前列的制造任务执行完成后方可执行。

表1列出了相关集合、参数和变量的表示方式和解释。在云制造实践中，制造任务通常有顺序、并行、选择及循环4种执行结构。本文引入执行矩阵Ep描述制造任务间的执行关系，其具体定义如表1所示。通常，服务组合中各组合QoS参数的计算是将具有不同结构的服务转换成顺序关系进行计算。在下文中，对于属性So(式(3)),Q(式(8))以及R(式(9)), 按照表2中传统的计算方式进行服务

表1 集合、参数和决策变量

表2 不同结构下制造服务的复合属性值计算方式

组合属性值的计算。然而，对于属性M(即最大完工时间(Makespan)，式(4)),Ec(经济绩效评价，式(1))与En(环境绩效评价，式(2))，并不照此方式计算。

2.1 可持续性的数学描述

为帮助云制造系统实现长期繁荣，应将可持续性(Sus)确定为优化目标之一。具体来说，Sus涉及经济(Ec)、环境(En)和社会(So)方面。经济绩效的评价(Ec)包含了云制造过程中的生产成本和物流成本:

(1)

环境绩效(En)测量云制造过程中的生产排放与物流排放:

(2)

云制造的社会方面在本文中主要从客户满意角度出发。因此，社会绩效(So)以用户对某制造服务的评价来表示:

(3)

2.2 服务质量的数学描述

本文选取最大完工时间(M)、质量(Q)和可靠性(R)几项云制造中常用的QoS属性来表示服务质量。最大完工时间(M)表示给定的所有制造项目完成所需要的最小时间:

(4)

其中

FTij=max(PSTij,ATij)+xijtijσi。

(5)

式(5)中第一项为MTi的实际启动时间，第二项为MTi的总制造时间。对于第二项，假设在tij中包含了设置时间。对于第一项，假设制造服务总是可用的，PSTij可以表示为:

(6)

ATij定义如下:

(7)

在云制造中，质量(Q)是云制造服务组合中常用的QoS属性之一，平均产品合格率[18]可以用来代表质量。云制造任务的执行结果是工业产品，而产品质量可以被解释为符合设计标准的程度(即产品是否精确地按照设计者的意图制造)。本文中，Q定义为所有云制造产品符合设计水平的程度，是一个给定的QoS属性值。基于云制造实践和质量损失的基本概念，假设在云制造中获得的产品质量损失具有时间随制造时间变化[13]，类似于呈指数趋势老化、衰退的过程[30]：

(8)

可靠性(R)衡量成功完成所有给定制造任务的能力：

(9)

2.3 问题的形式化描述

本服务组合问题被表述为一个双目标问题。式(10)和式(11)中，云制造服务组合过程的服务质量和可持续性性能都应取得最大值。如前所述，服务质量是通过M、Q和R的加权和来评估的。同样，可持续性绩效的计算方法是Ec、En与So的加权和。整个问题可以形式化为:

(10)

(11)

(12)

FTi′j≤PSTij,∀i∈T,∀i′∈prii,∀j∈S；

(13)

(14)

(15)

(16)

3 DA-PESA2算法

本章详细阐述提出的双目标非线性整数规划算法DA-PESA2。DA-PESA2基于著名的多目标进化算法PESA2[31]，并结合基于染色体距离的自适应机制。像大多数多目标进化算法一样，经典的PESA2基于上一代档案库中的解，进行多种操作生成新一代非主导解。PESA2具有基于区域的选择机制。目标空间被划分为超空间网格来测量每个解决方案的密度。如果档案库过满，在最拥挤的超空间网格中的冗余解决方案将被清除。此外，进行遗传操作的个体是随机从档案中选择的。

本文采用整数编码方法。染色体的长度等于任务的数量。染色体中第i个基因的取值为j，表示MSPj提供的制造服务执行MTi。注意，本文设定并非所有制造服务提供商都能够执行某项制造任务。DA-PESA2混合了基于距离的自适应交叉和变异算子。每个个体的基因型实际上代表了其在高维解空间中的位置。该机制主要计算种群中所有个体的平均欧式距离，并以此自适应地调整交叉和变异概率。较大的平均距离指标表明较好的种群多样性。在早期迭代阶段，距离度量为算法中的交叉概率增加了搜索效率的压力。当Pareto前沿基本稳定时，距离度量可以降低交叉概率，以保持较高的解质量，并增加变异概率以基于当前种群挖掘更好的解。

已知解空间共有|T|维，T为制造任务的数量。假设种群大小为npop，gk,i指种群中第k个个体的第i个基因，则针对种群中所有个体的第i个基因在解空间中可以求得一个均值，即

(17)

基于此，在|T|维解空间中，可以求得整个种群的几何中心，从而可以求得种群中第k个个体与几何中心的距离，即

(18)

同时，种群中所有个体的第i个基因在解空间中可以求得基因级别的标准差：

(19)

基于式(18)和式(19)，整个种群的空间距离量度D被定义为所有基因变异系数的平均值，被用作调整变异和交叉的概率：

(20)

DA-PESA2动态地将种群划分为两个次种群，分别用于交叉(popC)和突变(popM)。根据式(21)中的距离度量，具有较大距离度量的种群会增加交叉概率，以分配更多个体进行勘探，而密集的种群会驱使更多的个体来探索未搜索的空间。交叉概率

(21)

在DA-PESA2算法中，变异概率Pm和距离度量D间的关系可被定义如下：

(22)

其中α为调节系数，防止Pm过高损害解的质量。若种群多样性足够大，Pm就会下降。

DA-PESA2算法简要框架如图1所示。

4 数值实验

本文通过设计数值实验以验证算法的有效性。所有实验都是在Intel(R) Core(TM) i5-4258U CPU @ 2.40 GHz, 4.0 G RAM, Windows 8.1操作系统的PC上用MATLAB 2017b软件实现的。

4.1 问题参数设置与算例生成

对于本章涉及的所有实验和算法，种群大小和档案馆大小(如果有)均为100。每次运行迭代次数为100，平均每次实验运行20次。假设MSP数量的上限为10。如表3所示，10个MSP位于5个不同的工业区。因此MSP1和MSP2，MSP3和MSP4，MSP5和MSP6，MSP7到MSP9共享同一位置，而MSP10单独处于一个位置。

表3 不同MSP之间的距离(Rjj′) km

考虑到模型约束和生产实践，表4确定了服务组合服务质量和可持续性计算的参数取值范围。

表4 问题的参数设置

实验前需要对所有制造服务的部分服务质量和可持续性属性值进行归一化：

(23)

如图2所示，在本文算例中，考虑了4种不同类型的制造项目，即Type-I(包含5个制造任务)、Type-II(包含5个制造任务)、Type-III(包含5个制造任务)以及Type-IV型制造项目(包含10个制造任务)。显然，这4种制造项目类型涵盖了所有任务执行结构。顺序结构普遍存在于4种制造项目中；Type-I和Type-IV制造项目涉及并行结构；Type-III和Type-IV制造项目中包含循环结构，而选择结构在Type-II和Type-IV制造项目中存在。

基于4种制造项目类型和10个制造服务提供商，本数值实验共考虑了8个案例，如表5所示。在8个案例中，制造任务数量共有4个级别，制造服务提供商数量有2个级别。每个制造任务数量级别中，制造任务数量总计为30、40、50和60。制造服务提供商数量的级别分别为5个MSP和10个MSP。5个MSP分别为MSP1～MSP5，10个制造服务提供商为制造服务提供商MSP1～MSP10。

表5 8个案例中制造项目的种类和执行顺序

4.2 评价指标

为了进一步比较不同算法提供的Pareto前沿的质量，本文使用3个指标来衡量Pareto解决方案的收敛性和多样性:

(1) 反向世代距离(IGD)，

(24)

式中P和P′分别为全局最优Pareto解集和本算法得到的Pareto解集。|P|为全局最优Pareto解集的大小，dist(x,P′)为全局最优Pareto前沿的第i个点与P′中最接近解之间的欧氏距离。IGD值越小，表示得到的解越接近全局最优Pareto前沿。

(2) 二集覆盖率(SC)，

(25)

式中：A和B是由两个不同算法得到的两组Pareto解集；SC(A,B)指B集合中被A集合中解主导的解占B集合总数的比例，如果SC(A,B)较高而SC(B,A)较低，A集合的算法越好，反之B集合的算法越好。

(3)Spread[32]，

(26)

4.3 实验1：验证DA-PESA2中提出的改进

表6给出了不同情况下，建议的DA-PESA2和经典PESA2在IGD、SC和Spread指标方面的比较。在标有“IGD”的栏中，给出了IGD的平均值和标准偏差(std)值，std值用括号表示。更好的结果用粗体突出显示。

表6 DA-PESA2与经典PESA2算法的改进

总体而言，DA-PESA2的性能优于PESA2。从DA-PESA2得到的IGD和std值在所有情况下都优于PESA2，只是在30-10案例的情况下，DA-PESA得到的std值略高。从IGD指标的角度来看，随着制造任务数的增加，PESA2得到的Pareto前沿逐渐远离真实的Pareto前沿。相比之下，DA-PESA2能够发现适应度高、变化小的解决方案。DA-PESA2在SC指标上始终优于PESA2，说明每次运行DA-PESA2所得到的Pareto前沿都能主导PESA2所得到的大部分解。最后，除60-10案例外，DA-PESA2方案的Spread值均低于PESA2方案。说明DA-PESA2解分布在Pareto前沿，种群多样性较好，预计在所有情况下DA-PESA2都会表现良好。

4.4 实验2：与经典算法的性能比较

将提出的算法与典型算法进行比较，如NSGA-II[32]、MOPSO[33]、SPEA2[34]和PESA2。

如图3和图4所示，在这4种情况下，MOPSO、NSGA-II、PESA2和SPEA2的IGD箱线图均高于及宽于DA-PESA2。图3和图4中，在横轴上从1到5分别表示不同算法：1-MOPSO, 2-NSGA-II, 3-PESA2, 4-SPEA2, 5-DA-PESA2。结果证明了DA-PESA2在所有情况下良好的收敛能力。与DA-PESA2相比，可以观察到随着每个算例规模大小的增加，MOPSO、NSGA-II、PESA2和SPEA2会降解。而DA-PESA2得到的解始终保持与真实Pareto前沿的距离，且变化不大。结果表明，DA-PESA2在不同情况下都具有较好的收敛性。总体而言，PESA2的收敛质量仅次于DA-PESA2，但仍优于NSGA-II和MOPSO。NSGA-II算法一般得到最不稳定以及分布面最窄的解。同时，通过MOPSO得到的解的方差最大。

图5展示了5种算法在所有情况下的平均Spread值。DA-PESA2的平均Spread值最好，其次是SPEA2、PESA2、MOPSO和NSGA-II。NSGA-II的性能最差。随着制造服务提供商的增加，MOPSO得到的平均Spread值变大。总体结果表明DA-PESA2解均匀分布在Pareto前沿，但在30-5、40-5和50-10案例中，DA-PESA2解略弱。与PESA2解决方案相比，DA-PESA2中提出的自适应机制在除60-10案例外的大多数情况下都可以灵活地保持解决方案之间的空间。

4.5 讨论

基于以上实验和结果，本文提出的DA-PESA2在不同的测试用例和指标下，均优于MOPSO、NSGA-II、SPEA2和PESA2等经典算法，从而证明了基于距离的自适应机制的有效性。NSGA-II在所有算例的所有指标中表现最差，其次是MOPSO。DA-PESA2得到的最优解更接近真实的Pareto前沿，且具有良好的间距、收敛性、种群多样性和稳定性。综上所述，如果将复杂制造项目序列、制造服务提供商任务处理能力、产品质量损失和可持续性等实际因素考虑在内，本文提出的DA-PESA2算法能获得更好的云制造服务组合问题的解决方案。