生产网络多瓶颈识别与资源优化配置

研究内容

复杂制造网络

复杂网络

复杂网络引入制造业的研究进展

特征

知识点扫盲

定义

自相似

自组织

无标度

吸引子

小世界

1998年6月在Nature杂志上发表的题为《“小世界”网络的集体动力学》(Collective Dynamics of ‘Small-World’ Networks)的文章

1999年10月在Science杂志上发表的题为《随机网络中标度的涌现》(Emergence of Scaling in Random Networks)的文章

把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质,相应的结构叫做网络的拓扑结构。

click to edit

click to edit

click to edit

研究现状

刘涛等[6]从平均路径长度、聚集系数、度分布等复杂网络的统计性质,小世界网络和无标度网络等网络模型等层面简述了复杂网络领域的相关研究

史定华[7]从对网络节点度和度分布的理解入手,对网络分类、网络的演化机理和模型及结构涌现等方面取得的进展进行了总结

周涛等(2005)围绕小世界效应和无标度特性等复杂网络的统计特征及复杂网络上的物理过程等问题,概述了复杂网络的研究进展。

吴金闪等[5]从统计物理学的角度总结了复杂网络的主要研究结果,对无向网络、有向网络和加权网络等三种不同网络统计性质研究的现状分别作了综述,对规则网络、完全随机网络、小世界网络和无标度网络等网络机制模型进行了总结,并对网络演化的统计规律、网络上的动力学性质的研究进行了概括。

国内学者对国外复杂网络理论研究的介绍最早始于汪小帆(2002)发表在国外杂志上的一篇文章[3],文中回顾了近年来国外复杂网络研究所取得的重要成果,其中包括平均路径长度、聚集系数、度分布等网络度量,Internet、www和科学合作网络等现实系统,规则网络、随机网络、小世界网络、无标度网络等网络模型,以及复杂网络上的同步等。

统计特征

度及度分布


在网络中,点的度是指与该节点相邻的节点的数目,即连接该节点的边的数目。而网络的度<k>指网络中所有节点度的平均值。度分布P(k)指网络中一个任意选择的节点,它的度恰好为k的概率。

介数


包括节点介数和边介数。节点介数指网络中所有最短路径中经过该节点的数量比例,边介数则指网络中所有最短路径中经过该边的数量比例。介数反映了相应的节点或边在整个网络中的作用和影响力。

聚集系数C


在网络中,节点的聚集系数是指与该节点相邻的所有节点之间连边的数目占这些相邻节点之间最大可能连边数目的比例。而网络的聚集系数则是指网络中所有节点聚集系数的平均值,它表明网络中节点的聚集情况即网络的聚集性,也就是说同一个节点的两个相邻节点仍然是相邻节点的概率有多大,它反映了网络的局部特性。

小世界效应


复杂网络的小世界效应是指尽管网络的规模很大(网络节点数目N很大),但是两个节点之间的距离比我们想象的要小得多。也就是网络的平均路径长度L随网络的规模呈对数增长,即L~In N。大量的实证研究表明,真实网络几乎都具有小世界效应。

平均路径长度L


在网络中,两点之间的距离为连接两点的最短路径上所包含的边的数目。网络的平均路径长度指网络中所有节点对的平均距离,它表明网络中节点间的分离程度,反映了网络的全局特性。不同的网络结构可赋予L不同的含义。如在疾病传播模型中L可定义为疾病传播时间,通网络模型中L可定义为站点之间的距离等。

无标度特性


对于随机网络和规则网络,度分布区间非常狭窄,大多数节点都集中在节点度均值<k>的附近,说明节点具有同质性,因此<k>可以被看作是节点度的一个特征标度。而在节点度服从幂律分布的网络中,大多数节点的度都很小,而少数节点的度很大,说明节点具有异质性,这时特征标度消失。这种节点度的幂律分布为网络的无标度特性。


网络模型

作为从完全规则网络向完全随机网络的过渡,Watts和Strogtz于1998年引入了一个小世界网络模型,称为WS小世界模型。

很多网络(包括Internet和新陈代谢网络等)都不同程度拥有如下共同特性:大部分节点只有少数几个链接,而某些节点却拥有与其他节点的大量链接,表现在度分布上就是具有幂律形式,即P(k)~k—γ。这些具有大量链接的节点称为“集散节点”,所拥有的链接数可能高达几百、几千甚至几百万。包含这种集散节点的网络,由于网络节点的度没有明显的特征长度,故称为无标度网络。

如按纯粹的随机方式连线,所得的网络称为随机网络。

自相似是相似中的一种特殊情况,它是指系统的部分和整体之间具有某种相似性,这种相似性不是两个无关事物间的偶然近似,而是在系统中必然出现并始终保持的。这种自相似是层次复杂网络共有的拓扑性质,而自相似又是分型的一个基本特征,所以复杂系统与各层次子系统之间的自相似性,可以利用分形加以描述。

规则网络


最简单的网络模型为规则网络,它是指系统中各元素之间的关系可以用一些规则的结构表示,也就是说网络中任意两个节点之间的联系遵循既定的规则,通常每个节点的近邻数目都相同。常见的具有规则拓扑结构的网络包括全局耦合网络(也称为完全图)、最近邻耦合网络和星型耦合网络。

click to edit

制造系统网络特性

诸多制造网络均具有大的聚类系数和较小的最短路径,呈现明显的小世界特性

动态代理的演化建模研究结果表明:分形制造系统动态研究的驱动机制是系统的自组织行为

制造系统具有吸引子现象,当系统参数发生变化时,其动力学行为会改变,可能产生混沌现象。

离散加工业等网络的拓扑结构满足幂率,是典型的无标度网络。

将复杂加权网络理论引入到移动协同空间的描述与分析中,构建了移动协同网络,并在此基础之上进行了拓扑特性分析。

将复杂网络理论引入到分布式复杂机电系统脆性分析中,提出了基于网络结构的脆性分析方法

利用复杂网络理论进行区域协同制造资源网络构建,为区域协同制造中关键资源的发现及其统计提供了新方法。

将复杂网络理论用于动态物流网络异常检测

建立工业企业物流网络模型,并进行失效分析

将复杂网络用于离散制造企业的组织结构设计问题研究,提出了一种新的自组织方法

对制造企业协同生产网络进行建模分析,揭示了该网络脆弱性的演变规律

对产品族建模分析,证明了该产品族具有小世界和无标度的显著特点

利用复杂网络研究瓶颈多态性

复杂制造系统动态演化模型

瓶颈

瓶颈预测方法

通过放松调度问题机器的唯一性占用约束得到新优化模型,提出了基于约束转换的先验瓶颈识别方法,但属于复杂组合优化问题,难求解,不适用于大规模调度

对瓶颈等级划分以实现瓶颈漂移的预测

设计正交试验来预测,但是其结果依赖正交表,对多机器的瓶颈识别问题不适用

利用数学分析方法和仿真技术研究瓶颈问题

click to edit

瓶颈的识别方法

将制造单元生产能力和生产需求进行度量,在此基础上提出瓶颈识别方法

ROSER【72】等将设备持续活性时间作为识别离散加工系统的瞬时瓶颈和平均瓶颈的指标

综合设备生产率、利用率和质量效率三者,并将其联合作为系统瓶颈识别的指标

使用设备运行过程中的历史数据,利用数据驱动方法找出期阻塞和饥饿 “拐点”,进行瓶颈识别

if-then 评判规则进行瓶颈识别

采用启发式规则进行在线瓶颈的动态识别研究。

基于鼓-缓冲器-绳子理论的系统层瓶颈的计算方法,包含瓶颈识别

提出了基于聚类与多属性决策的作业车间瓶颈簇识别方法

利用遗传算法进行调度过程中得瓶颈识别。提出最大出现频率BPM的即为系统瓶颈

将排队平均加工队列等待时间最长的设备定义为瓶颈

提出设备瓶颈度的概念来预测瓶颈

利用瓶颈指数,建立综合瓶颈度和独立瓶颈度指标,通过度量各个制造单元成为瓶颈的能力,实现多瓶颈的动态识别

将物料流瓶颈指数用于表征制造单元阻碍制造车间物料
流流动平顺性的程度的指标,并进行了敏感度分析

提出瓶颈度及瓶颈指数这一动
态指标,以全面衡量各个制造单元成为瓶颈的能力,
进而实现瓶颈的动态预测。但瓶颈指数的每次计算都需要统计分析大量的历史数据,操作难度大,,当系统出现多个瓶颈时,主次瓶颈不能得到有效识别

企业级物流关系供需网络研究结果表明,自相似是制造系统关联
耦合关系的具体特征

复杂制造网络的生成

将复杂生产系统看作是由各种基本单元(如各种设备、装置、子系统等)通过各种物理上的管路、线路或者逻辑上的工艺、物流连接而成,则这些基本单元之间的相互作用关系实际上就构成了一种网络结构

结构复杂性研究

节点连边变化

节点连边间相互作用

网络节点变化

网络中资源数目的增减

资源节点自身能力的扩展

资源间耦合关系的变化

耦合强度的增减

制造系统的网络化特性研究(主要使用图论建模的方法)

click to edit

click to edit

排队论网络模型

析取图模型

将加工任务分解为具有逻辑关系的事件,每个事件为一个节点,事件之间有先后时序约束,事件之间冲突的资源为连边,构建有向网络模型。调度目标转化为求解任务子图的最长路径最短问题使得最大完工时间最小

单个加工资源为节点,资源之间相互协作关系为连边,若存在前后时序的约束,则生产过程就可以描述为一个加权有向图。资源节点上的任务的堆积视为该资源上的队列,这在一定程度上使得任务调度问题转化为网络模型上的队列描述问题。