生产计划与控制04第四章制造系统的建模方法

2019/10/41第4章制造系统的建模方法4.2活动循环图法4.4Petri网建模理论4.4.1Petri网的基本概念4.4.2Petri网的扩展形式4.4.3基于Petri网的事件关系分析4.4.4基于Petri网的系统性能分析4.4.5Petri网建模与分析实例4.5排队系统模型4.5.1排队系统的基本概念4.5.2顾客到达时间间隔和服务时间分布4.5.3排队系统的应用案例4.6库存系统模型4.6.1库存系统的基本概念4.6.2确定型库存模型4.6.3随机型库存模型2019/10/42活动循环图法（ACD）--基本原理离散事件系统建模方法之一——活动循环图法（ActivityCycleDiagram，ACD）ACD认为：系统中的每个实体都按照各自的循环方式发生变化－－静止状态和活动状态。这两种状态在循环交替出现。ACD以○表示静止状态，以□表示活动状态，以有向箭头→表示静止状态与活动状态之间的转换。当系统中有多个实体时，有向弧就要使用不同的颜色或线型，以示不同实体的区别。2019/10/43活动循环图法（ACD）--建模方法与建模过程根据研究对象的不同，可以建立系统不同层次的ACD模型，即高层次模型可以进一步分解为低层次的模型。ACD法注重“个体”的活动，系统状态的变化是全部个体状态变化的集合。ACD法的缺点：当系统庞大、复杂时，活动循环图将十分复杂；ACD法只描述系统的稳态，而不研究系统的瞬态（如动作的开始、结束等）；ACD法缺乏定量的分析工具。2019/10/44活动循环图法（ActivityCycleDiagram，ACD）ACD法中的术语：实体活动队列实体行为模式直联活动和虚拟队列合作活动2019/10/45活动循环图法（ACD）--举例一个由一位工人看管若干数控机床的加工车间。工人的任务是：（1）若刀具完好，则安装工件按运行按钮；（2）若若刀具损坏或需要更新，则先重装刀具，然后按运行按钮。上述工作仅当机床完成一次自动加工工序并停止运行时工人才能执行。假定每台机床均可加工各种工件，不会发生刀具、工件短缺现象。希望通过建模仿真来研究工人的忙闲率。（1）识别实体和属性①工人。“安装工件（RESET）”、“安装刀具（RETOOL）”、“其它活动（AWAY）”、“等待（WAITING）”。②机床。：“安装刀具”、“安装工件”和“加工（RUNNING）”。6活动循环图法（ACD）--举例（2）画实体活动周期图绘制实体活动周期图必须遵循以下两个原则：①交替原则②闭合原则7活动循环图法（ACD）--举例（3）系统活动周期图8活动循环图法（ACD）--举例（4）增加必要的虚拟实体（5）确定模型的参变量和属性描述变量参数：机床数量；参变量：“累计加工的工件数”和“累计加工时间”等；属性变量：“加工工件时间”、“安装刀具时间”、“安装工件时间”、“饮茶时间”等；服务规则：……9活动循环图法（ACD）--建模步骤（1）识别实体和属性；（2）分析各类实体的活动与状态及其变化的顺序；（3）画出个实体的ACD；（4）将实体ACD连接成系统ACD；（5）增添必要的虚拟实体；（6）表明活动发生的约束条件和占用资源的数量；（7）给出模型参数、参变量计算方法及属性描述变量取值方法模型，以及排队规则。•4.4Petri网建模与仿真–4.4.1Petri网的概述–4.4.2Petri的基本概念–4.4.3Petri网的运行规则–4.4.4Petri网的变迁间的关系–4.4.5Petri网的行为特性–4.4.6Petri网的行为特性分析方法–4.4.7Petri网的分类–4.4.8Petri网建模举例–4.4.9高级Petri网2019/10/4114.4.1Petri网的概述离散事件系统建模方法之三——Petri网（Petrinet）1962年，德国人CarlAdamPetri首次使用网状模型模拟通信系统，后发展成为Petri网理论。Petri网能够描述系统的结构特征，并能对系统的动态性能进行分析。与其它建模方法相比，Petri网建模具有下述优点：①Petri网具有准确的图形化建模能力和严密的数学基础，能够定性描述和定量分析系统中顺序、并发、随机和冲突等事件关系；2019/10/4124.4.1Petri网的概述②以Petri网模型为基础可以生成系统的控制逻辑代码及仿真逻辑代码；③通过仿真或数学方法，由Petri网模型分析系统的有界性、活性及可重用性等系统逻辑特性以及产量、设备利用率等性能指标。④Petri网提供了比其它建模工具更为丰富的模型信息。80年代以后，Petri网开始应用于制造系统的仿真、调度和控制建模以及系统性能分析中。2019/10/4134.4.2Petri的基本概念Petri网的基本概念：resourcestatetransitionplaceeventconditioncapability2019/10/4144.4.2Petri的基本概念Petri网的定义：Petri网有两种表示方式：一种是形式定义，另一种是图形表示。形式定义规定了Petri网的结构、组成、节点间的相互关系和动态行为。形式定义具有严密性、精确性、抽象性和概括性等优点，但是不形象、不直观，也不易于理解。Petri网的图形表示则具有形象直观、易于理解的特点，但是图形表示具有具体性，即Petri网图形往往与特定的建模实例相对应。2019/10/4154.4.2Petri的基本概念（1）定义1：基本Petri网N=P，T，F。其中，P={p1，p2，…，pm}为库所（place）的集合；T={t1，t2，…，tn}为变迁（transition）的集合；F=（P×T）∪（T×P）为输入函数和输出函数集，称为流关系。三元组N=（P，T；F）构成网（net）的充分必要条件：①P∩T=ф，规定了库所和变迁是两类不同的元素；②P∪T≠ф，表示网中至少有一个元素；③F=（P×T）∪(T×P)，建立了从库所到变迁、从变迁到库所的单方向联系，并且规定同类元素之间不能直接联系；2019/10/4164.4.2Petri的基本概念④dom（F）∪cod（F）=P∪T。dom（F）={x|］y:(x,y)∈F}为F所含有的有序偶的第一个元素的集合cod（F）={y|］x:(y,x)∈F}为F所含有的有序偶第二个元素的集合dom（F）∪cod（F）=P∪T则规定了网中不能有孤立元素。变迁的发生受到系统状态的控制，即变迁发生的前置条件必须满足；变迁发生后，某些前置条件不再满足，而某些后置条件则得到满足。Petri网描述系统的最基本概念是库所和变迁。库所表示系统的状态，变迁表示资源的消耗、使用及使系统状态产生的变化。2019/10/4174.4.2Petri的基本概念库所变迁N=P，T，F。其中，P={p1,p2,p3,p4}；T={t1,t2,t3}；F={(p1,t1),(t1,p2),(t1,p3),(p2,t2),…,(t3,p5)}。2019/10/4184.4.2Petri的基本概念图形化表示：Petri网是由节点和有向弧组成的一种有向图。用圆圈“0”表示库所用短竖线“|”或矩形“口”表示变迁以联结库所与变迁之间的有向弧表示输入输出函数用令牌（token）(库所中的黑点)表示库所中拥有的资源数量。库所中令牌分布决定变迁的使能（enabled）和激发（fire），变迁的激发又将改变令牌的分布。以变迁激发导致令牌在库所间的流动，Petri网可以用于模拟系统的动态运行过程，反映系统的动态特性。2019/10/4194.4.2Petri的基本概念W—权函数（权重）——每个变迁发生一次引起的相关资源数量上的变化，w(p,t)或w(t,p)，缺省时，权重为1.K—容量函数——库所容量，标注在库所旁边。缺省时，权重为1.M—标识——库所中拥有的资源（令牌）数量及其分布。标识以库所中的黑点表示。2019/10/4204.4.2Petri的基本概念举例。一个工业生产线Petri网模型。有一条工业生产线，它要完成两项工业操作，这两个操作分别用变迁t1和变迁t2表示。第一个变迁t1将传入生产线的半成品s1和部件s2用两个螺丝钉s3固定在一起，变成半成品s4.第二个变迁t2再将s4和部件s5用三个螺丝钉s3固定在一起，变成半成品s6.完成操作t1和t2都要用到工具s7.假定由于存放空间的限制，部件s2和s5最多不能超过100件，停放在生产线上的半成品s4最多不能超过5件，螺丝钉s3存放的件数不能超过1000件。2019/10/4214.4.2Petri的基本概念下图是一个具有W的petri网图。在这个图上弧线上标有数字。···················2019/10/4224.4.2Petri的基本概念六组元∑=（P，T；F，K，W，M0）构成库所/变迁网系统（place/transitionsystem，P/T_系统）的条件是：①N=（P，T；F）是构成∑的基网；②K，W，M0分别为N上的容量函数、权函数和初始标识。（2）定义2：库所/变迁网系统初始标识M0={m1,m2,…,mm}中的分量表示起始状态时相应库所中令牌的数量。系统运行过程中的标识用M表示。容量函数K表示库所的容量。有时，允许某些库所的容量为无穷，表示这些库所的容量不会对系统的行为构成限制。2019/10/4234.4.2Petri的基本概念上述定义给出了从结构到资源的静态特征，再定义变迁发生的条件和结果，构成了网系统的完整定义。权函数W规定每个变迁发生一次引起的相关资源数量的变化。一般地，对于任何（x，y）∈F，0W∞。网系统的动态规律称为变迁规则（transitionrule）。2019/10/4244.4.3Petri网的运行规则（3）定义3：变迁发生条件—运行规则∀p∈*t，M（p）≥W（p，t）∀p∈*t，M（p）≤[K（p）—W（t，p）]。∀p∈t*∧∀p∈t*，M（p）≤[K（p）+W（p，t）—W（t，p）]则称t在M下有效，记作M[t。六组元∑=（P，T；F，K，W，M）为一Petri网系统。对于任意t∈T变迁元素，如果在标识M下，有2019/10/4254.4.3Petri网的运行规则)(),(),()(),()(),()()('pMptWtpWpMptWpMtpWpMpM**ttp若ttp**若**ttp若**tp若M’为M之后继（successor）的事实记作M[tM’。若M[t,则t在M可以发生，同时将标识M改变为M的后续M’。对于任何p∈P，M’为：（4）定义4：变迁发生后果-运行规则4.4.3Petri网的运行规则下图是一个petri网系统中变迁t激发前和激发后的标识。例：根据Petri网的运行规则，按照t1t2t3t4的顺序，依次对图1中变迁发生进行检查。284.4.4Petri网的变迁间的关系基于Petri网的事件关系分析1.事件关系逻辑图a顺序关系b并发关系c冲突关系e迷惑关系d冲撞关系2019/10/4294.4.4Petri网的变迁间的关系基于Petri网的事件关系分析1.事件关系逻辑图f死锁关系•Petri网的可达性、有界性和安全性、活性以及可逆性。4.4.5Petri网的行为特性1、可达性可达性是Petri网的一个重要特性。给定一个Petri网，已知初始标识M0可以到达那些标识,或者给定某一标识，是否可以从初始标识通过一系列变迁到达该标识。定义5：若从初始标识开始实施一个变迁序列产生标识，则称该标识是从M0可达的。若只要从开始实施一个变迁即可产生，则称是从M0立即可达的。所有从M0可达的标识的集合称为可达标识集或可达集，记为R（M0）。314.4.5Petri网的行为特性可达树描述了从M0出发的所有可能启动序列的集合，它将R(M0)的各个标识作为节点，是以从M0到各个节点的发射系列为树枝画出的图。324.4.5Petri网的行为特性•可达性可描述制造系统这样的2个问题：（1）系统