1、现代制造系统,第8章 制造过程的建模与分析（5-7） 东北大学秦皇岛分校 黄亮 n-xyz,第8章 制造过程的建模与分析 8.1 制造过程建模概述 8.2 马尔可夫链 8.3 排队网络 8.4 极大代数 8.5 活动网络图 8.6 Petri网 8.7 仿真语言简介 8.8 制造成本建模 8.9 制造质量建模,狭义上的活动网络图指 （1）双代号网络图（activity on edges，AOE）； （2）单代号网络图（activity on vertices，AOV），这两种主要用于项目管理。 广义上的活动网络图泛指使用有向图表达活动的过程模型，样式多种多样，例如 （3）状态转移图（state
2、 transition diagram）; （4）活动循环图（activity cycle diagram，ACD）。 后面介绍的经典Petri网以及各种高级Petri网也有由双代号网络图发展变化而得到的。,8.5 活动网络图,（1）双代号网络图（activity on edges，AOE）: 以有向线段及其两端结点的编号表示活动的网络图，即活动在有向线段上。 例如：,双代号网络图举例： 图中虚线表示“虚工作”，即实际中并不存在的活动。虚线只表示前后相邻活动之间的前后关系，虚线本身既不占用时间，也不耗用资源。,（2）单代号网络图（activity on vertices，AOV）: 以结点表示
3、活动，以有向线段表示活动之间的先后关系的网络图，即活动在结点上。 例如： 有时仅需要记录活动代号时，则圆圈中的分割线可省略。,单代号网络图举例：,单代号网络图表示虚工作更方便一些，但双代号网络图更符合人们的表达习惯，实际中用得更多一些。,（3）状态转移图（state transition diagram）: 以结点表示状态，以有向线段表示状态之间的转移关系的一种过程建模方式。 从外在形式上看，状态转移图与双代号网络图几乎没有差异，唯一区别在于 状态转移图的有向线段上标注状态转移的概率或速率， 而双代号网络图的有向线段上标注活动持续的时间。,状态转移图举例： 回顾课件第8.2节中的青蛙蹦荷叶案例
4、， 状态转移图也可表达成状态转移矩阵，图中有向线段上标注的概率或速率经常直接写在状态转移矩阵中。,（4）活动循环图（activity cycle diagram，ACD）: 以结点表示状态（这里是持续存在的状态，等同于活动），有向线段表示状态之间的关系的一种过程建模方法，其中状态分为 活动态（简称活动），用矩形框表示； 等待态（简称队列），用圆或椭圆表示。 在对实际系统的建模描述时，活动与队列往往交替地周期性进行下去，因此可以首尾连接形成封闭的循环，故称之为活动循环图。 活动循环图的表达方式与单代号网络图类似。,活动循环图举例： 实体数量标于循环路径中央（例如机床3）； 活动周期（持续时间）标
5、于该活动的矩形框下。,活动网络图的应用: 本节举3个案例说明活动网络图的基本应用，如下 （1）状态转移图的应用 求解稳态方程（结合马尔可夫链和排队网络）； （2）单代号网络图的应用1 调度死锁分析（结合线性代数中的矩阵运算）； （3）双代号网络图的应用2 关键路径分析（结合极大代数中的矩阵运算）。,（1）求解稳态方程: 例1，有一制造单元，其组成如图所示。 其中M1、M2为加工工作站，M3为装配工作站。 三个工作站的工作速率分别为w1，w2和w3。 求各设备的利用率和系统的生产率。,例1，分析： 设每个工作站有工作或空闲两种状态， 则整个系统存在7种状态，如下 状态1，M1和M2工作，M3空闲
6、，记作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。,例1，继续分析： 思考：为什么不是23=8种状态？ 哪种状态不会出现？ 答案：默认为持续生产且原料充足， 不存在三个工作站都空闲的状态。 思考：工作站空闲的原因是什么? 答案：默认为持续生产且原料充足， M3空闲是因为M1和M2两者或其中之一未能供上半成品作为装配的原料； M1空闲是因
7、为M3忙或者M2未能配套供料； M2空闲是因为M3忙或者M1未能配套供料。,例1，继续分析：将上述状态转移关系用状态转移图表示如下 设生产达到稳态，则一段时间内的状态转移概率等同于相应的生产速率，标于图中箭头处。,例1，解： 根据状态转移图，得状态转移概率矩阵 非对角元素为相应状态之间的转移速率； 每行的对角元素为整行非对角元素之和的负数， 用以保证行元素之和为0。,例1，继续解： 利用稳态方程 和 。 可解得 即为系统稳态后各个状态的出现概率。 设备利用率为该设备所有工作状态的概率之和，则M1、M2和M3的设备利用率分别为,例1，继续解： 由于M3负责系统成品的组装，则系统生产率等同于M3的
8、实际生产率。 工作站的实际生产率为工作站的生产速率与工作站的设备利用率的乘积，即 总结解题步骤： （1）列出系统所有状态，绘制状态转移图； （2）构造状态转移概率矩阵和稳态方程； （3）计算稳态概率，计算设备利用率和系统生产率。,（2）调度死锁分析: 调度死锁指因为调度方案不合理，多个生产活动相互制约，导致调度方案无法执行的一种情况。,生产调度中要避免出现死锁现象，因此要在调度方案执行前判断是否存在死锁。 如存在死锁，则要修改调度方案，以上分析过程称为调度死锁分析。,调度死锁问题的背景： 实际制造系统中死锁多出现在搬运能力或存储能力有限的制造系统中。 如果一方面输送的原料类型不对，不能满足生产
9、需求，另一方面搬运设备或原料缓冲区又被错误的原料占用，不能更换原料，此时死锁就发生了。,调度死锁问题举例： 某冷凝器车间存在多种不同类型的产品， 不同产品需要长短不同的铜管作为原料， 铜管为避免弯曲，需要专门工具搬运。,调度死锁问题举例（续）： 某日因调度不当，运输工具被长管占用， 而根据订单，产品需要短管做原料， 若生产短管则无工具搬运和存放。,调度死锁问题举例（续）： 该死锁环节生产活动之间的约束关系可以用有向图表达，如下所示,可发现，有向图中存在“环”，这是出现死锁的标志。,调度死锁问题举例（续）： 最终解决方法 将长管手工锯断，作为短管使用。 造成损失包括： 耽误生产时间， 浪费材料，
10、 额外的人工费。 因此， 生产中要避免 出现死锁现象。,什么时候出现死锁？ 例2，考虑生产调度的一般情况： 2台设备，2个零件，4道工序， 方案A 一种可行的方案如图。,什么时候出现死锁？ 还是例2，2台设备，2个零件，4道工序， 方案B 出现死锁的方案如图。,如何判断出现死锁？ 答案： 若调度方案可以以有向图表达， 没有死锁=有向图不存在环， 出现死锁=有向图存在环。,简单的有限图我们可以直接看出是否存在环， 对于十分复杂的有向图应如何判断？,复杂的有向图是否存在环的判断方法： 首先将有向图（单代号网络图）以邻接矩阵的形式表达， 继而通过邻接矩阵计算可达矩阵，即可判断是否存在环。 如图所示的
11、有向图， 其邻接矩阵为,复习可达矩阵的计算方法： 若邻接矩阵以M表达， 则可达矩阵 本例中,回到调度死锁问题， 可行调度方案（无环图）的邻接矩阵： 以一个4维矩阵的4个维度分别表示无环图中的4个活动，该矩阵记作M1。,计算可行调度方案的可达关系， 可见，其矩阵的4次幂即为零矩阵， 表示该有向图不存在4阶可达关系， 容易证明，该有向图也不存在更高阶的可达关系，所以该有向图无环。,采用同样的分析方法， 死锁调度方案（有环图）的邻接矩阵： 同样以一个4维矩阵的4个维度分别表示有环图中的4个活动，该矩阵记作M2。,计算可行调度方案的可达关系， （过程略），直到得到其5阶可达关系， 可发现，表达5阶可达
12、关系的矩阵与邻接矩阵相同，即证明该有向图存在环。,调度死锁分析的总结： 一个存在n道工序的调度方案， 可用n个结点的有向图表达， 同时也可用n维邻接矩阵表达。 若邻接矩阵存在n阶或n阶以上的非零可达矩阵， 则该有向图存在环，调度方案存在死锁； 否则， 该有向图不存在环，调度方案不存在死锁。,（3）关键路径分析: 一系列存在相互制约的活动可以使用有向图（双代号网络图）表示，显然最终活动的结束时间由该有向图中累积时间最长的路径决定，该路径称为关键路径。 如下图例中的红线所示：,关键路径的手工计算方法结点法， 口诀：沿线累加、逢圈取大。 例3，某表示建筑项目工期的双代号活动网络图如下所示，要求使用结
13、点法计算关键路径。,例3，解：首先计算各个结点的时间， 步骤1（沿线累加、逢圈取大）， 寻找前驱结点时间都已知的未知时间结点。 找到结点2，只有一个前驱结点1。 已知结点1时刻为0，则结点2时刻为0+1=1。,例3，继续解：步骤2， 继续寻找前驱结点时间都已知的未知时间结点。 找到结点3，有2个前驱结点，为结点1和2。 根据结点1，结点3时间为0+5=5， 根据结点2，结点3时间为1+0=1（回顾虚工作）， 取两者之中的最大值，则结点3时间为5。,例3，继续解：步骤3， 继续寻找前驱结点时间都已知的未知时间结点。 找到结点4，有1个前驱结点，为结点3， 根据结点3，结点4时间为5+5=10。,
14、例3，继续解：步骤4， 最后处理结点5，有2、3和4共3个前驱结点， 根据结点2，结点5时间为1+5=6， 根据结点3，结点5时间为5+6=11， 根据结点4，结点5时间为10+3=13， 取三者中的最大值，为13。,例3，继续解：继而寻找关键路径， 从最大时间结点开始，根据最长时间的来源反向找结点，重复上述步骤直到找到初始结点。 步骤5， 关键路径一定包含时间最大结点，即结点5， 其最大时间来自结点4，则关键路径包含结点4。,例3，继续解：步骤6+7， 同理，结点4最长时间来源为结点3， 结点3最长时间来源为结点1， 所以关键路径包含结点3和1， 最后结论：关键路径为结点1-3-4-5。,与
15、调度死锁分析类似，简单的有向图，我们可以使用结点法手工计算关键路径，对于复杂的有向图如何处理？,复杂有向图的关键路径计算方法： 结合极大代数规则，进行定量计算。 回顾极大代数规则： 例图在极大代数规则下的邻接矩阵：,复杂有向图的关键路径计算方法： 根据邻接矩阵，计算可达矩阵,注: 虚工作记作权值为0的弧 并且,复杂有向图 的关键路径计算方法： 程序计算步骤 在可达矩阵中，选择元素全部为的一行，其行号为最终结点的编号； 选择以最终结点的编号为列号的一列，其中最大的元素取值即为最终结点时间； 最大的元素取值的计算过程标识着关键路径，参考后面的例4。,例4，某表示建筑项目工期的双代号活动网络图如下所
16、示（图和数据与例题3相同）， 要求使用极大代数方法计算关键路径。,例4，解： 步骤1，列出邻接矩阵； 步骤2，计算二阶可达关系；,例4，继续解： 步骤3+4，计算三阶、四阶可达关系；,例4，继续解： 步骤5，计算五阶可达关系； 此时可知五阶以上可达关系也为零矩阵。 问题：对于5个结点的有向图， 如果五阶可达关系不为零说明什么？ 答案：说明有向图存在环。,例4，继续解：步骤6，计算可达矩阵；,例4，继续解：步骤7，寻找关键路径。 可达矩阵中最长路径为结点1到结点5， 距离为13，则关键路径包含结点1和结点5； 分析距离13的来源3阶邻接矩阵， 分析记录的计算公式： 上式中方框标注的项最大， 其中
17、10为结点1到结点4,3为结点4到结点5， 因此关键路径包含结点4； 在分析10的来源，发现关键路径包含结点3， 最终关键路径为结点1-3-4-5。 以上方法看似麻烦，但适合计算机自动处理。,总结活动网络图: 活动网络图的形式多种多样，但基本原理类似，是仿真类过程模型中的一种基本方法。 活动网络图本身不具备分析功能，只能支持仿真程序的开发。即用于支持编程人员理清思路，设计算法。 活动网络图经常与分析类过程建模方法（马尔可夫链、排队网络和极大代数）结合，实现多种制造系统性能分析功能。,相关概念图论： 图论（graph theory）是数学的一个分支。它以图为研究对象。 图论中的图是由若干给定的点
18、及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论在多个科学领域都有广泛的应用，也是制造系统的建模、分析与优化领域所依据的重要理论体系之一。,相关概念图论： 图论的起源于数学家欧拉（Euler）1736年的哥尼斯堡（Konigsberg）之行。,欧拉在哥尼斯堡发现当地的市民正从事一项非常有趣的消遣活动。 哥尼斯堡城中有一条河流横经其中，这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。这就是著名的七桥问题。 欧拉将七桥问题转化成图形表达的数学问题，并
19、证明上述任务不可能完成。,相关概念图论： 在七桥问题的研究过程中，欧拉不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为“欧拉定理”。 凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。 凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点为终点。 其他情况的图都不能一笔画出。 上述研究提供了一个新的研究方向，开创了一个新的数学分支图论。,莱昂哈德欧拉（Leonhard Euler）（1707-1783），瑞士数学家和物理学家，近代数学先驱之一。,
20、欧拉在微积分、图论、力学、光学和天文学领域都做出过重大发现。 他引进的许多数学术语和书写格式，例如函数的记法“f(x) “ ，一直沿用至今。 欧拉一生共写下了886本书籍和论文，彼得堡科学院为了整理他的著作，足足忙碌了四十七年。他是科学史上最多产的数学家之一。,第8章 制造过程的建模与分析 8.1 制造过程建模概述 8.2 马尔可夫链 8.3 排队网络 8.4 极大代数 8.5 活动网络图 8.6 Petri网 8.7 仿真语言简介 8.8 制造成本建模 8.9 制造质量建模,8.6 Petri网,Petri网于1962年由德国数学家、信息学家卡尔亚当佩特里（Carl Adam Petri）提
21、出。 Petri网最初用于描述离散并发的计算机系统，后来被推广到制造领域离散事件动态系统的建模研究中。,因Petri网定义严谨，并且出现较早，因此成为应用得最多的一种图形化过程模型，有“流程定义语言之母”的称号。 因此，对Petri网的扩展研究非常多，除了佩特里提出的经典Petri网外，主要有 （1）时间Petri网（time Petri net）、 （2）随机Petri网（stochastic Petri net） （3）有色（着色）Petri网（colored Petri net）、 （4）层次Petri网（hierarchical Petri net）、 （5）广义随机Petri网（ge
22、neralized stochastic Petri net，GSPN）、 （6）扩展随机Petri网（extended stochastic Petri net，ESPN）等等。,经典Petri网的定义: Petri网模型的图形形式（还有语言形式）是一个有向的、只有两种结点的有向图。 各种状态称为库所（place），用圆圈“”表示， 状态之间的转移称为变迁（transition），用方框“”或竖线“”表示， 采用有向弧“”连接库所和变迁。 状态的取值称为令牌或托肯（Token），可用黑点在库所上标记，如“” 。,经典Petri网的语言描述： 经典Petri网使用五元组定义， 库所集，系统中状
23、态的集合； 变迁集，系统中状态之间转移关系的集合； 输入函数，指由库所指向变迁的弧； 输出函数，由变迁指向库所的弧； 输入或输出函数的值也称为弧的权值； 初始状态，各个库所初始的取值。,经典Petri网的绘制方法： 具有双向交换工作台的加工中心。,交换工作台： 具有两个或两个以上的可独立安装工件轮换进行工作的工作台。优点是可以一个工作台在加工，一个工作台在装配毛坯，效率较高。,P1P7表示系统的状态： P1 - 外工作台是否装有毛坯（圆圈中有黑点“”表示装有毛坯）； P2 - 加工中心是否加工完毕； P3 - 加工中心内的工作台上有否毛坯等待加工； P4 - 外工作台上有否成品等待拆卸； P5
24、 - 外工作台上的成品是否已卸下； P6 - 毛坯库情况； P7 - 成品库情况。,T1T4表示系统的活动过程： T1 - 将毛坯装上空的工作台； T2 - 双工作台换位； T3 - 将毛坯加工成成品； T4 - 将成品从工作台上卸下；,经典Petri网的应用： 绘制Petri网的主要目的在于帮助人们理清思路，辅助编制仿真程序。 当前，存在许多工具软件（通常称为“Petri网模拟”软件或“工作流开发”软件）提供绘制Petri网的功能，并在后台自动产生相应的仿真程序代码。,例如：Visual Object Net + 软件：,高级Petri网简介: （1）时间Petri网：变迁表示时间延迟； （
25、2）随机Petri网：变迁的时间延迟使用概率分布函数表达（例如指数分布）； （3）有色（着色）Petri网：令牌具有多种颜色，用以表示多种属性； （4）层次Petri网：网络具有多个层次，上层网络的局部可展开成一个子网络。 以上高级Petri网仅是描述功能更强大，但模拟的手段仍是编程仿真，因此仍属于仿真类模型。,有色层次Petri网示例， 案例，某物资存储系统示意图：,有色与层次的含义： 有色，指令牌存在多种状态； 层次，指变迁可能代表一个子系统。 某物资存储系统的 首层Petri网 t1-t4分别对应 固定货架、 旋转货架、 输送系统、 分拣系统。,然后每个子系统分别用一个Petri网描述，
26、 例如固定货架子系统和旋转货架子系统。,高级Petri网简介： （5）广义随机Petri网： 假设变迁时间服从指数分布，结合排队理论，可实现网络图的等效化简，因此可以无需编程仿真即实现性能分析，属于分析类模型。 （6）扩展随机Petri网 与广义随机Petri网类似，区别在于假设变迁时间服从一般分布（仅用均值和方差表达，而不关注具体分布形式），同样结合排队理论，实现近似的等效化简，属于分析类模型。,广义随机Petri网 常用于工作流或固定生产线建模。,案例， 某质量管理流程：,广义随机Petri网建模案例， 某质量管理流程的广义随机Petri网模型： 变迁服从指数分布， 图上标注的为变迁时间的
27、均值； 黑色方块代表瞬时变迁。,广义随机Petri网的等价化简： 等价化简的前提假设： 变迁时间相互独立，并服从指数分布。 可以等价化简的四种结构： （1）串联（sequent）结构， （2）并联（parallel）结构， （3）选择（choice）结构， （4）循环（iterative）结构。 下述等价化简公式的证明过程可参考清华大学出版社的随机Petri网和系统性能评价（林闯主编）。,（1）串联结构， 表示活动按顺序依次发生。 例如，一个零件加工完前一道工序，才能加工后一道工序。 注意：等价后的变迁不一定服从指数分布，只有均值符合等价化简公式。,（2）并联结构， 多个活动可同时进行，但需要
28、全部完成后才能进行后续活动。 例如，多个零件都加工完成后才能装配。,（3）选择结构， 多个活动按照一定概率进行，同时仅进行一个活动，并且总概率为1。 例如，某零件即可自行加工，也可以采购，二者根据当前的生产负荷情况选择其一。,（4）循环结构， 某活动按一定概率反复发生。 例如，某零件的某道工序加工难度大，经常需要返修，甚至返修多次。,例题1，某小型装配车间业务流程如下：,例题1，假设该业务流程的13个工作环节， 表示为t0至t12，各环节的处理时间相互独立， 并服从指数分布，其均值分别为38、15、8、30、20、40、5、120、40、2880、5、40、150， 单位为分钟，取值为0.91
29、,。 求整个系统对一笔订单的平均处理时间。,结论：整个系统对一笔订单的平均处理时间为3043.3分钟。 注意：等价化简后的时间不一定服从指数分布。,总结Petri网： Petri网是由活动网络图进化出的一种高级模型，因其定义严格，能够描述复杂的工作流程而被广泛应用。 经典Petri网以及有色层次Petri网等方法主要是辅助开发仿真程序，实现制造过程的性能分析，因此属于仿真类模型。 以广义随机Petri网为代表的方法结合了排队理论，可以通过等价化简简化制造过程，通过公式直接计算性能分析的结果，因此属于分析类模型。,第8章 制造过程的建模与分析 8.1 制造过程建模概述 8.2 马尔可夫链 8.3
30、 排队网络 8.4 极大代数 8.5 活动网络图 8.6 Petri网 8.7 仿真语言简介 8.8 制造成本建模 8.9 制造质量建模,除了前面介绍的建模方法外，还存在种类繁多的仿真建模工具，如witness、flexsim （参考建模与仿真课程），以及仿真语言，如GPSS、SIMAN等。 尽管它们的程序流程与开发工具各不相同，但都基于离散事件动态系统（DEDS）的基本假设，因此都属于仿真模型。 本节将简单介绍典型的仿真语言GPSS和SIMAN。,8.7 仿真语言简介,GPSS语言： GPSS是一种面向模块的语言。分析人员能以模块网络的形式向计算机输送一个模型，这些模块按序号的次序联结成网络
31、，每种模块代表一项基本的系统动作。 模块可反复地使用，模块所表示的动作由分析人员负责解释，执行该项动作所需的时间也由分析人员规定。 GPSS特别适用于交通系统和排队系统的建模，适用于需要详细研究的一个动态系统相互作用的情况。,GPSS仿真系统用模块符号来描述， 共定义了48种模块类型，每个都代表系统的一个特征活动，用户必须用这些模块图来画系统的模块流程图，程序将按顺序实现这些动作。,加工车间某一机床加工某一零件时，以每5分钟一件的速率进行，零件加工结束后送给检验员检验，检验一件的时间约为（43）分钟，有10零件不合格被拒收。,SIMAN语言： SIMAN既可按照进程交互方式仿真，又可按照事件调
32、度方式仿真，还可将这两种方式结合起来进行工作。 SIMAN建模强调系统模型和实验框架的区别。系统模型确定系统的静态和动态特性；实验框架确定使模型运行并产生特定输出数据的实验条件。 给定了系统模型和实验框架之后，该语言除了可提供标准输出报告之外，还根据实验框架中规定的内容产生用户的输出文件，用户可采用交互式或批处理方式对该输出文件进行各类数据处理。,事件图将模型的事件描述成网络节点， 节点编号由1开始直到总事件数。,一旦为模型选好了一种表达式，建模过程的下一步就是为每个事件建立逻辑表。事件逻辑表仅仅是事件每次发生时必须执行的逻辑步骤的汇总。,观察一个在一台机床上加工工件的例子，系统状态为排队的工
33、件数及机器的状态。只要工件进入系统，或开始由机床加工，或者工件离开系统，系统状态都将改变。,选定了系统的事件表达法，并确定了每个事件的逻辑，下一步就是将这种模型写成计算机代码。 其中包括编写描述系统中每个逻辑的FORTRAN子程序。,课程要求（8.5）,理解双代号网络图、单代号网络图和状态转移图的表示方法，简单了解活动循环图的表示方法； 掌握使用状态转移图辅助求解制造系统稳态方程的方法（本节例1）； 掌握利用双代号网络图和线性代数分析调度死锁问题的方法（本节例2）； 掌握利用双代号网络图和极大代数分析关键路径的方法（本节例3和例4）。,课程要求（8.6-7）,知道经典Petri网的图形描述和语言描述； 知道Petri网的主要高级形式（6种）， 知道各种高级Petri网的特点。 掌握广义随机Petri网3种结构（串联、并联和选择）的等价化简方法并会综合应用。 知道GPSS和SIMAN是典型的仿真编程语言。,
