生产计划与控制-制造系统的建模方法

第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随机型库存模型

1生产计划与控制--制造系统的建模方法第1页活动循环图法（ACD）--基本原理

离散事件系统建模方法之一——

活动循环图法（ActivityCycleDiagram，ACD）ACD认为：系统中每个实体都按照各自循环方式发生变化－－静止状态和活动状态。这两种状态在循环交替出现。ACD以○表示静止状态，以□表示活动状态，以有向箭头→表示静止状态与活动状态之间转换。

当系统中有多个实体时，有向弧就要使用不一样颜色或线型，以示不一样实体区分。2生产计划与控制--制造系统的建模方法第2页活动循环图法（ACD）--建模方法与建模过程

依据研究对象不一样，能够建立系统不一样层次ACD模型，即高层次模型能够深入分解为低层次模型。

ACD法重视“个体”活动，系统状态改变是全部个体状态改变集合。

ACD法缺点：当系统庞大、复杂时，活动循环图将十分复杂；

ACD法只描述系统稳态，而不研究系统瞬态（如动作开始、结束等）；

ACD法缺乏定量分析工具。3生产计划与控制--制造系统的建模方法第3页活动循环图法（ActivityCycleDiagram，ACD）ACD法中术语：

实体

活动

队列实体行为模式

直联活动和虚拟队列

合作活动4生产计划与控制--制造系统的建模方法第4页活动循环图法（ACD）--举例

一个由一位工人看管若干数控机床加工车间。工人任务是：（1）若刀具完好，则安装工件按运行按钮；（2）若若刀具损坏或需要更新，则先重装刀具，然后按运行按钮。上述工作仅当机床完成一次自动加工工序并停顿运行时工人才能执行。假定每台机床均可加工各种工件，不会发生刀具、工件短缺现象。希望经过建模仿真来研究工人忙闲率。

（1）识别实体和属性

①工人。“安装工件（RESET）”、“安装刀具（RETOOL）”、“其它活动（AWAY）”、“等候（WAITING）”。

②机床。：“安装刀具”、“安装工件”和“加工（RUNNING）”。5生产计划与控制--制造系统的建模方法第5页活动循环图法（ACD）--举例（2）画实体活动周期图绘制实体活动周期图必须遵照以下两个标准：①交替标准②闭合标准6生产计划与控制--制造系统的建模方法第6页活动循环图法（ACD）--举例（3）系统活动周期图7生产计划与控制--制造系统的建模方法第7页活动循环图法（ACD）--举例（4）增加必要虚拟实体（5）确定模型参变量和属性描述变量参数：机床数量；参变量：“累计加工工件数”和“累计加工时间”等；属性变量：“加工工件时间”、“安装刀具时间”、“安装工件时间”、“饮茶时间”等；服务规则：……8生产计划与控制--制造系统的建模方法第8页活动循环图法（ACD）--建模步骤（1）识别实体和属性；（2）分析各类实体活动与状态及其改变次序；（3）画出个实体ACD；（4）将实体ACD连接成系统ACD；（5）增添必要虚拟实体；（6）表明活动发生约束条件和占用资源数量；（7）给出模型参数、参变量计算方法及属性描述变量取值方法模型，以及排队规则。9生产计划与控制--制造系统的建模方法第9页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网生产计划与控制--制造系统的建模方法第10页4.4.1Petri网概述

离散事件系统建模方法之三——

Petri网（Petrinet）1962年，德国人CarlAdamPetri首次使用网状模型模拟通信系统，后发展成为Petri网理论。Petri网能够描述系统结构特征，并能对系统动态性能进行分析。与其它建模方法相比，Petri网建模含有下述优点：①Petri网含有准确图形化建模能力和严密数学基础，能够定性描述和定量分析系统中次序、并发、随机和冲突等事件关系；11生产计划与控制--制造系统的建模方法第11页

4.4.1Petri网概述②以Petri网模型为基础能够生成系统控制逻辑代码及仿真逻辑代码；③经过仿真或数学方法，由Petri网模型分析系统有界性、活性及可重用性等系统逻辑特征以及产量、设备利用率等性能指标。④Petri网提供了比其它建模工具更为丰富模型信息。80年代以后，Petri网开始应用于制造系统仿真、调度和控制建模以及系统性能分析中。12生产计划与控制--制造系统的建模方法第12页

4.4.2Petri基本概念

Petri网基本概念：resourcestatetransition

placeeventconditioncapability13生产计划与控制--制造系统的建模方法第13页

4.4.2Petri基本概念

Petri网定义：Petri网有两种表示方式：一个是形式定义，另一个是图形表示。

形式定义要求了Petri网结构、组成、节点间相互关系和动态行为。形式定义含有严密性、准确性、抽象性和概括性等优点，不过不形象、不直观，也不易于了解。Petri网图形表示则含有形象直观、易于了解特点，不过图形表示含有详细性，即Petri网图形往往与特定建模实例相对应。14生产计划与控制--制造系统的建模方法第14页

4.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)，建立了从库所到变迁、从变迁到库所单方向联络，而且要求同类元素之间不能直接联络；15生产计划与控制--制造系统的建模方法第15页

4.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网描述系统最基本概念是库所和变迁。

库所表示系统状态，变迁表示资源消耗、使用及使系统状态产生改变。16生产计划与控制--制造系统的建模方法第16页

4.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)}。17生产计划与控制--制造系统的建模方法第17页

4.4.2Petri基本概念

图形化表示：Petri网是由节点和有向弧组成一个有向图。

用圆圈“0”表示库所

用短竖线“|”或矩形“口”表示变迁以联结库所与变迁之间有向弧表示输入输出函数用令牌（token）(库所中黑点)表示库所中拥有资源数量。

库所中令牌分布决定变迁使能（enabled）和激发（fire），变迁激发又将改变令牌分布。

以变迁激发造成令牌在库所间流动，Petri网能够用于模拟系统动态运行过程，反应系统动态特征。18生产计划与控制--制造系统的建模方法第18页

4.4.2Petri基本概念

W—权函数（权重）——每个变迁发生一次引发相关资源数量上改变，w(p,t)或w(t,p)，缺省时，权重为1.K—容量函数——库所容量，标注在库所旁边。缺省时，权重为1.M—标识——库所中拥有资源（令牌）数量及其分布。标识以库所中黑点表示。19生产计划与控制--制造系统的建模方法第19页

4.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件。20生产计划与控制--制造系统的建模方法第20页

4.4.2Petri基本概念下列图是一个含有Wpetri网图。在这个图上弧线上标有数字。···················21生产计划与控制--制造系统的建模方法第21页

4.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表示库所容量。有时，允许一些库所容量为无穷，表示这些库所容量不会对系统行为组成限制。22生产计划与控制--制造系统的建模方法第22页

4.4.2Petri基本概念

上述定义给出了从结构到资源静态特征，再定义变迁发生条件和结果，组成了网系统完整定义。

权函数W要求每个变迁发生一次引发相关资源数量改变。普通地，对于任何（x，y）∈F，0<W<∞。

网系统动态规律称为变迁规则（transitionrule）。23生产计划与控制--制造系统的建模方法第23页

4.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下，有24生产计划与控制--制造系统的建模方法第24页

4.4.3Petri网运行规则M’为M之后继（successor）事实记作M[t>M’。

若M[t>,则t在M能够发生，同时将标识M改变为M后续M’。对于任何p∈P，M’为：（4）定义4：变迁发生后果-运行规则25生产计划与控制--制造系统的建模方法第25页

4.4.3Petri网运行规则下列图是一个petri网系统中变迁t激发前和激发后标识。生产计划与控制--制造系统的建模方法第26页

例：依据Petri网运行规则，按照t1t2t3t4次序，依次对图1中变迁发生进行检验。生产计划与控制--制造系统的建模方法第27页

4.4.4Petri网变迁间关系基于Petri网事件关系分析1.事件关系逻辑图a次序关系

b并发关系c冲突关系e迷惑关系d冲撞关系28生产计划与控制--制造系统的建模方法第28页

4.4.4Petri网变迁间关系基于Petri网事件关系分析1.事件关系逻辑图f死锁关系29生产计划与控制--制造系统的建模方法第29页Petri网可达性、有界性和安全性、活性以及可逆性。4.4.5Petri网行为特征1、

可达性可达性是Petri网一个主要特征。给定一个Petri网，已知初始标识M0能够抵达那些标识,或者给定某一标识，是否能够从初始标识经过一系列变迁抵达该标识。定义5

：若从初始标识开始实施一个变迁序列产生标识，则称该标识是从M0可达。若只要从开始实施一个变迁即可产生，则称是从M0马上可达。全部从M0可达标识集合称为可达标识集或可达集，记为R（M0）。生产计划与控制--制造系统的建模方法第30页4.4.5Petri网行为特征可达树描述了从M0出发全部可能开启序列集合，它将R(M0)各个标识作为节点，是以从M0到各个节点发射系列为树枝画出图。31生产计划与控制--制造系统的建模方法第31页4.4.5Petri网行为特征可达性可描述制造系统这么2个问题：（1）系统按照一定轨迹运行，系统能否抵达一定状态或不期望状态不出现，经典问题是生产调度计划验证，即按照一定生产计划进行生产，一定生产任务是否能够完成；（2）要求抵达一定状态，怎样确定系统运行轨迹，经典问题是生产调度问题。32生产计划与控制--制造系统的建模方法第32页4.4.5Petri网行为特征2、有界性和安全性定义6：

对于Petri网，若存在一个整数,使得M0任何一个可达性标识每个位置中标识数都不超K，则称Petri网为K-有界或简称有界。若K=1，则称此Petri网为安全。这种网每个位置或有一个标识，或没有标识。通常，位置用于表示制造系统中工件、工具、托盘以及AGV存放区（工件存放区就是缓冲区），还用于表示资源可利用情况。确认这些存放区是否溢出或资源容量是否溢出是非常主要。Petri网有界性是检验系统是否存在溢出有效尺度。当位置用于描述一操作，该位置安全性能够确保不会重复开启一正在进行操作。33生产计划与控制--制造系统的建模方法第33页4.4.5Petri网行为特征3、活性定义7:对于一变迁t∈T，在任一标识下，若存在一个变迁序列，该变迁序列实施使得此变迁t可实施，则称该变迁是活。若一Petri网全部变迁都是活，则该Petri网是活。

死变迁和锁死从反面描述Petri网活性。出现锁死原因是不合理资源分配策略或一些或全部资源耗尽。34生产计划与控制--制造系统的建模方法第34页在自动化制造系统中，许多资源是共享。在这么资源共享系统中，以下4个情况可能同时满足，从而导致锁死：1）互斥：一个资源不可认为2个或2个以上过程同时使用，一过程排斥其它过程对于该资源占用；2）占用且等候：一过程已占用某一或某些资源，同时又在请求占用其它资源；3）无抢占：已分配给某一过程资源不能从该过程中抢走，除非该过程使用此资源完成后释放；4）循环等候：2个或更多过程排成一个链，链上每个过程都在等候一个正在被链上下一个过程占用资源。除非系统控制软件含有探测和恢复系统功效，最初发生在子系统中锁死可能传输到系统大部分，从而造成系统完全停顿。4.4.5Petri网行为特征生产计划与控制--制造系统的建模方法第35页4.4.5Petri网行为特征36生产计划与控制--制造系统的建模方法第36页4.4.5Petri网行为特征37生产计划与控制--制造系统的建模方法第37页4.4.5Petri网行为特征4、可逆行定义8

：一Petri网，若对于每一个标识M∈R（M0），M0都是从M可达，则称该Petri网是可逆。含有可逆性petri网被称为可逆网。所以，一个可逆网能够返回初始标识或初始状态。在许多实际应用中，往往只要求系统回到某个特定状态（称为为主宿状态M’），而无需回到初始状态。对于R（M0）每个标识M，主宿状态M’都是可达。可逆性意味着模型能够本身初始化。这对于自动从差错中恢复是极为主要。38生产计划与控制--制造系统的建模方法第38页4.4.5Petri网行为特征上图是一个可逆Petri网。在这个网中，初始标识M0(0,0,1,1,1)经过变迁序列t2t1t3t4能够回到初始标识。M

(0,0,1,1,1)Mt2(1,1,0,1,1)Mt1(1,0,1,1,1)Mt3(0,0,1,0,2)Mt4(0,0,1,1,1)39生产计划与控制--制造系统的建模方法第39页4.4.5Petri网行为特征5、可覆盖性假如一个Petri网有没有限多个可达标识，为了用有限个图来表示它，引入符号ω来表示无限，对每个正整数n(ω>n)。这么，就能够在一个有限图中，使每一个标识用图中一个节点表示，这么图称为覆盖图。定义9：在一个Petri网中，一个标识M称作可覆盖，仅当在R(M0)中存在一个标识M’，使得对于网中每个库所p，有M’(p)≥M(p)成立。备注：ω有以下性质：

对每个整数n，有ω>n，ω+n>ω，ω-n=ω，ω≥ω40生产计划与控制--制造系统的建模方法第40页4.4.5Petri网行为特征41生产计划与控制--制造系统的建模方法第41页4.4.5Petri网行为特征6、同时距离系统一个主要特征是事件间发生依赖程度，即某个事件发生依赖于其它事件发生。比如同时发生、交替发生或以任意次序发生，极端情况是完全独立。定义10：事件t1和t2间同时距离d12：d12=max|n(t1)-n(t2)|。其中n(t1)和n(t2)分别为事件t1和t2在开启序列σ中发生次数(σ为起始于R(M0)中任何标识M一个开启序列)。同时距离是对未引入“时间”概念系统动态行为一个度量。42生产计划与控制--制造系统的建模方法第42页4.4.5Petri网行为特征并发系统Petri网上图表示是一个并发系统，t2，t3能够同时发生，此时d23=0；也能够一前一后发生，此时d23=1.43生产计划与控制--制造系统的建模方法第43页4.4.5Petri网行为特征并发系统Petri网d12=ω,两组事件异步；d12<ω,两组事件以d12为距离相互同时；d12=0,两组事件在时间和空间上一起发生；d12=1,两组事件必须交替发生；44生产计划与控制--制造系统的建模方法第44页4.4.6Petri网行为特征分析方法对于行为特征，当前较成熟分析方法只能对部分特征进行分析，对其它特征进行分析方法仍在研究之中。Petri网行为特征分析方法分为三类：（1）分层或化简；（2）可达性（可覆盖性）树；（3）矩阵方程求解。45生产计划与控制--制造系统的建模方法第45页4.4.6Petri网行为特征分析方法Petri网可达树构建算法：让初始标识M0为树根，并作上“new”记号；若“new”标识存在，则重复以下各步，不然终止。选择某一“new”标识M。3.1）若M与树中间已经有其它标识相同，则将其记为“old”，然后转向其它“new”标识。3.2）若在M下无变迁可实施，则将M记为“deadend”。对于M下可实施变迁t，做以下事情：

4.1）实施t由M产生标识M’；4.2）若在从树根至M’路径上存在一标识M’’，使得M’覆盖

M’’，（即M’>M’’），则对于那些使M’（p）>M’’（p）成立p：用ω取代M’（p）；4.3）以M’为一节点，从M至M’画一有向线，将其记为t，并将M’记为“new”；除去M“new”标识。（1）可达性树分析法46生产计划与控制--制造系统的建模方法第46页4.4.6Petri网行为特征分析方法Petri网可达树构建算法：（1）可达性树分析法47生产计划与控制--制造系统的建模方法第47页4.4.6Petri网行为特征分析方法基于可达树，能够做以下分析：1）当且仅当树中全部节点上均不出现ω时，Petri网是有界；此时，能够在树中找出某一位置中最大托肯数K，则该位置是K-有界；若K是树中全部位置中最大托肯数，则该Petri网是K-有界。2）当且仅当树中全部节点仅包含0或1时，该Petri网是安全。3）没有任何死点包含ω，则树中死点个数就是Petri网死标识数目；若树中死点之一包含ω，则Petri网包含无数个死标识；4）某变迁在树中不出现，则该变迁是死变迁；5）在不包含ω树中，若给定任何两个节点之间，都存在一有向路径，在该路径上全部变迁都出现，则该Petri网是活6）在无ω出现树中，若从任何节点到根节点之间都存在一有向路径，则该Petri网是可逆。48生产计划与控制--制造系统的建模方法第48页4.4.6Petri网行为特征分析方法（2）状态方程分析法—关联矩阵49生产计划与控制--制造系统的建模方法第49页4.4.6Petri网行为特征分析方法例：在下列图中，初始标识为M0=[1,0,0]T,输入函数矩阵、输出函数矩阵和关联矩阵分别为：C-(p1,t0)=1,C-(p2,t0)=0,C-(p3,t0)=1,C-(p1,t1)=1,C-(p2,t1)=0,C-(p3,t1)=0,C-(p1,t2)=0C-(p2,t2)=1,C-(p3,t2)=1,C-(p1,t3)=1C-(p2,t3)=0,C-(p3,t3)=0,C+(p1,t0)=0,C+(p2,t0)=0,C+(p3,t0)=0,C+(p1,t1)=0,C+(p2,t1)=0,C+(p3,t1)=1,C+(p1,t2)=0,C+(p2,t2)=0,C+(p3,t2)=1,C+(p1,t3)=1,C+(p2,t3)=1,C+(p3,t3)=0,生产计划与控制--制造系统的建模方法第50页4.4.6Petri网行为特征分析方法例：在下列图中，初始标识为M0=[1,0,0]T,输入函数矩阵、输出函数矩阵和关联矩阵分别为：生产计划与控制--制造系统的建模方法第51页4.4.6Petri网行为特征分析方法（2）状态方程分析法—状态方程52生产计划与控制--制造系统的建模方法第52页4.4.6Petri网行为特征分析方法（2）状态方程分析法—状态方程53生产计划与控制--制造系统的建模方法第53页4.4.6Petri网行为特征分析方法（2）状态方程分析法—状态方程在可达性分析中应用例：在下列图中生产计划与控制--制造系统的建模方法第54页4.4.6Petri网行为特征分析方法（2）状态方程分析法—状态方程在可达性分析中应用生产计划与控制--制造系统的建模方法第55页4.4.6Petri网行为特征分析方法（2）状态方程分析法—状态方程在可达性分析中应用生产计划与控制--制造系统的建模方法第56页4.4.6Petri网行为特征分析方法（2）状态方程分析法—状态方程在可达性分析中应用生产计划与控制--制造系统的建模方法第57页4.4.6Petri网行为特征分析方法（2）状态方程分析法—状态方程在可达性分析中应用生产计划与控制--制造系统的建模方法第58页4.4.6Petri网行为特征分析方法（2）状态方程分析法—状态方程在可达性分析中应用生产计划与控制--制造系统的建模方法第59页4.4.6Petri网行为特征分析方法（2）状态方程分析法—状态方程在可达性分析中应用生产计划与控制--制造系统的建模方法第60页4.4.7Petri网分类依据容量函数K和权函数W取值范围不一样，能够将Petri网系统分为三种类型：1）K≡1和W≡1.此时库所元素只能有“有令牌”和“无令牌”两种状态。因而能够了解为“真”与“假”两种状态布尔运算。网论中将这种库所称为条件，只与条件关联变迁称为事件。由条件和事件组成网系统称为基本Petri网系统。2）K≡ω和W≡1.这类系统称为Petri网网系统，也称库所/变迁网（P/T网）。3）K和W为任意函数。将K和W为任意函数系统称为库所/变迁系统（P/T系统）。

普通地，将P/T网和P/T系统统称为低级Petri网系统（LLPT）61生产计划与控制--制造系统的建模方法第61页4.4.8Petri网建模举例62生产计划与控制--制造系统的建模方法第62页4.4.8Petri网建模举例63生产计划与控制--制造系统的建模方法第63页4.4.8Petri网建模举例t`1264生产计划与控制--制造系统的建模方法第64页4.4.9高级Petri网前面接收基本Petri网系统（低级Petri网系统）主要有两大不足：（1）表示能力有限。稍微复杂一点系统就要使用大量库所和变迁，由此所引发“组合爆炸”