基于病毒传播模型的制造系统关键资源识别指标评价

吴家贝，常建娥，张 峰

(武汉理工大学 机电工程学院，湖北 武汉 430070)

0 引言

随着顾客对多品种短周期产品需求的日趋增长，加大了制造系统的复杂程度，保证制造系统的稳定运行是提高产量和企业竞争力的关键[1]。然而，现有制造系统包含大量资源节点(如设备、工站、零部件等)，而且资源节点间的关系(如工艺先后关系、装配先后关系等)十分复杂[2]，当某一资源节点出现故障时，对于后道工序可能造成物料供应不及时，对于前道工序可能造成物料阻塞，即产生双向影响，影响范围扩散到一定程度就会导致停线等严重后果，而关注系统中的每个资源节点是否正常运作并不现实，因此有效识别对制造系统影响大的资源节点并给予足够重视，对于保证制造系统稳定运行意义重大。

复杂网络可以清楚地表示系统结构及其耦合关系，其对识别复杂系统关键资源节点意义重大，而且网络结构特征常被用于衡量节点重要性[3]。因此，复杂网络被广泛用于识别电力网络[4]、供应链网络[5]、化工合成网络[6]等的关键节点，以保证系统稳定运行。由于制造系统包含大量资源节点，且节点间的关系十分复杂，国内外学者也开始采用复杂网络理论识别制造系统中的关键资源。李晓娟等[2]以工位为节点、工位间的物料流动为边构建网络模型，并通过介数、网络效率和节点负载构建了瓶颈度指标来识别瓶颈工位；Becker等[7]以设备为节点、设备间的物料流动为边构建网络模型，融合多种节点中心性指标得到设备重要度综合评价指标，然后通过对比PageRank算法的排序结果来评价该综合评价指标的优劣；Blunck等[8]指出生产过程中的瓶颈即具有最高利用率或最长等待时间的节点，但对于节点数量较多的制造系统，收集并分析相关数据的工作量较大，因此可以利用复杂网络中的拓扑指标初步识别瓶颈；李玉鹏等[9]在考虑网络拓扑特征的基础上加入节点的变化度、功能贡献率和更换成本，用于反映节点的自身属性；Gao等[10]从网络拓扑结构和功能属性两方面评估系统脆弱性，并通过网络效率损失识别系统中的脆弱节点，最后以发动机装配系统为例进行验证；向颖等[11]从系统脆弱性的角度出发，结合脆性风险熵识别出使用率高、到货率低和完成率不足的模块，为降低系统的整体脆弱性及保证系统稳定运行打下基础；张峰等[12]将复杂网络用于协同生产网络的脆弱性分析，并以节点删除后网络效率的下降程度作为评价节点重要性的指标。

上面关于制造系统关键资源节点识别指标可以分为两类：①利用制造系统网络模型的拓扑特征构建评价指标；②从制造系统脆弱性的角度出发，将脆性高或故障后对系统影响大的资源节点视为关键资源节点。然而，以制造网络的拓扑结构参数为衡量标准的识别结果受拓扑结构影响较大，而且对各指标的识别效果缺乏分析。

针对关键节点识别指标的评价，国内外学者做了大量研究。Wang等[13]以SIR(susceptible-infected-recovered)模型仿真所得的排序结果为标准，将该结果和多种排序方法的相似程度为方法优劣的衡量依据；Sara等[14]和Wang等[15]选取多种排序方法排名前10的节点为初始感染节点进行SIR模型仿真，通过比较感染节点数随时间的变化趋势来判断方法的优劣；多种排序方法排名前10的节点中存在大量重复节点，直接选取前10节点进行仿真会导致部分曲线近乎拟合，区分度不高，Du等[16]在以排名前10节点为初始感染节点的基础上，分别以方法间的不重复节点为初始感染节点进行SI(susceptible-infected)模型仿真；Namtirha等[17]在文献[15]的基础上，通过计算各排序方法对应指标的频率分布来衡量方法的优劣；Berahmand等[18]同时以SI模型和SIR模型进行方法优劣辨识；Zhang等[19]在各类方法排序结果的基础上，计算不同范围下的平均最短路径长度来衡量所选节点的重要程度，进而衡量方法的优劣；Fei等[20]和Wang等[21]在通过病毒传播模型辨识关键节点识别方法优劣的基础上，还通过比较删除排名靠前节点后的网络效率损失来衡量方法的优劣。综上，评价方法可分为两类：①指标间的评价，包括指标区分度和各方法排名靠前节点的影响传播能力；②基于病毒传播模型的评价，以病毒传播模型所得结果为标准，计算各类指标排序结果与病毒传播模型排序结果的相似程度。由于本文是以制造资源发生故障后对制造系统的影响程度作为资源节点重要程度的衡量标准，当某一资源发生故障后，故障的影响会沿着工艺路线双向传递，如果短时间内故障影响扩散到较大范围会导致严重后果，则将对应的初始感染节点视为关键节点。故障影响的传播机制与病毒传播模型的运行机制类似，因此将病毒传播模型引入制造系统关键资源节点识别指标优劣的辨识中。

针对制造系统关键资源识别指标评价问题研究的不足，本文利用病毒传播模型相关知识对方法优劣进行评价。首先，基于复杂网络的基本原理构建制造系统网络模型；其次，介绍几种典型关键节点识别指标；接着，介绍基于病毒传播模型的关键节点识别指标评价模型，以病毒传播模型仿真所得排序结果为标准，计算该标准和待评估指标排序结果的重复节点数和Kendall Rank相关系数；然后，以汽车内饰装配线为例验证模型的可行性；最后，对上述研究成果进行总结。

1 制造系统网络模型构建

设一个无向图G(V,E)，有n个节点和m条边，节点的集合为V={1,2,…,n}，ei,j表示节点i，j的连边，邻接矩阵为A=[aij]n×n，其中：

(1)

制造网络是由制造资源节点(如设备、工站、零部件等)和资源间所存在关系(装配先后关系等)组成的网络。因为本文是以制造资源故障后对整个系统的影响程度作为资源节点重要程度的衡量标准，而且当某一资源节点出现故障时，会对前道和后道工序产生双向影响，所以本文构建的网络模型为无向网络。以汽车终二装配线部分工位(如图1)为例构建装配系统网络模型，其中圆形表示功能件，六边形表示紧固件，正方形表示工站。绘制如图2所示的网络模型图，图中节点表示装配作业要素涉及的零部件，边表示装配的先后关系。

2 制造系统关键资源识别

复杂网络中衡量节点重要性的常用指标有度中心性(Degree Centrality, DC)、介数中心性(Betweenness Centrality, BC)和接近中心性(Closeness Centrality, CC)[19]。

定义1度中心性。节点i的度Di表示和节点i直接相连的节点数量，则度中心性

(2)

度中心性可以反映节点与其单层邻居节点的连接情况，属于节点的局部特征。在制造网络中，节点的度中心性越高，发生故障时影响的传播能力越强。

定义2介数中心性。gjk(i)表示节点j和节点k之间的最短路径通过节点i的条数，gjk表示节点j和节点k之间的最短路径条数，则节点i的介数中心性

(3)

介数中心性反映节点对的最短路径经过某一节点的情况，属于节点的全局特征，经过一个节点的最短路径条数越多，该节点越重要。在制造网络中，节点的介数中心性越大，故障后的影响传播得越快。

定义3接近中心性。dij表示节点i和节点j之间的最短距离，di表示节点i到其他节点最短距离的平均值，

(4)

节点i的接近中心性CCC(i)为di的倒数，CCC(i)越大，节点和其他节点的耦合程度越大。接近中心性属于节点的全局特征，其表达式为

(5)

在制造网络中，节点的接近中心性越大，该节点发生故障后影响的扩散速度越快。

上面的节点重要度衡量指标虽然便于实施，但是均存在局限性，例如：通过度中心性反映节点重要性时无法区分度值相同节点的重要性，而且无法准确识别某些起到连接作用的“桥”节点[22-23]；介数中心性由于计算复杂度较高，在处理节点上万的大规模网络时效率不高，而且计算介数中心性时，存在大量不处于最短路径上的节点，这些节点对应的介数中心性均为0，指标区分度不高[22]；接近中心性只能用于连通网络，如果两节点不连通，则计算结果为0，另外还存在因某一最短距离过长而导致整体计算结果偏小的情况[22]。

在制造系统中，当某一节点发生故障后，其影响可能要经过多次传递才会导致整个系统崩溃，单从度中心性考虑可能会忽略某些度值不高但起到连接作用的桥梁节点，而且对于度中心性值相同的节点也很难区分其重要程度，主要原因是度中心性只考虑了单层节点，因此本文采用考虑多层邻居节点的改进度中心性指标表征节点的局部特征。

定义网络效率损失为节点删除后网络效率的下降比例。本文资源故障可以映射为该定义中的节点被删除，关键资源的识别标准也是某一资源节点发生故障后对整个系统的影响程度，该影响程度可以映射为网络效率下降的幅度，即网络效率损失；作为衡量系统效能的全局指标，网络效率被广泛应用于节点重要性评价指标的构建[2]和系统鲁棒性分析[24]，节点删除后的网络效率损失也是分析系统鲁棒性[12]和关键节点识别指标优劣[20-21]评价的方法。因此本文采用网络效率损失表征节点的全局特征。

定义4改进度中心性。改进度中心性为某一节点与其多层邻居节点度值的乘积除以距离平方的和，即

(6)

式中：Di为节点i的度数，Dj为节点j的度数，φi为节点i的一层～三层邻居节点的集合，dij为节点i和节点j的最短距离，因为最多考虑三层邻居节点，所以

(7)

CID(i)越大，节点i越重要。

定义5网络效率损失。网络效率损失为删除某一节点后网络效率下降的比例，即

(8)

式中：E(Gi)为移除节点i后的网络效率；E(G)为初始网络效率。

G的网络效率E(G)指该网络中任意两节点最短距离倒数之和的平均值，即

(9)

网络效率损失是从系统脆弱性出发的网络全局特征，其值越大，说明对应节点受到攻击时对系统造成的影响越大，即该节点越关键。

上面的各类指标可分为两类：①局部特征指标，包括度中心性和改进度中心性；②全局特征指标，包括介数中心性、接近中心性和网络效率损失。单从节点的局部特征或全局特征来判断节点重要性具有局限性，因此加权融合局部特征指标和全局特征指标得到综合评价指标。

(10)

式中α+β=1。

3 基于病毒传播模型的关键资源识别指标评估

本文是以制造资源发生故障后对整个系统的影响程度作为资源节点重要程度的衡量标准，病毒传播模型在许多传播行为的研究都具有一定的适用性[25]，很多专家学者采用病毒传播模型来辨识关键资源识别指标的优劣。在上述研究中，用到的病毒传播模型分为SI病毒传播模型和SIR传播模型两类。

在SI模型中，网络节点状态分为两类：①易感染状态S，在以一定概率β被其邻居感染节点I感染后，原S状态的节点由S状态变成I状态；②感染状态I，由初始感染节点和后期由S到I的节点组成，且一直保持I状态，并具有以一定的概率β感染其邻居S节点的能力，其中t时刻处于I状态的节点数量用F(t)表示。在SIR模型中，S和I的含义和SI模型一致，R则为节点的第3种状态——免疫状态R，处于感染状态I的节点有一定的概率γ被治愈，且被治愈后的节点不会被再次感染，即免疫病毒感染。制造系统中故障的出现是随机的，无法保证故障修复后该资源一定不会再次出现问题，因此本文以SI病毒传播模型仿真所得的结果为标准，以各类指标所得结果与仿真结果的相似程度作为指标优劣的评判依据，相似程度越高，对应的关键节点识别指标越好。

在制造网络中，S表示处于正常工作状态但可能被故障影响的节点，I表示受到故障影响的节点，该类节点处于故障状态且具有将故障影响传递下去的能力，β为故障影响传递的概率，F(t)为t时刻受故障影响节点的数量。因为在SI模型中，所有节点最终都会被感染成I状态，所以F(t)趋于稳态的耗时t越少，初始感染节点的传播能力越强，即其对应的排序指标越好。之前研究对“稳定状态”的判断均通过感染节点数的变化曲线直接看出，但无法有效判断近乎拟合的曲线，为了能够更精确地描述“稳定状态”，本文引入传播增量模型，增量函数f(t)=F(t+1)-F(t)，f(t)≤λ且最接近λ时认为从t时刻开始处于稳态，t值越小，初始感染节点的传播速度越快，即对应的节点越重要；对于t值相同的情况，可以比较其对应的F(t)值，在传播速度相同时，F(t)越大，传播范围越广，对应的节点越重要。

在实际制造过程中，同一时刻出现故障的零部件可能不止一个，因此本文在SI模型仿真时分别以多个节点和单个节点作为初始感染节点，考虑到方法间的差异性，选取多个节点时剔除了综合评价指标和其他5种指标间重复出现的节点。

在不同加工环境(高温、高负荷、工艺变更等)下，故障影响的传播概率不同，为了提高方法的适用范围，本文考虑故障传播概率不同时的仿真结果。

为了能够定量地比较关键节点识别指标的优劣，本文通过计算各类识别指标排名前10的节点和SI模型仿真出的排名前10的节点间的重复节点数和Kendall Rank相关系数，来确定各类指标所得结果与SI模型仿真结果的相似程度，相似程度越高，该指标越好。

定义7重复节点数。重复节点数即两两排序结果中相同节点的数量，本文重复节点数指关键节点识别指标的排序结果与SI模型仿真排序结果相同节点的数量，其值越大，对应的关键节点识别指标越好。

定义8Kendall Rank相关系数。Kendall Rank相关系数用于测量两个随机变量相关性的统计值，常用字母τ表示，τ∈[-1，1]，τ=1表示两个随机变量拥有一致的等级相关性，τ=-1表示两个随机变量拥有完全相反的等级相关性，τ=0表示两个随机变量相互独立[15]。假设有两组随机变量X,Y，其元素个数均为n，设(xi,yi)和(xj,yj)为两组不同的观察值，其中1≤i≠j≤n。当xi>xj且yi>yj或xixjyiyj时，认为这两组元素是不一致的；当xi=xj且yi=yj时，认为这两组元素既不是一致又不是不一致的。Kendall Rank相关系数的计算公式为

(11)

式中：c为一致性元素的组数；d为不一致性元素的组数。

本文X为各种关键节点识别指标排名前10的节点，Y为SI模型仿真所得排名前10的节点，τ越大，对应的关键节点识别指标越好。

本文的研究思路和技术路线图(如图3)如下：

(1)以制造资源为节点、资源间的装配先后关系为边构建制造系统网络模型。

(2)采用度中心性、介数中心性、接近中心性、改进度中心性、网络效率损失和综合评价指标识别关键资源节点，各指标排名前10的节点为关键资源节点。

(3)分别选取综合评价指标所得的关键资源节点和其他5种指标所得的关键资源节点中的不重复节点为初始感染节点，进行SI模型仿真，绘制感染节点数随时间的变化曲线和感染节点数增量随时间的变化曲线，通过分析曲线变化情况来评价6种关键节点识别指标的优劣。

(4)以单个关键资源节点为初始感染节点依次进行SI模型仿真，得到基于SI模型的排序结果，以此作为指标优劣的评价标准。计算该标准与不同指标排序结果的重复节点数和Kendall Rank相关系数，评价方法优劣；改变传播概率β，取值区间为[0.01,0.1]，取值间隔为0.01，分析故障影响传播概率不同情况下指标的优劣。

(5)以内饰装配线为例，验证评价方法的可行性。

4 实例分析

4.1 内饰装配线网络模型的构建

本文以W厂汽车内饰工段装配线为例进行验证。首先构建网络模型，该网络以装配过程中消耗的物料(如紧固件和功能件)为节点，以其装配先后关系为边，绘制如图4所示的网络图。

4.2 内饰装配线网络关键资源的识别

采用前面提到的指标识别内饰装配线的关键资源，各类指标所得的结果汇总如图5所示。该工段有221种零部件，选取各识别指标中排名前10的资源，如表1所示

表1 各指标排名前10资源统计表

4.3 基于SI病毒传播模型的指标评估

4.3.1 排名前10的不重复节点为初始感染节点

通过表1可知综合评价指标和其他指标间存在大量重复节点，直接以排名前10的节点为初始感染节点无法体现指标间的差异性，因此本文以综合评价指标和其他指标排名前10的不重复节点为初始感染节点。结合历史故障数据，在该案例中故障影响传播概率β=0.02，SI模型仿真结果如图6所示。

由图6可见，综合评价指标(T)的F(t)变化曲线一直在度中心性(DC)和网络效率损失(E)的F(t)的变化曲线上，因此综合评价指标明显优于度中心性和网络效率损失；综合评价指标的变化曲线前期一直在介数中心性(BC)的F(t)变化曲线上，后期接近重合，因此综合评价指标略优于介数中心性；虽然综合评价指标(T)的F(t)变化曲线和接近中心性(CC)的F(t)变化曲线几乎重合，但是其增量f(t)的变化曲线在前期一直在接近中心性的增量曲线上，因此综合评价指标略优于接近中心性;改进度中心性(ID)的F(t)变化曲线前期一直在综合评价指标的F(t)变化曲线上，后期接近重合，因此改进度中心性略优于综合评价指标。综合来看，综合评价指标和改进度中心性较其他指标更优。

4.3.2 排名前10的单个节点为初始感染节点

综合考虑各排序指标排名前10的节点，分别以单个节点为初始感染节点进行SI模型仿真，感染率β=0.02。采用前面提到的对稳态的判别方法，得到通过SI模型仿真的重要性排名前10个节点分别为80、15，90，58，31，87，74，118，45，89；然后，分别计算SI模型仿真排序结果和6种指标排序结果的重复节点数及Kendall Rank相关系数，如表2所示；最后比较统计结果，综合评价指标无论在重复节点数还是Kendall Rank相关系数上均优于其他排序指标，证明该指标在关键资源识别上比其他指标更优。

表2 重复节点数和Kendall Rank相关系数统计表

考虑初始时间段的故障影响扩散情况，本例中因为整体时间范围取0～100，所以初始时间段选取0～20，再考虑初始时间段内每一次SI模型的仿真排序情况，分别计算每一次SI模型仿真排序结果和6种指标排序结果的重复节点数与Kendall Rank相关系数，如图7所示。可见在绝大多数时间点，综合评价指标的重复节点数较大，Kendall Rank相关系数最大，故该指标更好。

4.3.3 传染概率β不同的方法评估

上面案例中的故障影响传播概率β为定值，但是在其他制造系统中该值可能会不同，为了提高方法的适用范围，针对不同的β进行SI模型仿真，计算SI模型仿真排序结果和其他所有指标排序结果的Kendall Rank相关系数，如图8所示，其中β=0.01～0.1。由图8可见，β≤0.04时，综合评价指标(T)优于其他指标；β>0.04时，综合评价指标的关键资源识别能力有所下降，此时改进度中心性(ID)的关键资源识别能力最优。因此β较小时，综合评价指标在关键资源识别上更有效；β较大时，改进度中心性在关键资源识别上更准确。

5 结束语

本文结合故障影响在制造网络中的传播模式，提出基于SI病毒传播模型的关键资源识别指标的评价方法，并以汽车内饰装配线为例验证了该方法的可行性和适用性，主要工作如下：①以制造资源为节点、资源间的工艺先后关系为边建立制造系统网络模型；②采用多种关键节点识别指标识别制造系统关键资源；③提出判断基于SI病毒传播模型的制造系统关键资源识别指标优劣的评价模型；④以内饰装配线为例，验证了该评价方法的可行性和适用性，并得到综合评价指标在故障影响传播概率较小时最优、改进度中心性在故障传播概率较大时最优的结论。

本文的故障影响传播概率为定值，实际情况下故障概率会受多种因素影响，后期研究将更全面地考虑故障的产生机理，针对不同节点得到更为精确的故障影响传播概率；另外，本文的案例验证选用的是内饰装配线，属于离散制造系统，后期研究会继续探索该理论模型在流程制造系统中的应用。