搜索
现代制造系统第8章制造过程的建模与分析（5-7）东北大学秦皇岛分校黄亮n-xyz@163.com第8章制造过程的建模与分析z8.1制造过程建模概述z8.2马尔可夫链z8.3排队网络z8.4极大代数z8.5活动网络图z8.6Petri网z8.7仿真语言简介z8.8制造成本建模z8.9制造质量建模z狭义上的活动网络图指{（1）双代号网络图（activityonedges，AOE）；{（2）单代号网络图（activityonvertices，AOV），这两种主要用于项目管理。z广义上的活动网络图泛指使用有向图表达活动的过程模型，样式多种多样，例如{（3）状态转移图（statetransitiondiagram）;{（4）活动循环图（activitycyclediagram，ACD）。z后面介绍的经典Petri网以及各种高级Petri网也有由双代号网络图发展变化而得到的。8.5活动网络图（1）双代号网络图（activityonedges，AOE）:z以有向线段及其两端结点的编号表示活动的网络图，即活动在有向线段上。{例如：ijk活动代号或名称活动代号或名称持续时间持续时间z双代号网络图举例：{图中虚线表示“虚工作”，即实际中并不存在的活动。虚线只表示前后相邻活动之间的前后关系，虚线本身既不占用时间，也不耗用资源。活动名称C5E6H3B1G5D2012345616F5持续时间（2）单代号网络图（activityonvertices，AOV）:z以结点表示活动，以有向线段表示活动之间的先后关系的网络图，即活动在结点上。{例如：{有时仅需要记录活动代号时，则圆圈中的分割线可省略。活动代号活动名称持续时间z单代号网络图举例：z单代号网络图表示虚工作更方便一些，但双代号网络图更符合人们的表达习惯，实际中用得更多一些。（3）状态转移图（statetransitiondiagram）:z以结点表示状态，以有向线段表示状态之间的转移关系的一种过程建模方式。z从外在形式上看，状态转移图与双代号网络图几乎没有差异，唯一区别在于{状态转移图的有向线段上标注状态转移的概率或速率，{而双代号网络图的有向线段上标注活动持续的时间。z状态转移图举例：{回顾课件第8.2节中的青蛙蹦荷叶案例，{状态转移图也可表达成状态转移矩阵，图中有向线段上标注的概率或速率经常直接写在状态转移矩阵中。132111213212223313233pppHpppppp⎛⎞⎜⎟=⎜⎟⎜⎟⎝⎠（4）活动循环图（activitycyclediagram，ACD）:z以结点表示状态（这里是持续存在的状态，等同于活动），有向线段表示状态之间的关系的一种过程建模方法，其中状态分为{活动态（简称活动），用矩形框表示；{等待态（简称队列），用圆或椭圆表示。z在对实际系统的建模描述时，活动与队列往往交替地周期性进行下去，因此可以首尾连接形成封闭的循环，故称之为活动循环图。z活动循环图的表达方式与单代号网络图类似。z活动循环图举例：{实体数量标于循环路径中央（例如机床3）；{活动周期（持续时间）标于该活动的矩形框下。z活动网络图的应用:z本节举3个案例说明活动网络图的基本应用，如下{（1）状态转移图的应用z——求解稳态方程（结合马尔可夫链和排队网络）；{（2）单代号网络图的应用1z——调度死锁分析（结合线性代数中的矩阵运算）；{（3）双代号网络图的应用2z——关键路径分析（结合极大代数中的矩阵运算）。（1）求解稳态方程:z例1，有一制造单元，其组成如图所示。{其中M1、M2为加工工作站，M3为装配工作站。{三个工作站的工作速率分别为w1，w2和w3。{求各设备的利用率和系统的生产率。z例1，分析：{设每个工作站有工作或空闲两种状态，{则整个系统存在7种状态，如下{状态1，M1和M2工作，M3空闲，记作PPI；{状态2，M1空闲，M2工作，M3空闲，记作IPI；{状态3，M1工作，M2空闲，M3空闲，记作PII；{状态4，M1，M2和M3全工作，记作PPP；{状态5，M1空闲，M2和M3工作，记作IPP；{状态6，M1工作，M2空闲，M3工作，记作PIP；{状态7，M1和M2空闲，M3工作，记作IIP。z例1，继续分析：{思考：为什么不是23=8种状态？z哪种状态不会出现？{答案：默认为持续生产且原料充足，z不存在三个工作站都空闲的状态。{思考：工作站空闲的原因是什么?{答案：默认为持续生产且原料充足，zM3空闲是因为M1和M2两者或其中之一未能供上半成品作为装配的原料；zM1空闲是因为M3忙或者M2未能配套供料；zM2空闲是因为M3忙或者M1未能配套供料。z例1，继续分析：将上述状态转移关系用状态转移图表示如下{设生产达到稳态，则一段时间内的状态转移概率等同于相应的生产速率，标于图中箭头处。z例1，解：{根据状态转移图，得状态转移概率矩阵{非对角元素为相应状态之间的转移速率；{每行的对角元素为整行非对角元素之和的负数，z用以保证行元素之和为0。()()()()121222113123123232313133000000000000000000000000000000⎛−+⎞⎜⎟−⎜⎟⎜⎟−⎜⎟=−++⎜⎟⎜⎟−+⎜⎟−+⎜⎟⎜⎟−⎝⎠z例1，继续解：{利用稳态方程和。{可解得{即为系统稳态后各个状态的出现概率。{设备利用率为该设备所有工作状态的概率之和，则M1、M2和M3的设备利用率分别为0PQ=[]1234567.Pppppppp=113462124534567,,.uppppuppppupppp=+++=+++=+++1jjp=∑z例1，继续解：{由于M3负责系统成品的组装，则系统生产率等同于M3的实际生产率。{工作站的实际生产率为工作站的生产速率与工作站的设备利用率的乘积，即z总结解题步骤：{（1）列出系统所有状态，绘制状态转移图；{（2）构造状态转移概率矩阵和稳态方程；{（3）计算稳态概率，计算设备利用率和系统生产率。s33wwu=（2）调度死锁分析:z调度死锁指因为调度方案不合理，多个生产活动相互制约，导致调度方案无法执行的一种情况。z生产调度中要避免出现死锁现象，因此要在调度方案执行前判断是否存在死锁。z如存在死锁，则要修改调度方案，以上分析过程称为调度死锁分析。z调度死锁问题的背景：{实际制造系统中死锁多出现在搬运能力或存储能力有限的制造系统中。{如果一方面输送的原料类型不对，不能满足生产需求，另一方面搬运设备或原料缓冲区又被错误的原料占用，不能更换原料，此时死锁就发生了。z调度死锁问题举例：{某冷凝器车间存在多种不同类型的产品，{不同产品需要长短不同的铜管作为原料，{铜管为避免弯曲，需要专门工具搬运。z调度死锁问题举例（续）：{某日因调度不当，运输工具被长管占用，{而根据订单，产品需要短管做原料，{若生产短管则无工具搬运和存放。z调度死锁问题举例（续）：{该死锁环节生产活动之间的约束关系可以用有向图表达，如下所示z可发现，有向图中存在“环”，这是出现死锁的标志。z调度死锁问题举例（续）：{最终解决方法——z将长管手工锯断，作为短管使用。{造成损失包括：z耽误生产时间，z浪费材料，z额外的人工费。z因此，{生产中要避免{出现死锁现象。z什么时候出现死锁？{例2，考虑生产调度的一般情况：z2台设备，2个零件，4道工序，{方案A——z一种可行的方案如图。z什么时候出现死锁？{还是例2，2台设备，2个零件，4道工序，{方案B——z出现死锁的方案如图。z如何判断出现死锁？z答案：{若调度方案可以以有向图表达，{没有死锁=有向图不存在环，{出现死锁=有向图存在环。z简单的有限图我们可以直接看出是否存在环，{对于十分复杂的有向图应如何判断？S11SS21SS31SS41SS51SR1SR2SR3SR4SR5SC11SC21SC31SC41SC51SW1SW2SW3SW4SW5SS12SS22SS32SS42SS52SC12SC22SC32SC42SC52SS13SS23SS33SS43SS53SC13SC23SC33SC43SC53SS14SS24SS15SS44SS54SC14SC24SC15SC44SC54SS45SC45Sz复杂的有向图是否存在环的判断方法：{首先将有向图（单代号网络图）以邻接矩阵的形式表达，{继而通过邻接矩阵计算可达矩阵，即可判断是否存在环。z如图所示的有向图，{其邻接矩阵为011001000M⎛⎞⎜⎟=⎜⎟⎜⎟⎝⎠z复习可达矩阵的计算方法：{若邻接矩阵以M表达，{则可达矩阵z本例中2...nPMMM=+++012001000P⎛⎞⎜⎟=⎜⎟⎜⎟⎝⎠2001000000M⎛⎞⎜⎟=⎜⎟⎜⎟⎝⎠000000(3)000nMn⎛⎞⎜⎟011001000M⎛⎞⎜⎟=⎜⎟⎜⎟⎝⎠3000000000M⎛⎞⎜⎟=⎜⎟⎜⎟⎝⎠=⎜⎟⎜⎟⎝⎠z回到调度死锁问题，{可行调度方案（无环图）的邻接矩阵：z以一个4维矩阵的4个维度分别表示无环图中的4个活动，该矩阵记作M1。1(1,1)(1,2)(2,2)(2,1)(1,1)0110(1,2)0001(2,2)0000(2,1)0010M⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦z计算可行调度方案的可达关系，{可见，其矩阵的4次幂即为零矩阵，{表示该有向图不存在4阶可达关系，{容易证明，该有向图也不存在更高阶的可达关系，所以该有向图无环。210001001000000000M⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦310010000000000000M⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦410000000000000000M⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦10110000100000001M⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦z采用同样的分析方法，{死锁调度方案（有环图）的邻接矩阵：z同样以一个4维矩阵的4个维度分别表示有环图中的4个活动，该矩阵记作M2。2(1,1)(1,2)(2,2)(2,1)(1,1)0100(1,2)0001(2,2)1000(2,1)0010M⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦z计算可行调度方案的可达关系，{（过程略），直到得到其5阶可达关系，{可发现，表达5阶可达关系的矩阵与邻接矩阵相同，即证明该有向图存在环。520100000110000010M⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦20100000110000010M⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦220001001001001000M⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦z调度死锁分析的总结：{一个存在n道工序的调度方案，z可用n个结点的有向图表达，z同时也可用n维邻接矩阵表达。{若邻接矩阵存在n阶或n阶以上的非零可达矩阵，z则该有向图存在环，调度方案存在死锁；{否则，z该有向图不存在环，调度方案不存在死锁。（3）关键路径分析:z一系列存在相互制约的活动可以使用有向图（双代号网络图）表示，显然最终活动的结束时间由该有向图中累积时间最长的路径决定，该路径称为关键路径。z如下图例中的红线所示：C5E6H3B1G5D2012345616F5z关键路径的手工计算方法——结点法，{口诀：沿线累加、逢圈取大。z例3，某表示建筑项目工期的双代号活动网络图如下所示，要求使用结点法计算关键路径。z例3，解：首先计算各个结点的时间，{步骤1（沿线累加、逢圈取大），{寻找前驱结点时间都已知的未知时间结点。{找到结点2，只有一个前驱结点1。{已知结点1时刻为0，则结点2时刻为0+1=1。z例3，继续解：步骤2，{继续寻找前驱结点时间都已知的未知时间结点。{找到结点3，有2个前驱结点，为结点1和2。{根据结点1，结点3时间为0+5=5，{根据结点2，结点3时间为1+0=1（回顾虚工作），{取两者之中的最大值，则结点3时间为5。z例3，继续解：步骤3，{继续寻找前驱结点时间都已知的未知时间结点。{找到结点4，有1个前驱结点，为结点3，{根据结点3，结点4时间为5+5=10。z例3，继续解：步骤4，{最后处理结点5，有2、3和4共3个前驱结点，{根据结点2，结点5时间为1+5=6，{根据结点3，结点5时间为5+6=11，{根据