复杂产品制造过程网络建模与演化分析*
2016-09-08李华华袁逸萍李晓娟田书广
李华华，袁逸萍，李晓娟，田书广
(新疆大学 机械工程学院，乌鲁木齐 830047)
复杂产品制造过程网络建模与演化分析*
李华华，袁逸萍，李晓娟，田书广
(新疆大学 机械工程学院，乌鲁木齐830047)
针对产品制造过程集成性、复杂性、动态性和分布性等特点，应用复杂网络理论分析产品制造过程网络的结构特性与演化规律。提出生成产品制造过程网络演化模型的算法。该算法在模型增长的同时考虑了内部点、边的动态演化，在此基础上建立了动态演化模型，同时推导了产品制造过程网络分布特性。最后对复杂机电产品制造过程网络进行仿真对比，结果表明复杂产品制造过程网络具有无标度特性。
产品制造网络；复杂产品；动态演化；无标度特性
0 引言
复杂产品的制造过程是涵盖多学科、多领域的一系列系统化的问题，具有集成性、复杂性、动态性和分布性等特点，这种跨领域、跨学科的产品特性使得产品制造过程变得越来越复杂。由于企业规模的逐渐增大和专业化程度的不断提高，产品制造团队的进一步扩大，出现了跨部门的协同制造，进一步加大了产品制造过程的复杂性。
日益激烈的竞争迫使企业必须积极寻求制造产品的新模式。文献[1]基于复杂网络理论研究了汽车供应链的网络结构特性。文献[2]运用复杂网络对产品制造过程的资源使用性能进行了仿真分析。文献[3]提出了针对扩散制造这种面向复杂武器装备批量生产的网络制造模式。文献[4]以飞机关键复杂零件制造为例对网络化制造与快速扩散制造进行了比较。文献[5]提出基于复杂网络的知识评价和关联性分析方法，构建用于企业制造能力评价的复杂网络模型，并以某航天企业的实施验证证明。文献[6]基于复杂网络理论对城市公交网络进行分析，以提高公交系统的正常和高效运行。文献[7]考虑加权复杂网络拓扑结构提出了一种基于网络贡献度的节点重要性评估法。文献[8]对制造业协作网络的应用进行了分析，复杂网络在制造业领域的应用处于初级阶段。通过对产品制造过程的研究，人们已经对复杂产品的制造过程有了较深入的了解。然而，从目前的研究状况来看，复杂的制造系统网络建模与仿真的研究尚未受到广泛的关注。
因此从复杂产品制造的网络模型入手，分析产品制造过程的演化特点，对此进行理论推导和证明，并在此基础上提出产品制造过程的演化算法。同时，根据此算法模拟产品制造过程网络，分析本模型的网络特性，与无标度网络的网络特性进行对比发现，产品制造网络具有无标度特性。这为以后产品制造网络的相关特性研究提供参考。
1 产品制造网络的复杂性
产品制造网络具有动态随机性、演化性、多样性等多种复杂特性。多样性：资源的种类复杂、性质各异、具有不同的服务质量属性，它们是分布的和相对独立的，既存在合作又存在竞争。因复杂产品制造过程的复杂性，过程对象动态性规律很难掌控，相关参数未知，同时小批量、多品种的产品组合使系统的复杂系数成倍增加[9]。演化性：整个产品制造过程在计划、制造、执行等各阶段都面临着诸多不确定性因素[10]，资源数量以及各资源之间的相互作用程度都会随各种动态不确定因素的变化而改变，因而会影响产品制造的结构和功能。动态随机性：资源节点遵守自组织管理模式，资源节点可以动态的加入或退出，同时任务需求随机动态到达。随着任务的到达和完成退出，资源的数量和加工时间时时刻刻在变化，因此产品制造过程对应的资源网络的节点数和权重也都会相应的变化。每个任务的处理时间都是一个随机变量，由于种种随机因素，比如资源供应的波动，加工设备的故障影响等都会带来任务处理时间的随机性。
2 产品制造过程复杂加权网络模型及特性
2.1产品制造过程复杂加权网络模型
复杂产品制造过程网络图可以用四元组描述，即G=(V，E，W，RU)，其中V表示节点的集合；E表示边的集合；W表示权重的集合；RU表示网络演化规则的集合。复杂产品制造过程网络模型各个元素解释如下：
节点集合V：将产品制造过程中每个任务的工序所占用的资源看作一个网络节点。
边集合E：目前产品制造过程有两个维度：一个是工序之间的冲突；一个是资源之间的冲突。为清晰显示资源节点之间的连接关系，首先需要对网络模态进行降维处理，完成二维网向一维网的投影，即工序层向资源层的映射。连边规则如下：
(1)同一个任务的工序一般存在时间上的约束，因此，同一个任务中的不同工序一般不可以同时进行加工。在这种情况下，这个任务的工序所对应的所有资源构成一个完全连通子图。而且在一些情况下，工艺过程的不可逆则导致的节点连边具有一定的方向性，网络图转化为有向网络，如图1。
(2)不同任务的不同工序之间常常会出现抢占同一个资源的情况，在这种情况下则将该资源加入每一个单一任务所对应资源的完全连通图，同样，若存在工艺过程的前后时序关系，则该图转为有向图，如图1。
不同任务的工序之间可能完全没有联系，也可能有比较少的联系，这取决于工序资源是否存在冲突。这样，所有任务和资源之间的对应合作关系就可以看作许多资源构成的网络图。图1a是用来描述这种关系网的双粒子图，图中二层顶点(T顶点)表示工序，底层顶点(R顶点)表示资源。当一项工序需要占用不同的资源时，它们之间都连接一条边，同时两个资源之间也连接一条如图1b所示的边。
图1 工序-资源映射
权重集合W不同的边一般权值不同，权值的大小用资源协作关系的紧密程度来衡量。Wij对应资源承担的第i个任务的第j个工序的工时负载。
这样，将节点集合V和边集合E组合成一个多任务复杂加权网络，其复杂性表现在节点边的数量多以及权重的变化。
2.2产品制造过程加权网络特性定义
(1)节点度
(1)
其中，ki称为节点i的度，aij表示节点i与节点j是否连边，若节点i与节点j之间有业务协作，则aij=1，反之，aij=0。在制造网络中表示有多少上下游资源节点被直接连接到所观察的资源节点。
(2)网络平均路径长度
(2)
其中，dij定义为连接节点i和节点j的最短路径的边数。N表示网络节点数。
(3)网络聚类系数
(3)
其中，ki表示与节点i有连边的节点的数目，Ei表示与i节点的邻居节点有关系的数目。
3 产品制造过程拓扑演化模型
在实际的产品制造过程加权网络演变过程中，资源和资源之间的联系会不断地改变，资源之间连接的权重也在不断发生变化。当资源节点承担的加工任务完成时，该资源节点就会自动退出。但是也有受不确定因素的影响，如设备故障导致节点退出。因此网络在演化过程中，边的权值、节点之间的连接关系、节点的数量等应该是不断动态变化的。
3.1网络演化模型的建立
(1)在某一时刻，新任务的到达，新节点(设备)加入到复杂产品制造过程网络中，新节点与已经存在的节点有任务关系，因而与已存在的节点连边。新节点偏好连接“度值大”的节点(服务质量高的节点)。连接偏好概率为：
(4)
式中ki表示节点i的度，i∈(1,n)。
(2)在某一时刻，由于任务的完成或突发资源故障，可能会有单个或多个老节点(设备)出现运作停止现象。在网络形式上表现为退出复杂产品制造过程，在网络中节点与其它节点的协作关系也消失，所以将部分边从网络中去除。
(3)在某一时段，节点和边都是在不断发生变化的。我们从变压器生产行业统计数据中可知，在变压器生产过程中，边的增加数目要远大于边减少的数目。从现实的复杂产品制造过程网络看，网络节点的规模是不断随时间而增大。
(4)根据资源协作网络倾向于连接服务质量高的节点，在网络的演化过程中，服务质量好的资源节点一般有较大的几率与其它资源合作。如某些工艺路线的确定，导致资源合作关系的固定连接。有时资源可能会去选择效率低的资源进行合作，以此来减少在服务质量高的资源上的等待时间。实际上每一个资源都有一个服务能力上限，结合这个特性进行合理资源安排更显得尤为重要。
3.2度分布分析
初始节点个数为m0，初始节点的的连接方式为全连接。每隔一个时间点加入一个新的节点，可能在老节点间增加或者减少边，再对模型进行分析时认为时间t是连续的，用平均场理论分析。
Ki代表节点i的度，
网络中的平均度为：
(5)
利用连续性理论，把ki看成连续动力学函数。因此节点i的度ki可用以下的动力学方程近似：
(6)
(7)
根据上式可以计算节点i的度ki小于
(8)
其中ti表示时间的连续动力学函数，p(ki(t)<
ti的概率密度函数为：
代入式(8)得：
(9)
则度分布为：
(10)
其中γ=3+φ，服从指数为3+φ的幂律分布，有无标度网络的特性。
4 实例分析
以某变压器制造行业A车间数据集作为模型研究实例，该车间制造组织形式遵循Job Shop原则，所采集实验数据均为该企业车间MES系统真实反馈数据。在本文中选取一年的MES数据作为样本(这样的数据包含所有可能的季节性对制造带来的影响)。
该车间共有33个工作站Mi(i=1,2,…,33)，加工A，B，C和D四类典型零件，每天工作8h。表1所示为各个产品工艺路径所占用的资源及资源对应的标准处理时间；表2为每种产品每天的生产数量。
表1 工艺路线及处理时间
表2 产品制造数量
注：由于篇幅限制，在原始数据罗列时省去部分数据。
建立网络模型时，分别用“节点”和“边”来代替“设备”和“设备间的合作”。下面建立产品制造网络的动态演化算法。
步骤1：开始时刻t=0，由m0个节点构成全耦合网络。
步骤2：在各个时间间隔，生成一个[0,1]之间的随机数p1。
步骤3：每个时间间隔内，加入一个新的节点，利用轮赌法选择m个节点与之相连接。
步骤4：给定一个概率pp，若pp>p1，从网络中随机选取m1条边去除。表示该资源节点任务完成或发生故障，资源状态由工作状态变为停止状态。
步骤5：给定概率qq，若qq>p1，在网络中增加m2条边，新增边的一端随机选取一个节点，根据公式(4)选取边的另一端。即，选取偏好连接度大(节点服务能力好)的节点。
步骤6：返回步骤2，直到网络达到所需要的大小N为止。
上述算法中的参数m0和m是动态的增长，满足m 表3 模型参数设置 根据上面提出的演化算法模拟仿真，得出模型的度分布图2和强度分布图3。 仿真得出了数据可知，网络规模线性增长。图2中实线部分是p(k)～k-γ，γ=2.65时的曲线。可以看出，网络节点的度分布基本服从γ≈2.65的幂律分布，这与上述理论推导一致，说明模型仿真与BA无标度网络模型的特性相符。从网络规模增长过程来看，本模型度分布和强度分布都是递增的，但节点度最大值和强度最大值都被控制在一定范围内，和网络中的服务有限或者流量的阈值比较吻合，所以该模型比较真实的描述产品制造网络。 图2 产品制造过程网络度分布 图3 产品制造过程网络强度分布 初始时刻取参数m0=5，m=4，网络规模从200到1000逐级变化，仿真平均最短路径L和平均聚类系数C，与BA网络的网络参数相对比，数据如表3。 表4 两种模型的网络特性对比 注：C表示聚类系数；L表示最短路径长度 数据对比可以发现，本模型与BA无标度网络非常接近，平均最短路径都是呈增长趋势，平均聚类系数都是呈减小的趋势。通过仿真实验，发现演化模型所生成的网络是具有行业特色的无标度网络。通过与无标度网络特征进行比较，证明所构建的演化模型能较好地刻画现实网络的演化机理。 基于复杂网络理论提出产品制造过程网络演化模型在一定程度上反映了真实网络的演化机制，刻画了复杂产品制造过程网络的形成和演化机理，证明所构建的演化模型能较好地刻画现实网络的演化机理。从理论推导和实验仿真证明了产品制造过程网络度分布具有无标度特性，这为揭示产品制造过程网络系统的内在演化机理提供了参考，本文的后续工作： (1)探讨复杂制造网络结构与功能的关系，清晰把握网络中各构成要素及其相互作用关系。 (2)研究产品制造网络过程的鲁棒性和抗打击能力为复杂产品制造过程调度建立依据。 [1] WANG Keqiang, ZENG Zhaofeng, SUN Dongchuan. Structure analysis of supply chain networks based on complex network theory[C]//Proceedings of the 4th International Conference on Semantics, Knowledge and Grid. Washington, D.C,USA: IEEE Computer Society, 2008:493-494. [2] 祖旭,黄洪钟,周峰，等.产品制造过程资源管理及其仿真[J].系统仿真学报,2005,17(6) :1322-1325. [3] 安波,廖文，郭宇,等.扩散制造任务建模及分解方法[J].南京航空航天大学学报,2010,42(6):731-734. [4] 房亚东,杜来红,何卫平,等.快速扩散制造环境下制造资源选择技术研究[J].计算机集成制造系统,2009,15(3):515-521. [5] 刘骄剑,廖文和,郭宇,等.基于复杂网络的扩散制造知识评价与关联分析[J].计算机集成制造系统,2012,18(10): 2204-2210. [6] 汪涛,吴琳丽.基于复杂网络的城市公交网络抗毁性分析[J].计算机应用研究,2010,27(11):4084-4086. [7] 杨宏伟,张勇,王焕坤,等.基于负载流的点加权复杂网络节点重要性评估方法研究[J].计算机应用研究,2013,30(1): 137-137. [8] 谌炎辉,赵辉煌,陈岳坪,等.复杂网络在制造业中的应用分析[J].机械设计与制造,2010(8):267-268. [9] 王岳淼,李小宁,刘德仿,等. 基于知识工程的复杂产品智能配置系统研究[J]. 组合机床与自动化加工技术,2014(2):154-156,160. [10] 徐赐军,李爱平,冯大鹏. 资源受限的复杂产品开发过程规划平台[J]. 组合机床与自动化加工技术,2014(9):153-156,160. (编辑李秀敏) Network Modeling and Evolutionary Analysis of Complex Product Manufacturing Process LI Hua-hua, YUAN Yi-ping,LI Xiao-juan,TIAN Shu-guang (School of Mechanical Engineering, Xinjiang University, Urumqi 830047,China) In view of integration, complexity, dynamics and distribution of the products manufacturing process, the algorithm to generate network model of the products manufacturing process is proposed after analyzing structural characteristics of the products manufacturing process network and evolution rule with complex network theory. Aiming at model growth, the algorithm considers the dynamic evolution of the internal points and edges, the dynamic evolution model is established based on the algorithm, and the distribution features of the products manufacturing process network is deduced. Finally, through the simulation anslysis on the complex mechanical and electrical products manufacturing process network, the scale-free properties of the complex product manufacturing process network is showed. product manufacturing network; complex product; dynamic evolution; scale-free 1001-2265(2016)08-0001-04 10.13462/j.cnki.mmtamt.2016.08.001 2015-10-26； 2015-11-27 国家自然科学基金(51365054)；新疆维吾尔自治区自然科学基金(2014211A008)；新疆维吾尔自治区科技厅“十二五”重大专项(201130110-1) 李华华(1989—)，男，湖南耒阳人，新疆大学硕士研究生，研究方向为复杂生产系统建模与仿真、优化控制，(E-mail)a1154290709@163.com；通讯作者：袁逸萍(1973—)，女，乌鲁木齐人，新疆大学教授，博士，研究方向为计算机集成制造、工业工程，(E-mail)yipingyuan@163.com。 TH166；TG506 A
5 结论
