复杂网络脆性理论支持的生产车间鲁棒性分析*

李华华，袁逸萍，李晓娟，冯欢欢

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



复杂网络脆性理论支持的生产车间鲁棒性分析*

李华华，袁逸萍，李晓娟，冯欢欢

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

针对生产车间生产过程的鲁棒性和脆弱性问题，基于复杂网络理论，构建了生产车间网络模型，借鉴负荷-容量模型，建立了生产车间的网络故障模型；对生产车间网络进行了网络拓扑特性与鲁棒性分析，通过仿真分析的方法研究了生产车间网络的故障传播特性。最后，以某实际生产车间的生产过程为例进matlab仿真仿真实例分析了不同干扰方式下生产车间网络的鲁棒性，发现选择性干扰下生产车间网络具有脆弱性，随机干扰下生产车间网络具有较强的鲁棒性。

生产车间；复杂网络；鲁棒性

0　引言

自复杂网络的小世界效应及无标度特性被发现以来，复杂网络的研究就进入了一个划时代的阶段[1-2]，人们开始关注复杂网络的拓扑结构和网络的鲁棒性。目前研究复杂网络的鲁棒性[3-5]问题是研究复杂网络的一个热点。针对复杂网络的鲁棒性问题，张怡等[6-8]分析了供应链网络的鲁棒性，发现通过改变网络拓扑结构和演化机制可以提高网络的鲁棒性；陈晔[9]研究了分层复杂网络的鲁棒性，揭示不同层次的网络对随机攻击具有较强的鲁棒性，对选择性攻击具有脆弱性；毛凯[10]针对网络结构中结点连接特点，将网络划分为三种网络并且分析了三种网络的鲁棒性与稳定性的关系；徐凤[11]基于复杂网络理论研究了高铁-民航复合网络的鲁棒性。

复杂网络的鲁棒性可以通过触发网络故障发生的过程来体现，在众多相继故障模型当中由Moreno[12-13]等人提出了一种基于负荷-容量模型的相继故障的模型被广泛用于研究不同网络拓扑结构复杂网络的相继故障行为。在该模型中给各个节点赋予一个初始负荷和初始容量,当网络中的节点受到干扰使节点的负荷大于节点的容量从而触发故障，把该节点的负荷按照一定的机制分配给其它的节点，并且去除该节点，那些接收了额外负荷的节点由于负荷超过了容量也可能产生故障，这样故障扩散开来继而产生相继故障。相关的研究[14]表明负荷-容量模型的相继故障模型能较好地反映典型网络拓扑结构的相继故障行为。因此，本文借助负荷-容量模型来分析生产车间的故障传播特性，通过仿真分析的方法对生产车间网络故障模型进行仿真，来分析生产车间网络的鲁棒性和脆弱性。

1　基于复杂网络的生产车间网络鲁棒性定义

生产车间网络的鲁棒性是指系统在运行过程中设备或者资源受到不确定因素(设备故障、工艺路线变更、人为破坏等)的干扰下，有替代的设备或者资源能使生产车间网络正常运行或者保持其主要功能的能力。对生产车间网络来说，鲁棒性是一个重要的整体指标。生产车间网络受到干扰后如一台设备或者部分设备发生故障不能完成加工任务，发生故障的设备就会断开与其它设备的连接，在网络上表示为移除此节点从而导致原有的复杂网络结构发生变化，也就网络的拓扑结构发生了变化，此设备就会把加工任务分配给能代替此设备完成加工任务的设备，如果没有替代的设备，则零件不能进行下一步加工而发生等待，导致后续工序不能进行，这造成了其它设备生产能力和人力资源的浪费；如果干扰因素为工艺路线变更，则在网络上表现为移除变或者加边，设备的加工任务会重新分配。如果故障设备达到一定的规模则生产车间网络就会瘫痪，所以生产车间的鲁棒性对车间生产十分重要。本文主要考虑上面的设备故障这一类情况，并从复杂网络的相关概念与定义展开对生产车间网络鲁棒性的研究。

1.1相关概念与定义

(1)度与度分布

在生产车间网络中，δμν表示节点μ汇入节点ν，生产车间网络的度包括入度和出度，出度表示从本节点出发连向其它节点的边数，对应的生产车间网络表示该节点的紧后工序的节点数。入度表示从其它节点连向本节点的边数，对应的生产车间网络表示紧前工序的节点数。点的出度和入度定义如下：

(1)

用函数P(k)来描述网络中节点的度分布特性，P(k)定义为任意的选取网络中一个节点，节点的度值为恰好为k的概率。度与度分布是复杂网络理论中的重要概念，现实生活中许多网络度分布可以用形如函数P(k)∝k-γ(也称为无标度网络)来描述，如电子邮件网、单词搭配网络、代谢网等。

(2)干扰后生产车间网络最大连通子图的大小

假设生产车间网络G在受到干扰后，网络中的节点ν1,ν2,…,νm(1≤m≤n)与干扰发生前有连接的部分节点或者全部的节点断开连接，这样网络G被分割成几部分连通的子网络G1,G2,…,Gm(1≤m≤n)其中所含节点数目最多的那个子网络即是网络的最大连通子图，为干扰发生后的最大连通子图定义为：

(2)

其中Ki为子网络Gi的节点数目。

(3)连通度

当生产车间网络受到干扰时，网络的连通度φ反映了网络节点的连接状况，本文将连通度定义为干扰后网络中的最大连通子图与干扰前网络大小n的比值。

φ=R/n

(3)

干扰发生后如果R很大，即生产车间网络内部生产线上的节点很多，生产车间网络结构很稳定，如果R很小则网络很脆弱。

2　生产车间网络模型描述

图1　生产车间网络拓扑结构

生产车间网络：在零件的工艺矩阵中一个零件经过多台设备加工，节点之间通过工艺或物流关系建立关系，这样通过构建节点之间的工艺关系矩阵来描述生产车间网络。

3　生产车间网络故障模型及故障机理机理描述

3.1基于负荷-容量模型的生产车间网络故障模型

(4)

式中ρ代表Weibull指数，ρ的大小可以调节个节点的阈值分布情况。

在某个时刻，生产车间当由于某种原因(设备故障、紧急插单、工艺路线变更等)使某个节点或者几个节点的负荷超过其容量即σ≥σi，将故障节点的负荷按照一定的机制(分配给能代替故障节点完成加工任务的节点)给网络中的其它节点，这些节点接收了额外的负荷从而超出容量发生故障，这样故障规模可能扩散，最终整个生产车间网络可能崩溃。

3.2干扰机制

为了分析生产车间网络的鲁棒性，采用两种干扰方式，即随机干扰和选择性干扰。

(1)随机干扰

在生产车间网络中由于不确定的干扰因素的影响，例如：设备故障、计划更改、物料等待等都会对网络造成干扰，本文主要考虑设备故障这一干扰因素。生产网络中的设备故障是随机发生的，故障发生的概率服从Weibull分布，若生产车间网络中的节点发生故障，则应该在网络中去除发生故障的节点，在网络中表现为随机去除节点。

(2)选择性干扰

在生产车间网络中，选择性干扰(蓄意干扰)是指选按照一定策略择攻击网络节点度较大的节点或“桥接”节点，致使网络发生相继故障，这些节点是生产车间网络中的关键节点如瓶颈节点、“桥接”节点、度值大的节点等。一般来说，生产过程中度值大的节点所承担的负荷要比其它节点所承担的负荷要大，假设节点发生故障的概率正比于节点的度值，即度值越大的节点越容易失效。在生产车间网络中，选择性干扰是人为的破坏这些关键节点。

在两种干扰方式下，按一定的比例对去除原生产车间网络中的节点，对生产车间网络拓扑特性的变化进行分析，包括连通子图、度分布、连通度，故障规模，并从中得出结论。

4　实例分析

为了分析生产车间网络故障产生的影响，本文选取网络随时间变化的失效节点比I(t)表示网络的失效程度，网络的故障节点比为：

Nt—网络受到干扰后发生故障的规模；N—表示网络总的节点数。

以某变压器生产车间为例，该生产车间涉及多种零部件和多类资源，生产车间网络规模庞大，生产车间有超过两百多个工位，有设备77台，工艺流程23条，工艺之间的约束关系。为了方便仿真分析，我们选某个时间段内20个订单到达生产车间时进行仿真分析，为分析生产车间的鲁棒性，在两种干扰方式下我们对网络中的节点按照一定的比例进行移除，分析生产车间网络的拓扑结构的变化，如网络连通度、连通子图、度分布等，并且对结果进行分析。

4.1度分布

采用仿真实验的方法对该机加工车间网络的度分布进行统计，网络度分布图如图2所示。

图2　生产车间网络度分布

发现该机加工车间网络整体服从幂率指数为2.1～2.8的幂率分布，说明模型仿真与BA无标度网络和小世界网络模型的特性相符，具有行业特色的小世界网络和无标度网络的特性，如度分布在四十以内。生产车间网络中多数的节点相连的节点相对较少，节点失效对网络拓扑性的影响较大，维持生产车间的正常工作十分重要；网络中大部分节点的度值较小，少部分节点的值大，但节点度最大值被控制在一定范围内，这与实际的生产车间网络中的服务有限或者网络流量的阈值比较吻合。

4.2生产车间网络鲁棒性分析

为了分析生产车间的鲁棒性，本文采取随机干扰和选择性干扰两种方式对网络进行干扰。生产车间网络节点受到干扰时，可能会导致网络部分或者全部崩溃，在本文中，随机干扰是指随机的删除网络中的部分节点，而选择性的干扰是每次指删除选择网络中那些度值大的节点，最后用网络连通度和连通子图来衡量网络的鲁棒性如图3所示。

图3　随机和选择性干扰下网络的连通度

图4　随机和选择性干扰下网络的连通子图的大小

从图3和图4可知可以知道对于随机干扰，随机的干扰网络(增加负荷，去除节点)中的某些节点，网络连通度下降缓慢，大部分节点连通，当随机的删除网络中的节点达到90%时，最大连通子图包含的节点为零，网络几乎不连通；对于选择性的干扰(蓄意干扰)，网络的连通度相对于随机干扰呈线性下降趋势，生产车间网络溃散开，连通子图规模减小，这表明对于那些度大的节点的干扰更容易破坏网络原有的拓扑结构，当选择性的干扰网络中43%的节点时，网络几乎不连通，这表明对于生产车间这种具有无标度特性的网络，蓄意攻击网络中度值大的节点对网络的破坏程度更大。

选择不同的干扰机制，得到不同干扰机制下时间与网络故障规模关系图，从图5中可以看出，相同扰动下，选择性干扰比随机干扰传播更快，对网络的破坏性更大。

图5　不同干扰机制下网络故障规模扩散过程

5　结束语

本文应用复杂网络理论的基本知识，对生产车间网络进行了描述，定义了生产车间网络相关概念和生产车间网络的鲁棒性，分析了该生产车间网络的度分布，发现该生产车间网络具有小世界网络和无标度网络的特性，通过matlab仿真实验分析了在两种干扰情况下网络的鲁棒性，结果表明生产车间网络在生产过程中对随机干扰网络表现很强的鲁棒性，而对选择性的干扰下网络表现出脆弱性，选择性干扰机制下对生产车间网络的破坏程度较大，网络发生故障的规模越大且速度较快。

[1] 汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社，2006．

[2] 孙玺菁,司守奎.复杂网络算法与应用[M].北京:国防工业出版社,2015.

[3] Mahdi Jalili. Error and attack tolerance of small-worldness in complex networks[J]. Journal of Informetrics,2011,5(3):422-430.

[4] Albert, Jeong, Barabasi. Error and attack tolerance of complex networks[J]. Nature,2000,406(6794):378-382.

[5] 冯欢欢,袁逸萍,李晓娟. 制造车间生产过程网络鲁棒性分析[J]. 制造技术与机床,2015(11):21-24.

[6] 张怡,熊杰,冯春.基于复杂网络的供应链网络鲁棒性分析[J].计算机仿真,2012(11):370-373.

[7] 华连连,隋宇心,李弘. 基于复杂网络的供应链鲁棒性分析[J]. 上海管理科学,2015(1):42-47.

[8]刘小峰,陈国华.基于复杂网络的供应链鲁棒性分析[J].东南大学学报(自然科学版),2007,37(S2):237-242.

[9] 毛凯.复杂网络结构的稳定性与鲁棒性研究[J]. 计算机科学,2015,42(4):85-88.

[10] 陈晔,赵金超,齐欢.分层复杂网络的鲁棒性研究[J].兵工学报,2009,30(6):839-843.

[11] 徐凤,朱金福,苗建军. 基于复杂网络的空铁复合网络的鲁棒性研究[J]. 复杂系统与复杂性科学,2015,12(1):40-45.

[12] Moreno Y, Gomez J B, Pacheco A F. Instability of scale-free networks under node-breaking avalanches. Europhys. Lett. ,2002,58(4): 630-636.

[13] Motter Adilson E,Lai Ying-Cheng. Cascade-based attacks on complex networks.[J]. Physical Review E (Statistical, Nonlinear, and Soft Matter Physics),2003,66(6):65-102.

[14] 郭迟,王丽娜,李玉,等. 基于负荷-容量模型的网络相继故障研究[J]. 计算机研究与发展, 2012,49(12):2529-2538.

(编辑李秀敏)

Robustness Analysis of Production Workshop Network Based on Complex Networks

LI Hua-hua,YUAN Yi-ping,LI Xiao-juan,FENG Huan-huan

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

Aiming at the robustness and vulnerability issues of the production workshop production process based on complex network theory, constructing production workshop network model, Learning from the load-capacity model, Establishing network fault model of production workshop based on the theory of complex networks; The topological characteristics and robustness network are analyzed based on the complex network theory and studying the fault propagation characteristics manufacturing workshop network through simulation analysis method. Finally, the actual production workshop as an example, it analysis the actual production workshop network robustness under different methods of disruption, which shows the fragility for target disruption and better robustness for random disruption through matlab simulation.

manufacturing workshop ; complex network; robustness

R=max{Ki,i=1,2,…,n}

P(σi)=1-e-(σi)ρ

I(t)=Nt/N

1001-2265(2016)09-0149-04DOI:10.13462/j.cnki.mmtamt.2016.09.043

2016-03-05；

2016-04-14

国家自然科学基金(51365054)；新疆维吾尔自治区科技厅“十二五”重大专项(201130110-1)

李华华(1989—)，男，湖南耒阳人，新疆大学硕士研究生，研究方向为复杂生产系统建模与仿真、优化控制，(E-mail)a1154290709@163.com；通讯作者：袁逸萍(1973—)，女，乌鲁木齐人，新疆大学教授，博士，研究方向为计算机集成制造、工业工程，(E-mail)yipingyuan@163.com。

TH166;TG659

A