基于SOM的多粒度云制造资源组合推荐

Multi-Granularity Cloud Manufacturing Resource Combination Recommendation Based on SOM

摘要

在云制造过程中，细粒度的资源会使设计任务的匹配变得困难，难以满足云制造请求方对于制造任务的要求。目前实现方法中，多粒度资源组合推荐主要着重于分析资源性质，并从架构设计的角度解决多粒度资源组合的问题，而未从算法角度提供解决方案，泛化性能较差。针对这样的问题，提出基于自组织映射（self-organizing map，SOM）聚类分析的多粒度云制造资源组合推荐方式。该方法首先通过对请求方制造资源调度日志进行聚类分析，将制造资源按照QoS指标分为不同的类型；然后采用滑动窗口分析统计各种类型的资源调度方式，计算不同资源调度方式在整个资源调度过程中所占的比例，进而得出请求方在制造过程中常用的调度组合，以此作为向请求方推荐的资源组合；最后通过模拟实验的方式验证了本文方法时间消耗少于架构的固定组合。

Abstract

In the process of cloud manufacturing, fine-grained resources will make it difficult to match design tasks and meet the requirements of cloud manufacturing requestors for manufacturing tasks. In the current implementation methods, multi-granularity resource combination recommendation mainly focuses on analyzing the attribute of resources and solving the problem of multi-granularity resource combination from the perspective of architecture design, but does not provide a solution from the perspective of algorithm, so the generalization performance is poor. To solve this problem, this paper proposes a multi-granularity cloud manufacturing resource combination recommendation method based on self-organizing mapping (SOM) cluster analysis. Firstly, through cluster analysis of the requester’s manufacturing resource scheduling log, the manufacturing resources are divided into different types according to the QoS index. Then the sliding window is used to analyze and count various types of resource scheduling methods, calculate the proportion of different resource scheduling methods in the whole resource scheduling process, and then obtain the scheduling combination commonly used by the requester in the manufacturing process, which is used as the resource combination recommended to the requester. Finally, simulation experiments show that the time consumption of the method is reduced compared with the fixed combination of the architecture.

Graphical abstract

关键词

云制造 / SOM聚类 / 资源组合推荐 / 多粒度资源

Key words

cloud manufacturing / self-organizing map clustering / resource combination recommendation / multi-granularity resources

0　 引 言

制造资源是企业完成产品整个生命周期所有生产活动的物理元素的总称，它包含产品在设计、运输、制造、安装、维护等相关活动过程中涉及的所有软硬件元素^［1］。而云制造是一种利用网络和服务平台，按用户需求组织网上制造资源，为用户按需提供各类制造服务的新型制造模式^［2］。通过这种模式能够更好地集中利用制造资源，有效地解决资源分布广泛，产品产业链过于繁杂等问题^［3］。制造资源的虚拟化与调度是云制造的关键技术，资源虚拟化是将制造资源抽象成为虚拟服务^［4］，调度技术则是将大任务拆分成为小任务与相应服务匹配^［5~7］，一个任务可能有多个服务与之对应，请求方需要在这些服务之间选择。

但是在实际用户推荐的过程中，任务很难匹配到相应的细粒度资源。由于资源粒度太小，这些制造资源虚拟化的服务难以与任务相匹配，无法满足请求方对于任务的要求。所以要挑选出最符合请求方任务要求的粗粒度服务，就需要多粒度资源组合技术的支撑。因此，有学者提出了基于不同方式的资源组合。如李海波^［8］通过从实例和活动两个方面来计算资源的使用频率进而得出资源的组合方式。Ding等^［9］提出了一种将资源划分成三个不同的层级，围绕其中的关键资源并由用户自行选择辅助资源的组合方式。汤华茂等^［1］采用语义分析描述的方法对制造资源之间的关系进行分析，之后将制造资源进行抽象得出了其粒度模型。曹啸博等^［10］通过对资源的设计能力进行抽象和关联性分析，将知识类设计资源进行聚合。Liu等^［11］提出了通过QoS对相似的用户进行聚类分析和建立信任感知的方法为用户进行推荐。唐春华等^［12］提出了基于QoS评价的云制造组合优化算法，在考虑请求方和提供方双方约束的前提下对资源进行推荐。

现有的资源组合架构类设计都着力于寻找单个资源的性质特点，通过资源间性质特点的相关性进行多粒度资源组合，其好处在于不需针对制造实例进行分析，消耗时间较少。其缺点在于部分关系由调度方人为定义，导致模型泛化能力较差，资源结合过于死板，难以灵活应用于不同场景的制造实践中。SOM（self-organizing map）是一种自组织的神经网络算法^［13］，一般用于无监督学习。SOM聚类算法收敛能力好，资源通过自主学习划分种类，能较为灵活地运用于各种场景。通过聚类划分将复杂的制造资源数据降维，能够更加容易得出资源种类间的相关关系，减少时间开销。李海波^［8］认为资源的组合是随着业务开展不断变化的，因此制造资源调度日志可以在一定程度上反映用户对于资源调度组合的喜好程度，但是他所考虑的组合方式过于直接，将整个制造过程抽象成一个服务，难以应用于用户推荐，且没有考虑到资源组合结果也应该是多粒度的，应根据用户的需要进行不同粒度的组合。因此，本文基于SOM提出滑动窗口的资源调度组合计算方式，通过调节窗口的大小可以计算出不同粒度的资源组合，便于用户选择。

1　 问题描述

多粒度资源组合推荐的目的是将关联度高的细粒度资源组合成为粗粒度资源，使其将更有可能被请求方调用的资源序列抽象出的服务推荐给请求方。多粒度资源组合的关键就在于发现资源之间的相关性，从用户过往的调度实例中寻找用户最常用的调度模式。

彭功状等^［14］将制造资源组合的方式分为两种：第一种是同构组合，另一种是异构组合。同构组合是将功能相同的资源聚合，异构组合是关系紧密但功能不同的资源进行组合。采用异构组合处理顺序流程可以将执行不同功能但是在制造流程中紧密结合的资源组合到一起，成为更高粒度的资源。

本文采用资源调度日志表示的是已发生的用户调度实例，体现了实际用户调度中资源调度的顺序，是对工作流程图的实例化。本文将其抽象成为反映资源先后调用顺序的资源序列。如图1所示的电气设备工艺流程图（图中Rn表示调用的资源，n表示资源类别），从中可以抽象为3条不同的工作序列，即\{R\mathrm{1},R\mathrm{2},R\mathrm{3},R\mathrm{7},R\mathrm{8}\}、\{R\mathrm{1},R\mathrm{4},R\mathrm{5},R\mathrm{7},R\mathrm{8}\}、\{R\mathrm{1},R\mathrm{6},R\mathrm{7},R\mathrm{8}\}。这3条路径在实际过程中执行的次数也是不一样的，资源调度日志就是由这些实际调用的工作序列按照时序逻辑拼接而成，所以用户的资源调度日志可以在一定程度上反映其经常采用的工作路径，进而从工作路径中分析出可以进行资源组合的部分。不难看出，对于R\mathrm{7},R\mathrm{8}这一对资源在3条制造路径中都是一起出现的，所以理论上他们的相关性应该较高，它们应是资源组合所关注的重点。

2　 基于SOM算法的资源分类方法

在进行多粒度资源组合之前，首先要做的是对资源进行降维处理。云服务通过虚拟化将物理资源抽象成虚拟资源之后得到的虚拟资源往往维数过高，这样高维的数据对于分析在资源调用过程中资源相互的关系并无益处。而通过聚类的方式将资源分成不同的类，既降低了数据的维度，又能够体现出不同资源之间的关系。进行降维处理之后判断两资源是否能组合时只需判断两资源所在类是否可以组合即可。这样降低了时间成本，更容易运用到实际用户调度流程分析中。

从另一方面来说，在实际云制造用户制造服务调用过程中，请求方服务所需资源可能表示的不是一种资源而是一类资源，因为在云制造中可能存在多家供应商均能提供该资源，但是根据制造商的不同，其资源表现在数据上有可能不同，如不同供应商提供的资源吞吐量和可靠性不同，这也是需要采用聚类算法的一个原因，可以将相同类型的资源更好地抽象表示。

2.1　SOM算法原理

SOM算法采用学习率控制聚类节点中心在每次迭代中移动的速率。开始迭代的时候，SOM算法的学习率较大，保证相应节点快速地移动到聚类中心位置附近，以免陷入局部最优解。之后，学习率逐渐减小，防止在最佳位置周围出现振荡的现象，更容易逼近最优解。且SOM算法收敛速度较快，使找出的解可以满足交互式的推荐需求。

SOM输入层有m个节点，这m个节点表示SOM聚类算法的聚类簇，每个节点都有对应的不同向量用于表示节点簇的位置。对于每一个输入数据，所有节点都会判断输入数据与自身的距离，选择距离最近的节点并通过输入数据更新该节点的位置，使其离输入数据更加接近。通过不断迭代的方式使得节点中心不断学习，不断逼近理论上的聚类簇中心。

本文用 X =［x₁，x₂，…，x_n ］表示维度为n的制造资源数据，用 W_j =［w_j1，w_j2，…，w_jn ］表示第j个节点的n维向量。

2.2　SOM算法流程

SOM算法流程如图2所示。

SOM算法步骤如下，

步骤1 从数据集中读入数据 X。

步骤2 分别计算 X 与节点之间的距离dis（ X， W_j ），本文采用的是欧氏距离，计算如下

\mathrm{d}\mathrm{i}\mathrm{s}(\mathit{X},{\mathit{W}}_j)=\sum _i(w_{ji}-x_i{)}^{\mathrm{2}}（1）

步骤3 通过dis（ X， W_j ）寻找到距离 X 最近的节点k。

步骤4 通过（2）式更新节点向量

\left\{\begin{array}{l}{\mathit{W}}_k^{t+\mathrm{1}}={\mathit{W}}_k^t+\alpha (\mathit{X}-{\mathit{W}}_k^t)\\ {\mathit{W}}_j^{t+\mathrm{1}}={\mathit{W}}_j^t\end{array}\right.\begin{array}{c}\\ (j\ne k)\end{array}（2）

其中\alpha是学习率。SOM采用的是赢家通吃的思想，只会更新与 X 最近的节点，即节点k，其他节点不做更新操作。新的节点位置会在原先的位置上向输入数据偏移。

步骤5 判断节点是否发生变化，如变化跳转到步骤1，如未变化则认定算法收敛并退出。

3　 制造资源调度日志分析

在进行了资源分类得到资源数据到资源种类的映射之后，可以将制造资源调度日志中的资源调用顺序转化为资源种类调用顺序，用资源调度日志分析资源种类之间的关系。通过资源种类调度顺序可以分析出用户调用过程中常见的资源调度模式，即不同种类资源的调度顺序。利用滑动窗口的方式计算不同调度模式在调度日志中所占比例，通过模式出现的频率计算其在用户调用过程中复用的程度，频率越高复用程度越高，从而对这些资源进行组合。而调节滑动窗口的大小可以得出资源组合粒度的大小，适应不同情形下的资源调度。

3.1　计算原理

假设滑动窗口的长度为L，资源序列R=\{r_{\mathrm{1}},r_{\mathrm{2}},\dots ,r_n\}，其中r_i 为资源序列中第i位的资源。设滑动窗口的资源组合\mathrm{R}\mathrm{S}=\{r_i,r_{i+\mathrm{1}},\dots ,r_{i+L-\mathrm{1}}\}，则计算RS在整个资源序列R中出现的频率，如果该频率超过设定的阈值则认为RS中不同种类的资源可以进行组合，此处频率体现了用户对于该制造调度方式的喜爱程度，频率越高表明该调度模式被用户使用次数越多，在之后的调度过程中就应该推荐这类的调度序列。

3.2　组合频率计算

步骤1 判断当前窗口的RS是否符合组合条件，符合则记录；

步骤2 当前窗口是否为最后，若是，则L+=\mathrm{1}跳转步骤4；若不是，则执行步骤3；

步骤3 窗口向右移动一个资源，跳转步骤1；

步骤4 若L>m，则返回所有记录；否则跳转步骤1。

在计算当前窗口的RS是否符合条件的时候，如果RS的频率超过了阈值F_max，那么RS的所有子序列必然超过F_max。同理可得如果RS的一个子序列的频率没有超过F_max，那么RS必然不可能超过F_max。因此，可以将所有没有超过阈值的资源组合记录记为false_set（），在之后进行判断时，如果RS的某个子串在false_set（）中，就可以直接判断RS不可以进行组合。

图3为组合频率计算的流程图。

4　 实验分析

本文以图4所示电气装备设备柜加工流程图为例作为真实制造过程的模拟。图4中总计有3条可能的调度路径A=\{R\mathrm{1},R\mathrm{2},R\mathrm{3},R\mathrm{5},R\mathrm{6}\}，B=\{R\mathrm{1},R\mathrm{4},R\mathrm{5},R\mathrm{6}\}，C=\{R\mathrm{1},R\mathrm{4},R\mathrm{6}\}，通过添加不同的概率P_A 、P_B 、P_C 来模拟这3条路径在实际制造过程中出现的概率，用以分析不同实际制造情况对于本文算法所得出的资源组合结果的影响，并验证本文算法是否能针对不同的实际制造情形给出适合特定情形的资源组合方式。

服务质量（quality of service， QoS）常用于评价云制造的服务性能，本文采用的制造资源的QoS指标包括6个维度：响应时间、可用性、吞吐量、成功率、可靠性、合规性，其中部分数据如表1所示。总计制造资源数M=\mathrm{50}，按图4所示的资源种类进行分类形成6个资源集合，分别对应图4流程图中的\{R\mathrm{1},R\mathrm{2},R\mathrm{3},R\mathrm{4},R\mathrm{5},R\mathrm{6}\}。在调度某类资源时从对应资源集合中等概率地抽取，用以验证算法在涉及较多资源数据情况下的能力。

实验的运行环境为python 3.6。SOM算法迭代次数为300次，学习率\alpha=2，学习率的递减速率为0.95，聚类中心节点数m=\mathrm{6}，选择资源组合的频率阈值F_max为10%，制造资源路径总量为200。

为了展现本文所示算法可以根据不同的资源调度序列生成更适合该调度序列的资源组合模型，用不同的调度路径出现的概率模拟不同的资源调度序列，结果如表2所示。

为了展现本文资源调度模式比架构设计的组合方式效果有所提升，采用下式

\left\{\begin{array}{l}{T}_{\mathrm{a}\mathrm{l}\mathrm{l}}=T_{\mathrm{a}\mathrm{l}\mathrm{g}}+\beta T_{\mathrm{c}\mathrm{o}\mathrm{m}}+T_{\mathrm{u}\mathrm{c}\mathrm{o}\mathrm{m}}\\ T_{\mathrm{c}\mathrm{o}\mathrm{m}}=\sum T_{i,\mathrm{u}\mathrm{c}\mathrm{o}\mathrm{m}},i\in U\end{array}\right.（3）

计算不同路径总量下使用各种不同方式的响应时间，结果见图5。（3）式中，\beta表示采用了资源组合方法能够节省时间的比，\beta=0.8；T_all（s）表示处理该资源序列用的总时间，T_alg（s）表示SOM算法占用的时间，T_{\mathrm{a}\mathrm{l}\mathrm{g}}=\mathrm{10}\mathrm{s}；T_com（s）表示资源组合U占用的总时间，T_ucom（s）表示未组合资源占用的时间。P_A=P_C=0.25，P_B=\mathrm{0.5}。图5中SOM表示本文算法，ONLY_45表示仅组合\{R\mathrm{5},R\mathrm{6}\}的算法，ONLY_35表示仅组合\{R\mathrm{1},R\mathrm{5},R\mathrm{6}\}的算法，NONE表示不进行资源组合的算法。从图5可看出SOM算法在时间上优于两种基于架构的固定组合方式。

5　 结 语

本文通过SOM算法对用户制造资源调度日志当中涉及的资源进行分类处理，将高维的制造资源序列转化为低维的制造资源种类序列，之后通过滑动窗口提取不同粒度下的符合用户资源组合要求的经常被用户调用的资源集合，为之后用户再一次调用云制造服务时推荐更贴合用户需要的资源集合，最后通过模拟实验验证了该算法相较于只进行固定组合在响应时间上更短。本文提出的具有创新性的基于SOM聚类算法的资源聚合方式，通过对用户资源调度的实例分析用户常用的资源调度模式，进而采用这类模式对用户调用的资源组合进行推荐，而不是单纯地从资源本身的性质分析资源间的关系，为资源组合推荐提供了一种可能的思路。同时不可忽视的是时效性对于用户调度方式的影响，即用户对于某类调度方式的喜欢是有时效性的，所以对于用户调度实例的分析也应该考虑到时效性的影响，这是将来工作的中心。

参考文献

[1] 汤华茂， 郭钢. 云制造资源虚拟化描述模型及集成化智能服务模式研究［J］. 中国机械工程， 2016， 27（16）：2172-2178. DOI: 10.3969/j.issn.1004-132X.2016.16.008 .

[2] TANG H M， GUO G. Virtualization descriptions and integrated intelligent service model of cloud manufacturing resources ［J］. China Mechanical Engineering， 2016， 27（16）：2172-2178 （Ch）. DOI: 10.3969/j.issn.1004-132X.2016.16.008 .

[3] 李伯虎， 张霖， 王时龙，等. 云制造——面向服务的网络化制造新模式［J］. 计算机集成制造系统， 2010， 16（1）： 1-7. DOI：10.13196/j.cims.2010.01.3.libh.004 .

[4] LI B H， ZHANG L， WANG S L， et al. Cloud manufacturing： A new service-oriented networked manufacturing model［J］. Computer Integrated Manufacturing Systems， 2010， 16（1）： 1-7. DOI：10.13196/j.cims.2010.01.3.libh.004（Ch ）.

[5] 李长云， 王宏起， 李玥. 基于经济控制论的云制造服务平台特性分析［J］. 计算机集成制造系统， 2017， 23（6）： 1224-1233. DOI：10.13196/j.cims.2017.06.008 .

[6] LI C Y， WANG H Q， LI Y. Characteristics analysis on cloud manufacturing service platform based on economic cybernetics ［J］. Computer Integrated Manufacturing Systems， 2017， 23（6）： 1224-1233. DOI：10.13196/j.cims.2017.06.008 （Ch ）.

[7] 任磊， 张霖， 张雅彬， 等. 云制造资源虚拟化研究［J］. 计算机集成制造系统， 2011， 17（3）： 511-518. DOI：10.13196/j.cims.2011.03.65.renl.011 .

[8] REN L， ZHANG L， ZHANG Y B， et al. Resource virtualization in cloud manufacturing ［J］. Computer Integrated Manufacturing Systems， 2011， 17（3）： 511-518. DOI：10.13196/j.cims.2011.03.65.renl.011 （Ch ）.

[9] LIU Y K， WANG L H， WANG X V， et al. Scheduling in cloud manufacturing： State-of-the-art and research challenges ［J］. International Journal of Production Research， 2019， 57（15/16）： 4854-4879. DOI：10.1080/00207543.2018.1449978 .

[10] LI F， ZHANG L， LIAO T W， et al. Multi-objective optimisation of multi-task scheduling in cloud manufacturing ［J］. International Journal of Production Research， 2019， 57（12）： 3847-3863. DOI：10.1080/00207543.2018.1538579 .

[11] CHEN F Z， DOU R L， LI M Q， et al. A flexible QoS-aware Web service composition method by multi-objective optimization in cloud manufacturing ［J］. Computers & Industrial Engineering， 2016， 99： 423-431. DOI：10.1016/j.cie.2015.12.018 .

[12] 李海波. 云制造环境下基于工作流的多粒度资源组合方法［J］. 计算机集成制造系统， 2013， 19（1）： 210-216. DOI：10.13196/j.cims.2013.01.212.lihb.022 .

[13] LI H B. Approach to multi-granularity resource composition based on workflow in cloud manufacturing ［J］. Computer Integrated Manufacturing Systems， 2013， 19（1）： 210-216. DOI：10.13196/j.cims.2013.01.212.lihb.022（Ch ）.

[14] DING S H， HAN J L， MENG X J， et al. Multi-granularity modeling and aggregation of design resources in cloud manufacturing ［J］. IEEE Access， 2020， 8： 130797-130819. DOI：10.1109/ACCESS.2020.3009678 .

[15] 曹啸博， 许承东， 胡春生， 等. 基于设计能力的设计资源聚合方式［J］. 计算机集成制造系统， 2015， 21（9）： 2296-2311. DOI：10.13196/j.cims.2015.09.005 .

[16] CAO X B， XU C D， HU C S， et al. Design resources agglomeration methods based on design ability ［J］. Computer Integrated Manufacturing Systems， 2015， 21（9）： 2296-2311. DOI：10.13196/j.cims.2015.09.005 （Ch ）.

[17] LIU J， CHEN Y L. A personalized clustering-based and reliable trust-aware QoS prediction approach for cloud service recommendation in cloud manufacturing ［J］. KnowledgeBased Systems， 2019， 174： 43-56. DOI：10.1016/j.knosys.2019.02.032 .

[18] 唐春华，赵爽耀，黄挺，张强.基于QoS多方异质评价与供需双约束的云制造服务推荐模型［J/OL］. ［2021-10-10］.

[19] TANG C H， ZHAO C Y， HUANG T， et al. Cloud Manufacturing Service Recommendation Model Based on QoS Multi-party Heterogeneous Evaluation and dual Constraints of Supply and Demand ［J/OL］. ［2021-10-10］.

[20] FU T C， CHUNG F L， NG V， et al. Pattern Discovery from Stock Time Series Using Self-Organizing Maps ［EB/OL］.［2021-08-10］. https：//

[21] 彭功状， 吴友琪， 何安瑞. 多粒度制造服务建模与调度方法研究［J］. 华中科技大学学报（自然科学版）， 2020， 48（5）： 80-85. DOI：10.13245/j.hust.200515 .

[22] PENG G Z， WU Y Q， HE A R. Research on modeling and scheduling method of multi-granularity manufacturing service ［J］. Journal of Huazhong University of Science and Technology （Natural Science Edition）， 2020， 48（5）： 80-85. DOI：10.13245/j.hust.200515（Ch ）.

基金资助

国家重点研究计划(2019YFB1706401)