基于复杂网络理论的离散制造车间生产物流网络建模与分析

尹 超，高 玲，李孝斌

(重庆大学 机械传动国家重点实验室，重庆 400030)

0 引言

离散制造车间布局复杂、物料种类和工序繁多、生产扰动层出不穷，致使车间生产物流难以高效、稳定的运行。据统计，在广大离散制造车间运行过程中，生产物流业务占车间整体运行周期的95%左右[1]，其优化运行水平对企业生产效率和生产成本起至关重要的作用。然而，目前离散制造车间生产物流运行环节普遍存在调度不精确、运输成本高、物料积压频发、物流线路混乱等问题[2-3]。在生产信息高度集成和生产精益化、智能化、协同化需求不断提升的背景下，如何改善现有离散制造车间生产物流业务的运行效率，已经成为广大离散制造企业亟需解决的重点难题之一。

目前，国内外学者已对生产物流系统展开了一定的研究。例如，李春玲[4]基于多色图理论对离散制造企业生产物流系统进行建模，明确了系统内部各元素间及元素与系统整体间的关联关系，并通过Flexsim对所建模型进行了实例仿真；张富强等[5]针对离散型制造车间中存在的混流排程计划与多任务执行脱离的问题，构建了一种加权赋值有向型车间工序物流动态网络的拓扑构型，分析了车间工序物流运行状态；赵业清等[6]建立了一种钢铁企业生产物流系统复杂网络模型，分析了网络特征参数，并指出生产过程中存在的问题及改进方法；李晔等[7]为解决车间生产运输托辊效率低下的问题，利用Petri网对托辊生产物流系统进行建模，精确描述了系统所涉及的时间相互关系，并通过Witness仿真对瓶颈设备及其工艺进行了优化；Wang等[8]为了较好地描述物流网络中节点的异构性、多维性和动态性，基于可拓理论和复杂系统理论，提出一种基于物元节点、关系元节点和事件元节点的物流网络模型；Negri等[9]构建了基于本体的生产物流模型，提出内部物流要素的层次关系结构，并开展了实例验证；此类研究还包括文献[10-12]等。

以上研究虽然在一定程度上改进了车间生产物流业务的运行效率，但是存在以下3点不足：①在生产物流网络动态性、不确定性方面考量不足，缺乏车间紧急插单、设备故障、物料供应等不确定性生产扰动因素对离散制造车间生产物流网络(Discrete Manufacturing Workshop Production Logistics Network, DMWPLN)演化结果的分析；②未能在车间整体层面上把控DMWPLN性能，难以实现车间生产物流的全局最优；③未能很好地将物流时间融入模型，对时间的分析不够明确，难以体现时间的重要性。因此本文采用复杂网络理论[13-17]对DMWPLN进行建模和性能分析，将紧急插单、设备故障、物料供应等不确定性生产扰动因素和时间融入DMWPLN的性能指标，从全局角度分析DMWPLN，对改善DMWPLN的稳定性、自修复能力，以及识别DMWPLN重要节点效果显著，能为DMWPLN的实时优化和生产调度的合理性提供支撑和依据，达到生产物流和生产调度的最优平衡。

1 离散制造车间生产物流网络建模

1.1 模型构建

本文建立的DMWPLN模型前提条件如下：

(1)以制造执行系统(Manufacturing Execution System, MES)生产调度中同一生产任务所涉及物料流经的物流节点形成的有向路线为DMWPLN结构最基本的单元，同一时刻多个基本单元组合形成DMWPLN。每个基本单元的起点和终点均为车间存储单元，中间节点为各工位。

(2)模型基于同一网络场景构建。网络场景指车间内所有已下达的生产任务所形成的物流网络。而同一网络场景指生产物流网络内物流节点的可用性和任务集合均保持不变时所维持的网络。若网络场景变化，则模型需重新构建。

基于复杂网络理论，本文将DMWPLN模型抽象为一个带时间窗的双权重有向复杂网络G(V,E,W,T)，其各元素集合的具体含义如下：

(1)集合V={1V,2V}，由工位和存储单元两类节点组成。

1V={1vi1|i1=1,2,…,n1}表示n1个可正常工作的工位集合，1vi1由静态信息和动态信息组成，即1vi1={1vi1_StaticInfo,1vi1_DynamicInfo},1vi1_StaticInfo={1vi1_BaseInfo,1vi1_FuctionInfo},1vi1_DynamicInfo={1vi1_StateInfo,1vi1_TaskInfo}。其中：

1vi1_BaseInfo为工位节点的基本信息，包括工位编码、工位名称、工位位置等。

1vi1_FuctionInfo为工位节点的功能信息，包括工位工作类型、可加工材料、在制品最大可存储容量等。

1vi1_StateInfo为工位节点的状态信息，包括闲置、未饱和、饱和状态、过饱和状态。

1vi1_TaskInfo为工位节点的任务信息，由一个有序集合组成{Task1→Task2→…}，表示该网络场景下该节点需执行的任务和执行顺序。各节点任务的描述信息包括任务编号、任务名称、任务流经的节点、任务到达该节点的时间、任务离开该节点的时间等。根据任务描述信息可以获知某物料在该工位的加工时间。一个工位节点的任务集合若为∅，则表示该节点处于闲置状态。

2V={2vi2|i2=n1+1,n1+2,…,n1+n2}表示n2个车间存储单元。同理，2vi2可由静态信息和动态信息组成，即2vi2={2vi2_StaticInfo,2vi2_DynamicInfo},2vi2_StaticInfo={2vi2_BaseInfo},2vi2_DynamicInfo={2vi2_StateInfo,2vi2_StorageInfo}。其中：

2vi2_BaseInfo为存储单元节点的基本信息，包括存储单元编码、存储单元名称、存储单元位置等；

2vi2_StateInfo为存储单元节点的状态信息，包括闲置、未饱和、饱和状态；

2vi2_StorageInfo为存储单元节点的存储信息，包括该节点存储的物料编码、各物料数量、剩余存储容量等。

(2)有向边集合

式中ei1j1，ei1i2，ei2i1的物理意义分别为工位间的物料流、工位和存储单元间的物料流；网络拓扑含义为节点1vi1指向节点1vj1、节点1vi1指向节点2vi2、节点2vi2指向节点1vi1的有向边。物料流一般由自动导引小车(Automated Guided Vehicle, AGV)、机械手等实体运行形成。若节点间有物料流，则两节点的连边值为1，否则为0。为了便于描述节点，以有向边为基准定义流出节点和流入节点，如图1所示。

(3)权重W={1w,2w}，由一类权重1w和二类权重2w组成，即双权重。本文将权重值赋予有向边来体现各边之间的差异，以更全面地反映生产物流的实际情况。

1w=

表示物料在节点的占用时间，在一定程度上反映了该边的重要性。各元素值为流出节点被物料占用的时间之和。一类权重为相似权重，其值越大，该边越重要。特别地，物料在存储单元节点的占用时间对本文模型没有意义，但为了保证各边均有权重值，本文视物料在存储单元节点的占用时间为0.01 h，即1wi2i1=0.01。

2w=

表示节点间物料流动的时间间隔，反映节点间物料的平均流动效率。各元素值为不同生产任务下的物料在流出节点和流入节点间流动的时间间隔平均值。二类权重为相异权重，其值越大，该边的物流平均流动效率越低。

模型的邻接矩阵与权重对应，可表示为：

(2)

在离散制造车间中，物料不会在某节点完成任务后再流向该节点，即节点不会形成自环路。因此，邻接矩阵对角线的值恒为零。

(4)时间区间T反映了DMWPLN模型所囊括的时间范围，表示为T=[TES,TLF]，其中：TES为DMWPLN中所有任务的最早开始时间，TLF为DMWPLN中所有任务的最迟完成时间，TES和TLF随着任务的完成与下达而改变。

整个网络模型的生成过程如图2所示。

1.2 动态演化驱动因素

离散制造车间生产过程中的工位、任务和物料具有动态不确定性，会使DMWPLN场景发生变化，进而影响生产物流的运行效率。因此需要分析DMWPLN的动态演化驱动因素，为网络的重构、演化及性能分析提供判据。影响DMWPLN模型动态演化的因素分析如下：

(1)工位加入 工位的加入来源于两部分，一是故障设备维修后重新接入生产网络模型；二是企业新增设备后接入生产网络模型，表示该车间的生产物流网络有新工位加入，应增加相应的网络节点。

(2)工位退出 工位设备故障而不能继续完成所承担的任务，因而节点失效，需从DMWPLN模型中删除。

(3)任务变更 车间是一个不确定的环境，其生产任务时常受到设备故障、紧急插单等因素影响而调整生产计划、工艺路线等，其变更方式包括生产任务取消、紧急订单插入等。

(4)物料供应不足 由于物料供应不及时导致工位空闲等待，使任务无法正常进行。

(5)任务正常下达 由于车间维持较高的利用率，会在相对固定的一段时间段内下达新的任务。

(6)任务完成 物料经过一系列加工后形成成品，表示该任务已完成，释放其相应节点。

上述因素对DMWPLN模型的具体演化形式主要体现在对模型节点、连边、边权和时间区间的影响程度，具体如表1所示。

表1 动态演化驱动因素的演化形式

由表1可知，生产任务的正常下达、完成属于物流网络正常演化范畴，反映了网络的更新速度，同时反映了车间生产周期；其他演化驱动因素由外部干扰造成，属于非正常演化，应尽量避免。DMWPLN演化模型如图3所示。

2 离散制造车间生产物流网络特征

为进一步分析所建立模型的本质特性，需对其网络特征进行分析。根据DMWPLN的特点，本文对DMWPLN模型的度及其分布、相关性、负载均衡度、节点平衡性等特征进行研究。

2.1 度及其分布

在DMWPLN模型中，节点的度k有出度kout和入度kin之分。kin为其他节点流入该节点的边数，其物理意义表示节点的容纳对象范围；kout为该节点流入其他节点的边数，其物理意义表示节点的能力影响范围。节点的度表示为：

(3)

(4)

k(1vi1)=kin(1vi1)+kout(1vi1)，

k(2vi2)=kin(2vi2)+kout(2vi2)。

(5)

其中度为0的节点为孤立节点，表示在该网络场景下，该节点一直处于闲置状态。除生产物流起点和终点外，度值较高的物流节点往往是一些柔性较高的工位，这些工位在车间生产物流过程中更加重要。

度的分布用节点度的分布函数P(k)表示，物理意义为在网络中任一节点的度为k的概率。度的分布体现了车间生产物流所呈现的网络特性以及度值分布的均衡性。

(6)

(7)

(8)

式中：P(kout)为出度分布，P(kin)为入度分布。

点强度是度的推广，是边权和度的结合，分为出强度和入强度。出强度指该节点出边的权重之和，入强度指该节点入边的权重之和，映射到邻接矩阵1A，2A，分别为对角线所在行、列中各数值之和。因此出、入强度也有一类出、入强度1sout，1sin和二类出、入强度2sout，2sin。由邻接矩阵的定义可知，1sout表示节点承担的任务量，1sin表示指向该节点所承担的任务量之和；2sout，2sin则需转换为二类单位出强度2uout，2uin，其物理意义为节点间的物料平均流动效率。

(12)

因为点强度的值各不相同，所以点强度分布为各节点的点强度值在二维坐标上的点。P(1sout)能更好地体现车间工位的负载分布，P(2uout)能体现工位之间的物料流动效率分布。

2.2 相关性

为了分析DMWPLN中以工位为基准的物流连接倾向性，论文对DMWPLN的权—度相关性、度—度相关性，以及点权—点权相关性进行了分析。

参考文献[18]，论文设计了有向无权的最近邻平均度knn,i1、有向加权网络的一类最近邻平均度1kw_nn,i1、二类最近邻平均度2kw_nn,i1对DMWPLN的权—度相关性进行分析描述，即：

(15)

式中kout(vj1)为节点vj1的出度。对任一节点，若1kw_nn,i1>knn,i1，则表示任务负载较大的边倾向于与能力影响范围广的节点相连；若1kw_nn,i1knn,i1，则表示物料流动效率大的边倾向于与能力影响范围广的节点相连；若2kw_nn,i1

DMWPLN的度—度相关性则参考文献[19]中的Pearson相关系数γ1，用式(16)进行判断：

γ1=

(16)

DMWPLN的权—权相关性则参考度—度相关性的评判方法，给出如下Pearson相关系数γ2和γ3进行判断：

(17)

(18)

2.3 负载均衡度

负载均衡度体现了车间生产过程中工位各自利用率的差别，负载均衡度越低，车间生产安排越合理[19]。节点负载均衡度LB以1sout为基础进行衡量，

(19)

2.4 节点平衡性

节点平衡性指各节点流入物料效率与流出物料效率间的差异。节点间的物料流动差异性越大，节点间的平衡性越差，说明该节点应为重点关注节点。节点平衡性定义为：

(20)

在实际DMWPLN中，节点的平衡性越小，物料流动的流畅性越好。

3 离散制造车间生产物流网络性能分析

3.1 节点重要性分析

上述分析的度、相关性、负载均衡度及节点平衡性等DMWPLN网络特征，仅从单一的角度体现了节点的重要性，未整体考虑以上网络特征对节点重要性的评价。因此本文基于复杂网络重要性评价方法[20-24]，建立了一个包括度、一类出强度和节点平衡性的多属性决策方法，以对DMWPLN的节点重要性进行评价。

为便于书写，分别用f1，f2，f3表示k(1vi1)，1sout(1vi1)，NB(1vi1)。本文采用基于线性加权的DMWPLN多属性决策方法，其权重决定了整个函数的最优值，也决定了该综合评价指标的优劣。为此，本文采用变异系数法确定各指标的权重，其变异系数为

(21)

因此，各指标的权重为

(22)

因为本文的各指标均为正向指标，指标值越大表示该节点越重要，所以采用线性比例变换法可将各指标进行标准化处理为

(23)

因此节点1vi1重要性评价可可表示为

(24)

利用式(24)对DMWPLN各节点的重要性进行排序，重要性越大的节点(即为关键节点)，在生产物流系统运行过程中越需重点关注，应对其进行合理优化。

3.2 稳定性分析

DMWPLN的稳定性是衡量一个车间生产调度合理性的重要指标之一，该指标能够较好地反应其抵御非正常演化的能力。因此，本文结合信息熵理论定义系统的稳定性，即

(25)

式中：pq为与表1对应的各非正常演化驱动因素发生的概率；ψ为DMWPLN的均衡度，即网络节点的重要性偏差程度，用于反映抗演化能力。

(26)

3.3 自修复能力分析

自修复能力体现了遭受非正常演化时DMWPLN的应对能力。本文基于节点一类出强度对DMWPLN的自修复能力进行量化和分析。先将网络模型中的工位按功能进行能力划分，共有a种，每个集合中的元素有bak个，则各工位的自修复能力可表示为

(27)

因此DMWPLN的自修复能力可表示为

(28)

R越大，DMWPLN的自修复能力越强，表示该网络场景下的工位利用率越低。因此，为保证企业利益，应在DMWPLN有一定自修复能力的前提下，尽量提高企业的工位利用率，使DMWPLN的整体效果最好。

4 实例应用

本文以重庆某企业的发动机箱体机加工车间的生产物流业务为例进行实例验证。该车间按订单模式生产，实行两班制，一次性下达1～4个订单的任务量(除紧急插单外)。该车间共有95台可正常工作的工位，6个车间存储单元，已下达未完成的任务共48个，部分任务信息如表2所示。根据表2建立发动机箱体机加车间生产物流网络模型G(V,E,W,T)，其中：V={1V,2V}={1vi1,2vi2|i1=1,…,95;i2=1,…,6}，n1=95，n2=6，共129条边，T=51.14。

表2 部分任务信息

4.1 网络特征

根据以上信息和1.1节方法建立复杂网络模型，其模型拓扑图如图4所示。

(1)度及其分布

根据式(3)～式(5)和式(9)～式(11)计算该车间生产物流网络模型节点的特征值，如表3所示，其度分布如图5和图6所示。

表3 网络特征值

从图5可以看出，无论是节点的出度、入度、度，其值大部分较小，因此该车间的生产物流网络近似为无标度网络。从图6a可见，工位被物料占用的时间分布范围很广，但呈区域分布，大致集中在20，28，40左右，主要因不同工位分配的任务不同导致。从图6b可见，相连节点间的物料流动频率大致分布在3个区域，多数节点分布在0.5左右，一部分分布在2左右，剩下的一部分分布在1.6左右。因此应充分保证物料流动效率较高节点间所涉及的AGV或机械手的可用性，确保物流运输效率，同时尽量缩短物料流动较慢节点间的时间，提高物料流动效率。

综上可知，一类出强度和二类单位出强度的分布类型大致相同，主要由于该车间的生产物流网络由10条发动机箱体生产线组成，除存储单元节点外，生产线间不存在交叉，其中5条线均为同类型发动机箱体生产线。

(2)相关性

在分析发动机箱体机加车间生产物流网络模型的度和点强度的基础上，进一步分析该网络点与点之间、点与边之间的连接特点。

1)权—度相关性 由式(12)～式(14)计算可知，1kw_nn,i1=knn,i1，2kw_nn,i1=knn,i1，因此权重和节点的出度之间没有相关性，即任务负载大的边所连接的节点与该节点能力影响范围无关。

2)度—度相关性 由式(15)计算得γ1=-0.400 0，表示发动机箱体机加车间生产物流网络呈负相关，即出度值大的节点倾向于和入度值小的节点相连，说明能力影响范围大的节点更倾向于与容纳对象范围小的节点相连，符合车间实际情况。

3)权—权相关性 由式(16)和式(17)计算得γ2=0.419 0，γ3=0.290 6，表示发动机箱体机加车间生产物流网络为权—权正相关，说明物料流动快的工位节点倾向于和物料流动快的工位节点相连。

(3)负载均衡度

由式(19)计算得工位节点的负载均衡度LB=0.287 5，值较大，说明该车间各工位的负载差异较大，应重新调整该车间的任务，使工位负载均衡。

(4)节点平衡性

由式(20)得各工位节点的平衡性，如图7所示。可见，大部分节点的平衡性在0.2以下，节点的平衡性较好，节点物料流入流出差别较小；少部分节点的平衡性在0.35以上，节点物料流入流出差别较大，存在节点空闲等待，说明此时的生产线未能实现工位利用率最大化。

4.2 整体性能

(1)节点重要性

根据3.1节的方法和4.1节的计算结果得到度、一类出强度、节点平衡性对应的权重值分别为λ1=0.224 3，λ2=0.220 8，λ3=0.554 9，可知节点平衡性占据的比例最大，说明节点平衡性差异最大。各工位节点的重要性如图8所示。为了便于分析比较节点的重要性特征，本文列举了重要性前10的节点，如表4所示。

表4 重要性前10的节点

从表4可见，重要性最大的节点为1v45和1v54，是车间里不同线体的钻孔工位，因为当前网络场景下两个线体的布置情况和所承担的生产任务一样，所以其重要性一样，生产过程中需要重点关注这两个节点，加强物料运输管理。同理，根据节点重要性依次加强对重要性高的节点的关注，防止因节点处出现意外而导致车间物流发生阻塞。

从前10节点重要性各分指标的数值来看，分指标大的节点重要性不一定最大，验证了本文采用综合指标判定节点重要性的方法更优越。

(2)稳定性

根据车间的日常统计预测出的各非正常演化驱动因素发生的概率pq={0.003,0.003,0.01,0.01,0.004,0.08}，由式(25)和式(26)得ψ=0.177 7，D=0.089 7，说明DMWPLN的稳定性较好，其不易受外部因素干扰而发生较大变化，具有较强的抗干扰能力，同时反映该网络场景下的MES安排合理，车间性能较好。

(3)自修复

车间的工位划分为铣、钻、镗、磨、检漏、打标6类功能，用式(27)和式(28)计算各类功能的自修复能力和总修复能力，如表5所示。

表5 车间各类功能的自修复能力

从表5可见，自修复能力最强的是打标功能，可以承受4个工位的故障而不影响生产物流网络的整体进度，较符合车间实际情况。该车间生产物流网络的自修复能力较好，能很好地应对车间不确定因素的影响，从侧面反映了该车间生产任务安排不合理，导致工位在该网络场景下的利用率偏低。

综上所述，通过分析本文DMWPLN构建方法建立的重庆某发动机箱体机加工车间生产物流网络模型，得出如下结论：

(1)DMWPLN具有无标度网络特性，以及度负相关、权正相关的特点。

(2)该网络场景下，该车间的生产调度合理性一般，各工位的负载分配不均匀，物料流动效率符合该车间加工类型的特点。整体而言，车间生产物流网络在稳定性、和修复能力方面较好。

4.3 建模方法分析

Petri网是对离散事件的动态系统进行建模与分析的主要方法之一，现已有大量基于Petri网的生产物流系统建模方法的研究[7,12,25]。该方法与基于复杂网络理论的建模方法类似，均是将实际系统抽象为图论网络，但二者又有区别。为验证本文建模方法的优越性，本文与文献[7]基于Petri网的铁棍车间生产物流建模方法进行对比。将文献[7]的方法应用到本文实例中建立的模型如图9所示。图中：符号“〇”为存放资源的库所；“⊙”为托肯，用Pc表示，c为库所和托肯序号，c=1,2,…,196，其中P1～P95对应本文模型的1v1～1v95，P96～P101对应本文模型的2v96～2v101；“┃”为变迁，用td表示，d=1,2,…,125；“→”为库所到变迁的输入函数或变迁到库所的输出函数。与本文所提方法建立的模型(如图4)相比，基于Petri网构建的模型(如图9)比较复杂，当所需建模的车间生产工序或工位较多时，基于Petri网的建模方法容易出现维数灾难问题。

另外，分析图9和文献[7]可知，基于Petri网的建模方法可实时反映各工位的空闲率和占用率，并通过各工位的占用率判断生产平衡性和瓶颈工位(占有率大于90%)，这与本文所提建模方法中的度、出强度和负载均衡度所体现的物理意义类似，但本文方法还支持对DMWPLN的分布特性、各节点间的连接倾向性、整个网络稳定性和自修复能力等的分析。相对而言，可为车间生产物流的优化运行提供更全面的技术支撑。

综上所述，本文建模方法能够帮助决策者更好地了解车间生产物流网络的本质特性，为决策者的统筹优化提供更全面的基础支撑，因此更具优势。

5 结束语

本文结合复杂网络理论，对离散制造车间生产物流业务进行了网络模型构建与分析。建立了一种以工位和车间存储单元为节点、物流流动为边的带时间窗的双权重有向生产物流网络模型，分析了引起网络模型动态演化的6类驱动因素；研究了模型的部分关键网络特征，以及节点重要性、稳定性、自修复能力等性能，以此为任务合理分配、物流设备合理调度，以及改善车间物流运行效率提供依据。最后以重庆某发动机箱体机加工车间生产物流过程为例，得出：①在网络特征方面，该DMWPLN具有无标度网络的特性，呈度负相关、权正相关；②在网络性能方面，该车间负载分布不均衡，网络稳定性和自修复能力较好。研究成果为广大离散制造车间生产物流的优化运行提供了一定的技术支持，也为下一步课题组在车间生产物流网络性能优化、智能调度等方面的研究提供一定的基础理论支撑。