谢 旺，袁逸萍，李晓娟

(新疆大学 机械工程学院,乌鲁木齐 830047)

基于网络分析的作业车间故障资源评价方法研究*

谢 旺，袁逸萍，李晓娟

(新疆大学 机械工程学院,乌鲁木齐 830047)

针对作业车间中不同的故障资源对车间网络影响程度不同，结合网络属性和制造属性构建车间网络节点影响力指标体系，在层次分析法的基础上，改进网络层次分析法(ANP)的结构以及标度指数提出改进网络层次分析法(IANP)，对车间网络中故障节点影响力进行分析及排序。网络层引入复杂网络理论，以制造资源为节点，工艺约束为连边构建车间网络。对网络层进行定量分析，对控制层进行定性分析，提高了评价分析的精确性。通过将文章中算法和度中心性、接近中心性、LeaderRank算法以及节点删除法进行对比，验证了该指标体系以及模型的有效性。

车间网络；节点故障；节点影响力；改进网络层次分析法

0 引言

车间网络[1]是对复杂制造系统的一种抽象的描述，其中包含大量制造资源(如：设备、工装、工作站等)。一个耦合度高的资源发生了故障可能导致关联资源的相继故障，最终可能导致整个制造系统的瘫痪[2]。挖掘与分析影响力大资源节点有助于理解整个车间网络的结构和功能，为故障传播的有效控制与预防提供依据。现有的节点重要性以及有影响力的传播节点研究,主要有以下几种方法：中心性评价方法，如度中心性、接近中心性、LeaderRank算法等[3]；多属性融合网络影响力节点识别方法[4]；熵权逼近理想解的排序方法(TOPSIS)[5-6]；邻域核心度指标算法[7]。以及结合介数中心性(BC)和Katz中心性(KC)提出的BKC方法[8]，通过相继删除BKC方法中识别的重要节点，以网络鲁棒性为衡量指标来验证方法的有效性；基于模糊层次分析和TOPSIS[9]，识别生产系统中关键机器，并通过依此删除关键节点来评估具有不同网络拓扑结构的系统鲁棒性。

然而车间网络中除了网络特性指标，生产属性如关键工序比率、不可替代程度、节点失效频度、失效影响程度、检测难易度等对节点的重要性也有影响。因此本文结合网络属性和生产属性构建车间网络节点影响力评价指标体系，更全面的分析了故障节点。基于网络层次分析法[10-11](Analytic Hierarchy Process，ANP)，并对ANP中的结构以及标度准则进行改进提出IANP分析法，对故障节点进行影响力排序。通过将本文算法和度中心性、接近中心性、LeaderRank算法进行对比，并借鉴节点删除法，用遗传算法分别求得影响力大的节点被删除后的最短交货期，来验证方法的有效性。

1 车间网络节点影响力评价指标分析

基于网络重要度拓扑特性指标构建网络属性集合INet=[kin，kout，Sin，Sout，C]=[入度，出度，入强度，出强度，聚类系数]；基于复杂制造系统中资源影响能力相关特性，构建制造属性集合IM=[V，T，F，H，D] =[关键工序比率，不可替代程度，节点失效频度，失效影响程度，检测难易度]。并结合网络属性和制造属性构建车间网络节点影响力评价指标体系，如图1所示。

图1 节点影响力评价指标体系

入度kin：上游节点与该节点直接相连数量，表示制造资源节点的加工对象范围。

(1)

Eji表示由节点j汇入节点Vi工序的数量。

出度kout：下游节点与该节点直接相连数量，表示制造资源节点加工能力的影响范围。

(2)

Eij表示资源节点Vi汇入节点j工序的数量。

入强度Sin：反映制造单元承担的任务量。

(3)

Wji为相应的权值。

出强度Sout：反映制造节点加工能力的影响程度。

(4)

聚类系数C：是指某个节点与其邻居节点间相互连接的紧密程度，可以反映车间网络中资源节点关键程度的大小。

(5)

ki表示与节点i有连边的节点的数目，Ei表示与i节点的邻居节点有关系的数目。

关键工序比率V：故障资源节点拥有关键工序越多，其对最大完工时间的影响越大。将资源i上的关键工序数量与总工序数量比较，得到资源i关键工序比率Vi，如公式：

(6)

式中，ORik表示资源Ri上的关键工序，ORih为资源Ri上的工序。

不可替代程度T：车间中已有可用于替代的资源的数量和比率也影响资源的不可替代程度。定义不可替代程度Ti，为资源Ri上的每道工序Oh可选择的机器数量的倒数之和。

(7)

式中，MhRi表示资源Ri上工序Oh的可选择机器量。

节点失效频度F：节点入度越大，其上游节点越多，即其他节点发生故障时传播给该节点的机会就越大，节点失效的概率就越高。定义一个节点失效发生频度：

(8)

失效影响程度H：节点出度越大，其下游节点越多，即该节点发生故障时传播给其他节点的机会就越大，对其他节点的影响程度就越大。定义严重程度：

(9)

检测难易度D：节点熵表示节点的不确定性，节点熵值越大节点状态不确定性越大，节点失效检测也就越难。定义检测难易度：

(10)

2 车间网络节点影响力评价方法

2.1 改进的网络层析分析法

网络层析分析法(Analytic Network Process, ANP)是由层次分析法(Analytic Hierarchy Process , AHP)拓展而来，与层次分析法(AHP)相比ANP具有更灵活的网络结构，在分析问题时既考虑了元素之间又考虑了元素集之间的相互依存关系，即内部依存性与外部依赖性。在构造判断矩阵时一般都使用Satty的(1/9,9)标度准则[11]，同样存在着两个问题：一是标度选择问题，1～9标度一致性检验效果不理想；二是专家偏好问题，判断矩阵受专家主观偏好的影响较大。

因此本文提出改进的网络层析分析法(Improved Analytic Network Process, IANP)，其结构分为上下两层：控制层主要考虑节点影响力的网络属性和制造属性，网络层为资源节点构建的车间网络，如图2所示。并将定量与定性标度相结合，对网络层进行定量分析，定量表达不仅比定性的表达更容易理解，也弱化了定性分析带来的主观误差。尤其针对部分资源故障特性存在高度相似的特点，定量分析带来了更准确的意义增加了判断的准确性。控制层元素采取0～2三标度法，容易选取标度值克服主观偏好带来的影响，并且不需要一致性检验，简化了分析过程的复杂性。

图2 基于IANP车间网络节点影响力评价模型

2.2 车间网络节点影响力评价

车间网络节点影响力评价IANP结构模型中控制层有元素P1,P2,…,Pm，即相对目标的准则。网络层元素中N个元素集R1,R2, …,RN中有元素ei1,ei2, …,ein(i=1,2)，对网络层重要度程度通过间接法判断。评价流程如图3所示。

图3 车间网络节点影响力评价流程

步骤1：以控制层为准则，以元素组中的元素为次准则构建判断矩阵，如表1所列。其中，在控制层中依据三标度准则，ei比ej重要时aij=2，ei和ej同等重要时aij=1，ei没有ej重要时aij=0。在网络层中进行定量比较判断矩阵如式(11)。

(1)

步骤2：依据特征根法得到排序向量，其归一化得，

(12)

式中，Wij的列向量为Ri中元素ei1,ei2, …,ein对Rj中的元素ej1,ej2, …,ejn的影响程度的排序向量。如果Ri中的元素不影响Rj中的元素，则Wij=0。

步骤3：根据特征向量，构建控制层下超矩阵W：

(13)

(14)

3 模型验证

3.1 车间网络模型的构建

以某作业车间为例，在15台机器(资源)Rj(j=1,2,…,15)上加工10类典型复杂工件Ji(i=1,2,…,10)共100道工序Oij(i,j=1,2,…,10)，其任务—资源映射关系如图4所示。图中如O11及其对应的连边表示工件J1的第一道工序可以在资源R11、R13和R15上加工。

图4 任务—资源映射关系图

根据作业车间调度的基本约束条件，通过遗传算法求得一个可行的调度解，如图5所示。其纵坐标表示工件所在的资源号，横坐标表示该道工序在所在资源上对应的加工时间。图中描述了如资源R1上对应的7道不同工件工序的加工时间及先后顺序。

图5 工序—资源二维甘特图

为了清晰描述制造资源节点间的耦合关系对网络模态进行降维，由二维调度甘特图向一维车间网络投影，即工序层向资源层映射。从图5中提取基础数据，将15个资源作为节点，100条工艺路径作为连边构建复杂加权有向车间网络[1]，如图6所示。图中边权即连边的粗细表示加工时间，连边的有向性表示工序间的约束关系，即同一个任务的工序存在时间上的先后约束。

3.2 节点影响力指标度量值的计算

根据公式(1)～公式(5)分别计算出各节点网络属性影响力指标度量值，计算结果如图7a所示。根据公式(6)～公式(10)分别计算出各节点制造属性影响力指标度量值，计算结果如图7b所示。

图6 工序—资源一维车间网络图

(a)节点网络属性影响力指标度量值

(b)节点制造属性影响力指标度量值图7 节点影响力指标度量值

3.3 故障节点的选取

故障节点选取规则，①可视故障节点，根据车间实际观测情况，判断生产过程中的节点故障状态。②不可视故障节点，定义节点超负荷为故障状态，参考文献[1]中公式并改进得：

(15)

即为总负载超过额定负载，m为工件数量，h为工序，Tijk表示为工件Ji的第j道工序在资源Rk上的加工时间；xijk为决策变量，当工件Ji的第j道工序在资源Rk上的加工时，xijk为“1”，否则为“0”。TRk为资源Rk的额定工作负载，QRk为节点Rk的服务能力。综合规则一、二，计算并选取故障节点R3，R8，R12，R14，R15。

3.4 故障节点影响力计算

基于IANP分析法的节点影响力评价过程中需要计算超矩阵、加权超矩阵、极限加权超矩阵，计算量相当大，通常需要借助计算机编程实现。本文借助超级决策Super Decision软件构建基于IANP车间网络节点影响力评价模型，用计算机来完成复杂的计算过程，求得结果如图8所示。

图8 故障节点影响力大小排序

3.5 结果分析

将本文算法和度中心性、接近中心性、LeaderRank进行对比[12]，得到每个算法的节点重要度排序。从表2中可以看出本文的算法与LeaderRank算法结果比较一致。而度中心性则认为节点的邻居节点越多其影响力越大，仅仅考虑了节点的局部信息具有一定的局限性；接近中心性通过计算节点与网络中其他所有节点距离平均值来衡量节点的重要性，虽然考虑了部分全局特性，但是评判标准单一，不能体现节点在车间网络中的重要性。

表2 车间网络节点重要性排序

为了进一步说明节点影响力评价指标体系以及基于IANP评价模型在分析车间网络中故障节点影响力的有效性，借鉴节点删除法在级联故障模型影响力节点识别中的应用[9]，在车间调度中依次删除故障节点。基于遗传优化算法求得依次删除故障节点对应生产计划中的最短交货期，结果如图9所示。对比图8和图9可以看出，故障节点在制造系统中影响力越大导致的最短交货期越长，符合资源故障对复杂制造系统影响的规律，从而验证了本文所提出的指标体系和评价模型的有效性。

图9 故障节点删除最短交货期

4 结束语

本文分析了车间网络中故障节点的影响力，主要研究有以下3点：

(1)在现有的网络指标基础上进一步改进，将网络属性和制造属性相结合，构建了车间网络节点影响力评价指标体系。

(2)提出了改进的网络层次分析法(IANP)，网络层引入复杂网络理论构建车间网络，对网络层采取定量分析，对控制层采取定性分析，定量定性分析的结合在一定程度上克服了层次分析法中标度选择专家主观偏好的问题，改善了评价结果的精确性。

(3)基于IANP对车间网络中故障节点影响力进行分析及排序，通过对比不同重要性评价方法结果验证了该指标体系以及模型的有效性，为后续进一步基于车间网络的故障传播与预防的研究提供帮助。

[1] 李晓娟,袁逸萍,孙文磊.基于网络结构特征的作业车间瓶颈识别方法[J].计算机集成制造系统,2016, 22(4):1089-1096.

[2] Kröning S, Denkena B. Dynamic scheduling of maintenance measures in complex production systems[J]. Cirp Journal of Manufacturing Science & Technology, 2013, 6(4):292-300.

[3] 刘建国,任卓明,郭强,等.复杂网络中节点重要性排序的研究进展[J]. 物理学报, 2013, 62(17): 1-10.

[4] Zhong L, Gao C, Zhang Z, et al. Identifying Influential Nodes in Complex Networks: A Multiple Attributes Fusion Method[M].Active Media Technology, 2014.

[5] Du Y, Gao C, Hu Y, et al. A new method of identifying influential nodes in complex networks based on TOPSIS[J]. Physica A: Statistical Mechanics and its Applications, 2014, 399: 57-69.

[6] Hu J, Du Y, Mo H, et al. A modified weighted TOPSIS to identify influential nodes in complex networks[J].Physica A Statistical Mechanics & Its Applications,2016,444:73-85.

[7] Bae J, Kim S. Identifying and ranking influential spreaders in complex networks by neighborhood coreness[J]. Physica A Statistical Mechanics & Its Applications, 2014, 395(4):549-559.

[8] Zhang Y, Bao Y, Zhao S, et al. Identifying Node Importance by Combining Betweenness Centrality and Katz Centrality[C]//2015 International Conference on Cloud Computing and Big Data (CCBD). IEEE, 2015: 354-357.

[9] Becker T, Wagner D. Identification of Key Machines in Complex Production Networks[J]. Procedia Cirp, 2016, 41:69-74.

[10] Chemweno P, Pintelon L, Van Horenbeek A, et al. Development of a risk assessment selection methodology for asset maintenance decision making: An analytic network process (ANP) approach[J]. International Journal of Production Economics, 2015, 170: 663-676.

[11] Saaty T L,Vargas L G. Models,Methods,Concepts & Applications of the Analytic Hierarchy Process [J]. International,2001,7(2):159-172.

[12] 顾亦然, 朱梓嫣, GUYi-ran,等. 基于LeaderRank和节点相似度的复杂网络重要节点排序算法[J]. 电子科技大学学报, 2017, 46(2):441-448.

EvaluationMethodResearchonJobShopFaultResourceBasedonNetworkAnalysis

XIE Wang, YUAN Yi-ping, LI Xiao-juan

(School of Mechanical Engineering, Xinjiang University, Urumqi 830047, China)

To analyze the influence of the fault nodes in manufacturing networks, we construct the influence index system of manufacturing network based on network and manufacturing attributes. Improved structure and scale index of Analytic Network Process (ANP) based on analytic hierarchy process (AHP) and the Improved Analytic Network Process (IANP) is put forward to analysis and sort the influence fault node in the manufacturing network. The complex network theory is introduced to make the manufacturing network in the network layer as manufacture resources for the nodes and the process constraints for the continuous construction. Take the quantitative analysis to the network layer, the qualitative analysis of the control layer. Considering both quantitative analysis and qualitative analysis to improve the accuracy of the analysis and evaluation. Finally, we verify the validity of the index system and the model.

manufacture network; node failure; node influence; improved analytic network process

1001-2265(2017)11-0153-04

10.13462/j.cnki.mmtamt.2017.11.041

2017-07-04；

2017-08-15

国家自然科学基金(51365054)；新疆维吾尔自治区自然科学基金(2014211A008)

谢旺(1991—)，男，湖南邵阳人，新疆大学硕士研究生，研究方向为计算机集成制造，(E-mail)xiewone@163.com；通讯作者：袁逸萍(1973—)，女，乌鲁木齐人，新疆大学教授，博士，研究方向为计算机集成制造，(E-mail) yipingyuan@163.com。

TH166；TG506

A

(编辑李秀敏)