基于网络结构特征的作业车间瓶颈识别方法-李晓娟.pdf

《基于网络结构特征的作业车间瓶颈识别方法-李晓娟.pdf》由会员分享，可在线阅读，更多相关《基于网络结构特征的作业车间瓶颈识别方法-李晓娟.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第22卷第4期2 0 1 6年4月计算机集成制造系统Computer Integrated Manufacturing SystemsV0122 No4Apr2 0 1 6DOI：1013196jcims201604023基于网络结构特征的作业车间瓶颈识别方法李晓娟，袁逸萍+，孙文磊，冯欢欢(新疆大学机械工程学院，新疆乌鲁木齐830047)摘要：针对作业车间管理层面的瓶颈识别，从制造系统复杂性与复杂网络相结合这一全新视角，提出基于网络特性的制造瓶颈识别方法。根据设备工装、工艺路线、物流路径和产品配置等多层次生产数据，建立了作业车间网络模型。对瓶颈内涵进行了扩充，提出基于网络瓶颈效率矩阵的瓶颈识

2、别算法。综合考虑了网络结构、网络传播机制及节点自身特性的影响，利用节点的制造负载和节点间的网络瓶颈效率矩阵表征节点的瓶颈程度，克服了其他算法中瓶颈节点识别只依赖于邻接节点的不足。通过对某机电产品企业车间生产瓶颈的动态监控和预测，验证了该瓶颈识别方法的有效性和准确性，也表明制造系统的网络模型是实现制造系统快速评估的有效方法。关键词：复杂网络；作业车间；瓶颈贡献度；瓶颈识别中图分类号：THl66；TPl81 文献标识码：ABottleneck identification in job-shop based on network structure characteristicLI Xiaojua

3、n，YUAN Yiping+，SUN Wenlei，FENG Huanhuan(School of Mechanical Engineering，Xinjiang University，Urumq 830047，China)Abstract：Aiming at the bottleneck identification problem in joh-shop operation management of work station，a newWeb-based manufacturing bottleneck identification method was presented A jobs

4、hop network model was established according tO multiple levels of production data such as equipment and tooling，process route，logistics pathand product configurationBy expending bottleneck connotation，a bottleneck recognition method was proposedbased on efficiency of network bottlenecks matrixThe co

5、mprehensive evaluation of the proposed method was takeninto account combined with the network structure，network communication mechanisms and node self characteristicsFurthermore，the bottleneck index was characterized by using manufacturing load and network efficiency matrix，which overcame the defici

6、ency that the bottleneck node identifier depended only on the adjacent nodeAn example for dynamic monitoring and forecasting the bottleneck in a mechanical and electrical products plant job shopwas given tO prove the validation and practicability of bottleneckThe result showed that the network model

7、 of manufacturing system was an effective way tO achieve rapid manufacturing system assessmentKeywords：complex network；jobshop；bottleneck contribution；bottleneck identification0 引言作业车间是一个包含大量资源节点且节点间存在复杂相互作用、依赖关系的定常周期运动，其中存在一种更为普遍意义的形式，即无序的混沌。因此，作业车间资源优化配置(Job Shop Scheduling，JSP)是最困难的组合优化问题之一，而对最终性

8、能影响最大的就是瓶颈。因此，有效地辨识瓶颈并充分利用瓶颈，是资源优化配置的首要任务。针对瓶颈识别问题，众多学者进行了大量研究。POLLETT等13将具有最长平均等待时间的机器定义为系统的瓶颈；ROSER等瞳1使用设备持续活性时间进行离散事件系统的瞬时瓶颈和平均瓶颈识别；LI3使用在线数据驱动方法，找出机器在指定时期阻塞和饥饿出现的“拐点”以识别该时期的瓶颈；MUTHIAH等4将设备综合效率、机器质量效率收稿日期：2015-0227；修订日期：2015一1016。Received 27 Feb2015；accepted 16 Oct2015万方数据第4期 李晓娟等：基于网络结构特征的作业车间瓶颈

9、识别方法和机器理论生产率三个指标联合为综合产出率，将其作为系统瓶颈识别的综合指标；KASEMSET等51通过仿真方法获取机器利用率、机器加工利用因子、机器生产瓶颈率三个指标，并制定if-then评判规则进行瓶颈识别；王军强等61基于聚类思想及多属性决策理论提出作业车间瓶颈簇的识别方法，识别包含瓶颈资源的瓶颈簇。该类方法主要依据瓶颈设备的外部表现特征进行识别，属于瓶颈静态识别方法，该方法简单直观，但当系统处于饱和状态或者在多瓶颈工况下时，其识别的瓶颈并不一定是真正的瓶颈。翟颖妮等71针对大规模作业车间生产调度问题，以系统作业目标对各个机器调度方案变化的敏感度为指标，采用正交试验识别瓶颈设备；ZH

10、ANG等8提出一种基于模拟退火算法的瓶颈识别方法；王刚等9运用遗传算法将瓶颈识别和调度方案相结合，指出具有最大出现频率(Possible BettleneekMachine，PBM)的瓶颈即为系统瓶颈；Wang等10采用启发式派工规则为排队工件赋予优先级，动态在线调度瓶颈资源；乔非等1妇借鉴鼓一缓冲器一绳子理论，提出系统瓶颈及层瓶颈的计算方法。该类方法主要利用仿真和智能优化算法分析的优势进行瓶颈识别和调度优化，可操作性强，但是由于不同生产系统需要的仿真模型和算法不同，该类方法的推广受到一定的限制。RICHARD等口幻通过度量各制造单元能力和需求的大小，对瓶颈识别方法进行研究；WANG等133提

11、出设备瓶颈度的概念，以预测系统瓶颈；刘志等1胡利用瓶颈指数建立综合瓶颈度和独立瓶颈度指标，通过度量各个制造单元成为瓶颈的能力，实现多瓶颈的动态识别；凌琳等n朝提出将物料流瓶颈指数用于表征制造单元阻碍制造车间物料流流动平顺性程度的指标，并进行了敏感度分析；刘明周等163提出瓶颈度及瓶颈指数这一动态指标，以全面衡量各个制造单元成为瓶颈的能力，进而实现瓶颈的动态预测。该类方法主要是基于瓶颈度的预测方法，它从瓶颈产生的本因出发来预测系统瓶颈，克服了前两种方法存在的不足，但每次计算瓶颈指数都需要统计分析大量历史数据，从而使该方法的操作难度大，而且当系统出现多个瓶颈时，主次瓶颈并不总能得到有效的辨识。综上

12、所述，基于瓶颈的制造车间瓶颈识别方法在理论研究上取得了一定的成果，但随着产品多样性和产品复杂性的不断增加，制造系统生长尺度不断加大，各工作站节点之间耦合、互斥、关联等各类关系复杂，制造系统已经成为典型的大规模复杂系统，现有瓶颈识别方法在处理大量生产数据和制造信息随机性以及固有动态特性传播方面显得有些吃力。为了获得长期的生产决策支持，创造性地提出新的生产瓶颈研究思路和方法，已成为制造企业提高效益的迫切需求。复杂网络是研究复杂系统的一种角度和方法，它关注不同复杂系统的结构、功能及相互耦合关系，是理解复杂系统性质和功能的基础。作为分析复杂系统的有力工具和方法，复杂网络已广泛应用于不同类型的系统、研究

13、不同的问题，如社交网络1 7|、生物网络1引、社会网络1妇和交通网络2叩等。事实上，制造系统网络同其他网络一样具有复杂网络特性(如大量的资源节点、资源之间协作紧密等)。因此，利用复杂网络对制造系统的固有特性进行分析和研究是可行的21|。目前，将复杂网络应用于制造业进行相关基础研究才刚刚起步。Jiang等221运用复杂网络对流程工业中的物料流动进行失效分析；Vrabie等z32妇将复杂网络理论用于动态物流网络异常的检测，同时针对经典单元制造企业组织结构设计问题，提出制造系统网络自组织结构的新方法；Till Becker等25基于复杂网络理论建立了复杂制造系统演化模型；祁国宁等26以工业汽轮机产品

14、族为研究对象，建立了基于复杂机械产品族的零部件关系网络，证明了该网络的小世界特性和无标度特性，同时发现产品族网络具有分层、模块性等显著特点；张峰等271将复杂网络理论应用于协同生产网络组织的失效模式和脆弱性分析，解释了整体脆弱性与局部脆弱性的变化规律。虽然将复杂网络分析方法结合具体工业背景进行的研究近年来已崭露头角，但对于车间制造系统各构成要素及其相互作用关系，以及网络结构与配置变化对车间制造系统关键环节和优化过程的影响等方面的研究却仍进展艰难，其背后的科学问题及在生产调度优化中的作用有待进一步深入研究。因此，本文以作业车间为研究对象，首先根据设备工装、工艺路线、物流路径和产品配置等多个层次生

15、产数据，建立作业车间网络(JobShop Net，JSN)模型，在此基础上提取网络节点的特性值，提出综合万方数据计算机集成制造系统 第22卷考虑网络结构、网络传播机制和工作站节点自身属性的瓶颈度指标及瓶颈辨识方法，并以此为基础给出节点瓶颈度仿真过程并进行实例验证，进而实现作业车间瓶颈的连续预测，为求解复杂生产环境下生产调度优化问题提供新思路和新方法。1作业车间网络模型11问题描述作业车间安排h种共竹个零件在m台设备上加工，零件J。(i1，2，竹)依据给定工艺路线的一道或多道工序加工。其中：零件J。有O。道工序；瓯为零件J；的第-道工序；每道工序之间有工艺上的先后约束；各道工序所需要的生产资源和

16、加工时间已确定；T洳为第i个零件-，。的第_f道工序在设备r的标准加工时间。作业车间生产系统存在以下特点：(1)任务的随机性 作业车间的订单不可能一次性到达，通常是随机动态到达。(2)工艺约束的有向性 工艺过程的不可逆导Clr序流程1致设备、工装、质量控制点间存在的工艺路线、物流路径等具有一定的方向性。(3)制造资源负栽的动态性 由于不同订单任务的加工工艺不同，任务的开始时间不同，占用的资源不同，导致每台设备在不同时间段加工的零件不同，设备的制造负载也随之变化。(4)瓶颈识别的复杂性生产车间受外部需求和内部产能的综合影响，瓶颈数目和位置随作业车间系统时间和空间特性的变化而变化，即瓶颈会发生动态

17、漂移。因此，瓶颈识别具有复杂性和动态性。1。2作业车间网络描述若将作业车间系统中涉及的每一个工作站(设备、工装、质量控制点等)作为一个节点(后文所说节点均指工作站)，将节点间可能存在的工艺路线和物流路径作为边，则作业车间生产系统构成了一个多任务有向加权网络，如图1所示。任务的动态增减触发网络结构的变化，JSN模型是依据订单的任务分解所具有的共性特征进行建模的结果。G工序流程C工序流程月图l作业车间生产车间网络映射本文根据作业车间特征提出统一的数据集合，表达JSN的数据结构，使生产约束条件通过点、边和映射关系予以充分反映。模型中的参数分别表示节点数、连边数、节点负载、映射关系、订单属性、加工时间

18、和节点服务能力等，可按照需要简化网络，实现作业车间的网络化映射。在网络描述层面，节点之间的数据结构定义为JSNM一R，E，W，M(td)，U，L，QDS，。式中：R表示节点集合，R1，2，r，m)；E表示连边的集合；W，表示节点r的制造负载；M(td)万方数据第4期 李晓娟等：基于网络结构特征的作业车间瓶颈识别方法表示任务与节点的映射关系；U表示订单集合，【，一1，2，z)；T洳表示第i个零件Ji的第歹道工序在设备，的标准处理时间；QOS，表示节点，在额定工作时间内持续提供服务的能力，COS，一1一!堡娶翌!lOO。(1)上7式中：Qos，o，1；TEr，TC,，TO分别表示设备r由于设备故障

19、、更换工装卡具、加工质量三项问题引起的服务损失时间；T，为设备r每个工作日内的额定工作时间。基于上述定义，可显著简化网络复杂度、避免维数灾，极大地减少了后期网络数据计算量。2作业车间网络特性定义考虑到作业车间车间网络结构、网络传播机制和工作站节点的自身属性都会对瓶颈的产生带来影响，抽取节点度、介数、网络效率和制造负载四个具有代表性的参数识别瓶颈。其中：节点度和介数是网络结构局部特性评估的重要参数，可反映节点在SN中的重要度和中心性；网络效率是网络结构全局性能评估的重要参数，可反映任务驱动的事件在JSN中的耦合程度和传播机制对瓶颈的影响；制造负载是节点自身特性，可反映节点所承担的任务负荷的大小对

20、瓶颈的影响。具体定义如下：定义1节点度。人度：节点人度是指SN中有多少上游节点直接与该节点相连，如式(2)所示：D，一：口，i。 (2)j“i)式中：D了表示节点r的人度；口ii为节点r的上游节点汇人节点r的边数。出度：节点出度是指在JSN中有多少下游节点被直接连接到所观察的节点，如式(3)所示：D；“一：ad。 (3)J三乏)式中：D7表示节点r的出度；ni表示由节点r出发到邻居节点的边数。节点度值D(r)是该节点输入和输出的边数之和，是表征节点局部重要特征的指标之一。在SN中，节点的度值越高，意味着该节点参与的订单加工任务越多，该节点的利用率和重要性就越高。定义2介数。节点介数用于描述节点

21、r在整体网络中的中心性，如式(4)所示：RP空!型 f4) 篆rt8t 一j ug5，frEm式中：B，表示节点r的介数。B，o，1，节点r的中心性越高，其值越接近1。以为从节点s到节点t的所有最短路径的条数。鼠(r)为从节点S到节点t经过节点r的所有最短路径的条数。在JSN中，最短路径是指物料流流经频率较高的路径。节点的介数值越高，表示订单加工任务流经该节点的概率越大，当网络结构含有随机变化因素时该指标尤为重要。类似节点度，介数不仅量化了各个工作站在作业车间中的中心性，而且更加强调节点与非邻居节点的总体连接水平。定义3网络效率。网络效率&(sm，tE仇)指任意两个节点(S，)之间的距离(节点

22、间的最短连边数目)的倒数，即岛一1d。在JSN中，网络效率可以表征两个加工事件的耦合程度，距离越大，耦合越小。网络效率是节点间相互作用最直接、最有效的表现形式。因此，具有m个节点的JSN效率矩阵可表示为：E= (5)定义4节点负载。节点负载是指所有待处理的零件占用第r个工作站的时间总和与节点r额定工作时间的比值，如式(6)所示：h NfqiA沙Td，Wr一旦弓莳。(6)式中：W，表示节点r的负荷情况，q。为零件，i的数量；N，为零件-，。的处理次数；Ad，为设备系数，若零件J。的第歹道工序可以在工作站r上完成，则A，一1，反之A驴一0；QoS，为节点r的服务能力；T，为设备r每个工作日内的额定

23、工作时间。3作业车间瓶颈度分析基于复杂网络视角研究，从直观上看，若一个节点的度值越大，则该节点在整体网络运作中的作用越大。但在JSN中仅凭度值大小很难判断节点的瓶颈程度，因为忽略了那些在网络中起桥梁作用但是度值很小的节点，即桥连接节点2 8|。实际上，若SN中存在非工艺衔接的工作站节万方数据计算机集成制造系统 第22卷点之间的彼此依赖程度显著高于工艺相依的邻接节点，则该非邻接工作站节点之间的相互依赖不容忽视。因此，将瓶颈的内涵扩充为：定义5瓶颈指在作业车间网络中拥有重要位置，在很大程度上可以控制制造信息的传播路径走向，从而改变制造信息传播范围的节点。定义6瓶颈度指各节点在外部制造需求和内在生产

24、环境共同影响下成为瓶颈的能力，它是节点固有的一种动态特性，用于描述节点对制造网络的直接影响力。在JSN中，一个节点的瓶颈度大小取决于两个方面：其在JSN中的重要度，利用最有效路径完成的网络效率进行评估计算；网络中其他节点对该节点的瓶颈贡献程度，利用工作站负载值表征其对全网的节点的瓶颈度贡献基准值。因此，网络中每个节点依赖于其余节点的程度可以通过贡献矩阵进行计算，如式(7)所示：S：= 一”降L：，e21e22：Pm2W1W2：。(7)因此，第r个节点在整体JSN中的相对重要度为s，一Sq。 (8)sr一厶 。 L6通过综合考虑待评估节点自身的全局中心性介数，及其他节点对待评估节点的瓶颈贡献程度

25、，节点的瓶颈度为PB一B，S，。 (9)进行归一化处理，得第r个节点的瓶颈度埘P7肿一当r_ B(r)(氏W，)生垒一 。 (10)P肌(B(七)(已hW；)=r =， z；E31 基于贡献矩阵的作业车间节点瓶颈度算法大多数制造工况下，节点之间连通的最简单形式取决于加工的相依性，即相邻工作站之间的相互依赖关系。但在车间生产网络中存在一种工作站节点，它们本身并不相邻但具有明显的局部重要度，且对待评估节点具有较大的传输效率，该类非邻接节点所产生的瓶颈贡献程度将大于邻接节点。因此，本文综合考虑影响节点瓶颈度的因素，提出节点瓶颈度评价算法，具体步骤如下：步骤1根据式(4)，计算节点介数B，。步骤2计算

26、任意两个节点之间的网络效率SPFA(shortest path faster algorithm)真法?h并写入效率矩阵(5)。步骤3根据式(6)计算节点的负载W，。步骤4根据式(7)计算节点的重要度矩阵。步骤5 根据式(8)计算第r个节点在整体JSN中的相对重要度S，。步骤6根据式(10)计算节点的瓶颈度P7BN，并写入矩阵(9)，输出结果即为节点的瓶颈度评估值。该方法综合考虑节点自身负载(制造负载)和结构负载(度、介数、网络效率)，能比较客观、全面地反映节点瓶颈度等级，弥补了节点瓶颈度评估只依赖邻接节点的不足。4算例分析41数据处理以某机电产品企业A车间数据集作为模型研究实例，该企业车间的

27、组织形式遵循作业车间原则，所采集的实验数据均为该车间制造执行系统(Manufacturing Executive System，MES)的真实反馈数据。该车间共有35个工作站Ri(i一1，2，35)，加工A，B，C和D四类典型零件，每天工作8 h。表1所示为每种零件在各工作站的标准处理时间、准备时间和各工作站服务能力；表2所示为零件每天的加工数量。假定该车间运输设备充裕，不存在物流运输瓶颈，且不存在返工产品。表1 零件标准处理时间(rain)准备时间(rain)及节点服务能力辨mm；万方数据第4期 李晓娟等：基于网络结构特征的作业车间瓶颈识别方法 1093续表1C1330o930O970 O9

28、1O99 o80O9874O986009859098 74O99 O45 o98074 0 60 0 59 0 74 uDl14099O78O99O12O98 073099 076O97D 099O99O98 一O99 一49 o97050 0 54 0 48 0 52 U 表2零件每天的加工数量 件天数零件类型42模型的建立由于所采集的数据集均为车间生产计划和IVIESR-11R3t-7RII-m2 Rll,3R蕾7 R丝-Rtl-S 6R2e13 Rm。5 瞄一 撵知”h， 81” “5R，R， R3elORi$-6R-5 R2 R1117 嗡。7 Ra1 R奄10R“。R7I m11的原

29、始数据，需经过一定转化步骤才能最终形成网络模型。具体步骤如下：步骤1选择观察时间区间。步骤2抽取所有节点和连边。步骤3将节点和连边信息转化为网络模型。步骤4给点和连边赋予性能特征信息。步骤5计算网络特征信息，为瓶颈节点计算提供数据支持。通过转化建立车间数据集的制造网络模型，如图2所示。“。07一、，蛔，哪，吵 ，嘣土，!矽乡叠7帮7磅， ”叫o、磐j 70渐一，。霉醚。删R310 R珥10圈2作业车间网络拓扑结构图中展示了机电产品企业A车间制造网络演化后的最大连通子图。同时，该车间系统网络模型也从微观结构揭示了车间内部高度互联的作业车间结构。43瓶颈度计算采用基于贡献矩阵的瓶颈度计算方法预测该

30、机电产品企业A生产车间工作站瓶颈情况。以d为单位，连续预测8 d。为验证方法的准确性，采用文献E83中的PBM预测方法和文献163中的原瓶颈指数JBN预测方法，对该组实际数据进行同步验证，以对结果进行比对。依据所建立算法计算各节点的瓶颈度PBN，假定车间生产波动微小，可忽略不计，瓶颈判定标准_】一1，计算结果如表3所示。鹣0，。表3节点瓶颈度计算【8 d)l d 2 d名称度度萎负载介效 度 兰萎彦萎萎介教苫名称 一 负载度Rl 0848 0632 0486 126 R1 0459 0642 0481 129Rz 0634 0367 0228 082 Rz 0234 0567 0328 079

31、R3 0756 0588 0472 118 R3 0433 0537 0443 121Rz0432 0369 0259 077 R20147 0271 0156 078R35 0574 0377 0102 079 R35 0169 0277 0152 0763 d 4 d耋耋度霎蓁介数苫 名称度度萋负载介数 度Rl 0415 0602 0536 113 R1 0405 0402 0428 107Rz 0212 0479 0228 08 Rz 0314 0511 0328 098Rs 0441 0533 0429 097 R3 0441 0542 0507 1145O22465l一55OZ一94

32、78558O一7788_18025599O2O59668一O488748868O86598一O0O06485一瓣万方数据1094 计算机集成制造系统 第22卷续表3Rz4 0161 0293 0172 076 0 Rz0159 0237 0112 078R35 0177 0247 0168 069R35 0163 0Z25 0104 0735 d 6 d耋耋度昙蓁介数苫 名称度度萋负载介数 度名称度负载介数 度Rl 0611 0513 0561 138 Rl 0415 0602 0413 112Rz 0224 0265 0233 075 R2 0387 0579 0399 109R3 0573

33、 0521 0524 120 R3 0358 0543 0347 091R24 0192 0227 0186 076 R24 0156 0223 0118 076R35 0214 0263 0201 078 R35 0177 0244 0149 07,17 d 8 d耋曩度罢萎介数苫 名称度度萎负载介数 度名称度 负载介数度Rl 0389 0405 0376 096 R1 0321 0523 0435 083Rz 0454 0561 0444 112 Rz 0276 0446 0387 074R3 0406 0541 0436 109 R3 0283 0487 0417 077R20187 0

34、222 0139 080 R20115 0262 0172 059R35 0174 0173 0114 069 R35 0123 0217 0164 061受外部需求和内部产能的综合影响，节点的瓶颈度不断发生变化，导致系统瓶颈的数量和位置也不断变化，在某一时刻可能存在一个或多个瓶颈，而且瓶颈会发生动态漂移。以第1 d计算结果为例，在测试的第1生产日内车间存在两个瓶颈，分别为R。和R。，其中R。为主瓶颈。为验证预测结果的准确性，实际统计车间1 d各工作站的活性时间。根据统计数据显示，预测结果与实际相符，统计结果如图3所示。R3sR14飓R2JRIi f卜一_ 一H H -_JIlI： E： ：目

35、2#I Hi l二1 l；l一。 1 i i。 iI 2 3 4 5 6 7 8时间hH活性时间r-l漂移瓶颈团唯一瓶颈图3车间瓶颈漂移过程示意图其他方法预测结果利用最大出现频率PBM和JBN法预测系统瓶颈。其中R，表示多瓶颈存在时该节点为主瓶颈。依次预测后7 d的瓶颈位置，结果如表4所示。表4预测结果对比126129113107138112O960820790800980751091121081210971141ZO091109077 079 R，R3078 076 Rf，R3076 069 Rl078 0。73 Rf，R3076 078 R，R3076 074 Rr，Rz080 069 R

36、2，R3111113098105122103O90O72073070083O75096102103106089101110085100O6S063062065070O68O74068 R2，R3 R2 R，R3065 R，R3060 一061 Rl，R3069 RI。R3065 R，060 R，R3R1 Rf，R3R1 R1R3 R3R3 Rf，R3R2 R广，R2Rz R，R38 083 074 077 059 061 075 065 063 050 048 一 R144结果分析基于贡献矩阵的节点瓶颈度算法和IB法预测结果具有较好的一致性。二者主瓶颈预测结果吻合率为875，准确率均为875；

37、次瓶颈预测结果吻合率为72，准确率分别为86和72。两者对主瓶颈和次瓶颈的预测精确度均较好，其中基于贡献矩阵的节点瓶颈度算法改进了节点瓶颈度贡献发生在邻域范围内的情况，因此提高了判断的准确性。基于贡献矩阵的节点瓶颈度算法和PBM法对主瓶颈预测结果也具有较好的一致性，吻合率为86；PBM法只能预测出系统的主瓶颈，对次瓶颈忽略不计；基于贡献矩阵的节点瓶颈度算法则能够有效地区分节点间的重要程度。三种算法判断节点l234567万方数据第4期 李晓娟等：基于网络结构特征的作业车间瓶颈识别方法 1095瓶颈度的侧重点略有不同，结果稍有差异，但总体吻合度较高，从而证明了算法的正确性与有效性。为提高算法运行效

38、率，采用SPFA算法计算节点间的最短路径，算法的时间复杂度为O(P)。因为平均度一2en，所以所提算法的时间复杂度为o(n2)。当(D(，)竹时，算法的时间复杂度可达到0(行2)。5 结束语本文从复杂网络的视角出发，对作业车间进行复杂生产网络建模和分析，在理论上揭示作业车间系统各构成要素及其相互作用关系。以网络模型为基础，考虑制造信息在生产网络中的传播机制以及对其他节点的影响机理，建立基于贡献矩阵的作业车间节点瓶颈度算法，在保证瓶颈预测精度的前提下实现了作业车间瓶颈的量化描述和连续预测，进而为生产过程的合理规划和有效控制提供了依据。尽管本文是针对离散制造行业机加工车间进行研究，但其模型和算法可

39、以很方便地推广到其他类型的制造系统中。针对瓶颈动态识别的网络分析方法可兼顾全局和局部，具有一定的普适性，也可以推广到其他工程应用领域，为离散和连续优化问题的求解提供新方法和思路。本文未考虑不确定扰动因素对瓶颈多态性的影响，在后期工作中将基于网络模型研究机器故障、交货期变动等扰动事件在网络中的传播方式和传播临界行为，分析网络结构变化对作业车间运行效能的影响，揭示系统中扰动性事件在作业车间网络中的扩散机制以及对其他节点瓶颈度的影响机理。参考文献：1POLLETT P KModeling congestion in dosed queuing networkJInternational Transa

40、ctions in Operational Research，2000，7(4)：319-3302ROSER C，NAKANO M，TANAK MComparison of bottleneck detection methods for ACV systemsCProceedings ofthe 2003 Winter Simulation ConferenceWashington，DC，USA：IEEE，2003：119211983LI LBottleneck detection of complex manufacturing systemsusing a data-driven met

41、hodJInternational Journal of Production Research，2009，47(24)：6929694041 MUTHIAH K M N，HUANU S HOver all throughput effectiveness(OTE)metric for factor-level performance monitoring and bottleneck detectionJInternational Journal of Production Research，2007。45(20)：4753-476953 KASEMSET CKA 4cHITvIcHYANu

42、KuL VSimulationbased procedure for bottleneck identificationMCommunications in Computer and Information SCjenceBerlin，Germany：Springer-Verlag B，2007：435961 WANG Junqiang，KANG Yong，CHEN Jian，et a1Identification approach for bottleneck duster in a Job ShopJComputer Integrated Manufactu“ng Systems，2013

43、，19(3)：540547(in Chinese)王军强，康永，陈剑，等作业车间瓶颈簇识别方法J计算机集成制造系统，2013，19(3)：5405477ZHAI Yingni，SUN Shudong，WANG Junqiang，et a1scheduling algorithm based on bottleneck operations decompositionfor large-scale Job Shop scheduhng problemsJComputer Integrated Manufacturing Systems，201l，17(4)：827831(in Chinese)翟

44、颖妮，孙树栋，王军强，等大规模作业车间的瓶颈分解调度算法J计算机集成制造系统，2011，17(4)：8278318 zHANG RIui，CHENG WuBottleneck machine identificationmethod based on constraint transf0,rmation for job shop scheduling with genetic algorithmJInformation Sciences，2012，188：236-252DOI：101016jins2011110139WANG Gang，WANG Junqiang，SUN Shudong，et

45、a1Bottleneck identification for job shop in disturbance environmentJMechanical Science and Technology for Aerospace Engineering，2010，29(12)：16971702(in Chinese)王刚，王军强，孙树栋，等扰动环境下Job Shop瓶颈识别方法研究J机械科学与技术，2010，29(12)：1697170210WANG Z T，wu Q D，QIAO FA lot dispatching strategyintegrating WIP management a

46、nd wafer start controlJIEEE Trans on Automation Science and Engineering。2007，4(4)：579-58311QIAO Fei，MA Yumin，LI Li，et a1Multi一reentrant manufacturing system scheduhng based on layered bottleneck analysisJComputer Integrated Manufacturing Systems，2010，16(4)：855860(in Chinese)乔非，马玉敏，李莉。等基于分层瓶颈分析的多重入制造

47、系统调度方法J计算机集成制造系统，2010，16(4)：855-86012RICHARD A RApplying the TOC five in the service sector-a banking step focusing subsystemJManaging ServiceQuality，2007，17(2)：20923413WANG Z J，CHEN J，wu Q DA new method of dynamicbottleneck detection for semiconductor manufacturing linecProceedings of the 17th World Congress the International Federation of Amtomatic，Contr01AImsterdam，the