生产系统建模与仿真.ppt

,生产系统建模与仿真ProductionSystemModeling（2）T=t1,tm是变迁的有限集合，m(0)为变迁的个数；PT=，PT；（3）I：PTN是输入函数，它定义了从P到T的有向弧的重复数或权(Weight)的集合，这里N=0,1,为非负整数集；（4）O：TPN是输出函数，它定义了从T到P的有向弧的重复数或权的集合。,在表示PN结构的有向图中，库所用圆表示；变迁用长方形或粗实线段表示；若从位置p到变迁t的输入函数取值为非负整数w，记为I(p,t)=w，则用从p到t的一有向弧并旁注w表示；若从变迁t到位置p的输出函数取值非负整数w，记为O(p,t)=w，则用从t到p的一有向弧并旁注w表示。特别地，若w=1，则不必标注；若I(p,t)=0或O(p,t)=0，则不必画弧。I与O均表示为nm非负整数矩阵，O与I之差C=O-I称为关联矩阵。,Petri网的实例,例：一PN结构如图所示。按照PN的定义，该PN结构可描述如下：P=p1,p2,p3；T=t1,t2；I(p1,t1)=1;I(p2,t1)=1;I(p3,t1)=0;I(p1,t2)=0;I(p2,t2)=0;I(p3,t2)=1;,O(p1,t1)=0;O(p2,t1)=0;O(p3,t1)=1;O(p1,t2)=0;O(p2,t2)=1;O(p3,t2)=0.,输入函数：,输出函数：,关联矩阵：,第四章离散事件仿真的逻辑分析Petri网,在PN结构中，p表示了离散事件系统(DES)的局部状态，P表示DES的整体的状态；T表示其所有可能的事件；某一库所所表示的局部状态实现情况(是否实现？实现了几次？)用库所中所包含的标记(Token)数目m(p)来表示(用库所p中圆点或数量表示标记)。特别地，m(p)=0，则p中无圆点，表示p所代表的局部状态目前没有实现。t与t分别表示t的所有输入与输出库所的集合；p与p分别表示库所p的输入与输出变迁；I与O描述所有可能的状态与事件之间的关系，其中I描述事件发生的前提状态(因)，而O描述事件发生所实现的状态(果)。,Petri网有哪些功效？,Petri网的实例(续),例如，图题中：（1）从p1与p2到t1有弧连接，既I(p1,t1)0，I(p2,t1)0，说明t1所表示的事件的发生以p1与p2所表示的局部状态为前提条件；（2）而从p3到t1无弧连接，既I(p3,t1)=0，说明t1所表示的事件的发生不取决于p3所表示的局部状态；（3）从t1到p3有弧连接，即O(p3,t1)0，表明t1所表示的事件发生将影响p3所表示的局部状态；,（4）而从t1到其它库所无弧连接，表明t1所表示的事件发生将不影响这些库所所表示的局部状态。,Petri网的五要素定义,标识PN为一5要素：PN=PNS,m=P,T,I,O,m此处：(1)PNS=P,T,I,O为PN结构，它由Petri网的四要素定义给出；(2)m:PN为标识PN的标识，它为一列向量，其第i个元素m(pi)表示第i个库所中的标识数目。m=(m(p1),m(p2),m(pn)T特别地，DES的初始状态用初始标识表示，记为m0。相同结构的标识PN不是唯一的？,Petri网的实例(续),例题如图（包括库所中的圆点）一个标识PN，正规地描述如下：PN=P,T,I,O,m0*P,T,I,O见前例。*m0=(1,1,0)T,其中第1个元素为m(p1)=1,第2个元素为m(p2)=1,第3个元素为m(p3)=0,第四章离散事件仿真的逻辑分析Petri网,Petri网的使能？在DES中某一事件必须在所有前提条件（状态）得以满足（实现）的情况下才可能发生。有时，要求某一前提条件（状态）必须满足多次（实现多次）。在DES的Petri网中，我们以变迁t表示一事件，用变迁的使能(Enabling)表示事件因前提条件得以满足而能够发生。我们还用t的输入库所（通过指向t的弧连接的库所）表示该事件的发生所需要的前提局部状态，用由输入库所至t的输入函数定义这些要求局部前提状态实现的次数；而局部状态的实现情况由库所中所包含的标识数目来表示。,因此，变迁t的使能不仅与其输入函数有关，而且与其所有输入库所中的标识数目有关。为此，引入以下变迁使能规则。,使能的例子,Petri网的使能定义一变迁tT在标识m下使能，当且仅当：pt:m(p)I(p,t)。例如：在上例中，变迁t1的使能t1=p1,p2，由于m(p1)=1I(p1,t1)=1，m(p2)=1I(p2,t1)=1，因此变迁t1使能的；而t2=p3，由于m(p3)=0m。,状态转换的例子,在右上图所示的PN中，在m0=(1,1,0)T下使能的t1激发后，将产生新的标识m1(见右下图)：m1(p1)=m0(p1)-I(p1,t1)+O(p1,t1)=1-1+0=0；m1(p2)=m0(p2)-I(p2,t1)+O(p2,t1)=1-1+0=0；m1(p3)=m0(p3)-I(p3,t1)+O(p3,t1)=0-0+1=1；m1=(0,0,1)T,上例的计算，似乎给我们告诉了些东西：,几种特殊的PN:若PN的所有变迁至多有1个输入弧或输出弧，即I:PT0,1,O:TP0,1，则此PN称为普通PN（OrdinaryPetrinet）。若PN无自闭环，即某一库所同时是某一变迁的输入与输出库所，则此PN称为纯PN（PurePetrinet）。若PN的每一库所都恰好有1个输入变迁与1个输出变迁，即pP:|p|=|p|=1，则该PN称为标识图(Markedgraphs)。若PN的每一变迁都恰好有1个输入库所与1个输出库所，tT:|t|=|t|=1，则该PN称为状态机(Statemachine)。,第四章离散事件仿真的逻辑分析Petri网,若干制造系统的基本PN模型,缓冲区模型考虑两台机器M1与M2之间的缓冲区B，假设它能够存储k个工件。,t1：M1结束当前工件的加工并将该工件放入B中；t2：从B中取出一个工件并在M2上开始加工；pv：B的剩余容量；pb：B中存放的工件数量；puf：机器M2是空闲的；,当缓冲区满时，pb中容纳k个标识，而pv中无标识。此时t1被抑制而不能激发，机器M1堵塞(Blocked)。一旦一个工件从缓冲区移至机器M2，pv收到1个标识，则t1立即使能，生产得以恢复。,PN的抑制弧（Inhibitorarc）,按输入函数的定义，pb中至少有k个标识是t1使能条件。但是，抑制弧的作用应理解为：一旦抑制弧连接的输入库所中拥有与抑制弧的权相等数量的标识，则该抑制弧将抑制该变迁的激发。,抑制弧用一端带由小圆并旁注权值k的弧表示。,若干制造系统的基本PN模型,存储区溢出（Overflow）：当缓冲区存满工件时，其存储容量已耗尽的现象。当存储区溢出时，其前端机器被堵塞。发生溢出时，期望提供存储区溢出的信息，并改变堵塞在机器中工件的路径，将其送至其它机器，而不是原路径上的机器M2。,变迁toi的激发将输出溢出指示。由于连接toi与pv的抑制弧的权为0，因此只要pv中包含1个及以上的标识(表明储料取仍然有存储空间)，则toi将被抑制激发，不产生溢出指示。当p1中包含1个标识(表示1工件被机器M1加工完毕，等待从M1移出)，且pv中无标识(表明缓冲区堆满工件)，toi立即激发，输出溢出指示，将p1中的标识送至代表其它路径的入口(图中没有画出)，而不是pb。,若干制造系统的基本PN模型,FCFS的工件队列PN模型传送带是典型的先来先享受服务(First-Come-First-Serve,FCFS)工件队列的例子，因为先放置到传送带上的工件先从传送带的另一端离开。工件在传送带上传送的过程可看作是暂时储存在传输带上。,ps表示工件在传送之中，ta表示将工件放入传送带上。传送带所能够传送的最多工件数由ta的抑制弧的权N定义。只要ps中的标识数不超过N，抑制弧不起作用。此时，一当工件到达，ta立即激发，将1标识放入ps中，表示工件在传送之中。只要ps中有标识，一旦pd中有1标识(表示请求将1工件从传输带上移走)，则td激发，从ps中取走1标识，一工件离开传送带。,若干制造系统的基本PN模型,描述制造系统的并行与同步特征PN模型制造过程中，许多操作同时进行。例如，某一部件由2个零件装配而成，2个零件分别由2条独立的生产线加工，则装配只能在每一零件加工完毕后才能进行。2个零件的加工过程是并行的(Concurrent)，通过装配的开始而同步(Synchronized)。,左图所示的PN，假设p1中的标识表示放置在一托盘上的2个工件到达，t1表示拆卸操作：将一个工件从托盘上移走并放入p2中，如此同时将另一工件连同托盘送至p3。可以看到PN中的一个初始标识现在变为2个标识，也就是说，网中总标识数是可变的。还发现该模型中从t1分出2条不同的路径，每一路径代表一个加工过程，它们是并行的；两个过程在t3处合并从而同步。,若干制造系统的基本PN模型,制造系统另一常见的现象是两个以上的操作共享同一资源，例2台机器共享一套刀具。对于资源的竞争将导致冲突(Conflict)。在PN中，资源表示为库所，操作表示为变迁。因此，在PN中，资源的冲突表现为某一库所被2个及其以上变迁共享同一个输入库所。根据标识图的定义，它不能描述资源冲突。,左图中2个加工过程都需要资源p4进行各自的操作，这是一典型的冲突问题。如前面刚提到，t1与t3同时使能，但只有二者其一能够激发。出现冲突时，必须作出决策一决定谁优先激发。最简单的方法是采用随机确定方法。若t1在冲突中获胜，则t1激发并消耗p4中的标识。最终，t2激发从而将1标识放回p4，表示资源得以释放。,基本PN性能,系统的特性可分为行为（Behavioral）与结构(Structural)特性。行为特性是PN与初始标识有关的性能；而结构特性与初始标识无关，它们取决于PN的拓扑结构。重要的结构与行为特性:可达性(Reachability);有界性(Boundness);安全性(Safeness);守衡性(Conservativeness);活性(Liveness);可逆性(Reversibility)。,基本PN性能,可达性是PN的一个重要行为特性:给定一PN，我们期望知道从初始标识m0可以到达哪些标识;给定一标识mt，是否可以激发一系列变迁从初试标识m0到达该标识。定义:若从m0始标识开始激发一个变迁序列产生标识mr，则称mr是从m0可达的。若只要从m0开始激发一个变迁即可产生mr，则称mr是从m0立即可达的(Immediatelyreachable)。所有从m0可达的标识的集合称为可达标识集或可达集，记为R(m0)。一般地，从m0到mr所激发的变迁序列表示为:srtj1,tjr,这里j1,jr为1到m之间的整数。从m0激发sr产生mr表示为：m0srmr。,例,在右图的PN中，m0=(1,0,0,1,1,0,0)T，m0s4m4，这里m4=(0,0,1,1,0,0,1)T，s4=t3,t4,t1,t2。,对于每一个激发的变迁序列sr，都可以关联一个m1激发向量vr，该向量的第i个元素，对应着变迁ti在sr中出现的次数ni。一般地，vr=(n1,nm)T。对于一定的vr，其对应的激发的变迁序列可能不是唯一的。例如，上面例子中提到的从m0到达m4，v4=(1,1,1,1)T所激发的对应变迁序列就有t3,t4,t1,t2与t1,t2,t3,t4两个。,基本PN性能,可达性可描述制造系统的两个问题：(1)系统按照一定的轨迹运行系统是否能够实现一定的状态。典型的问题是生产调度计划的验证，即按照一定的生产调度计划进行生产，一定的生产任务是否能够得以完成；(2)要求到达一定的状态如何确定系统的运行轨迹，典型的问题是生产调度问题。第一个问题可以描述为：给定sr、初始标识m0以及期望达到的标识mr，则有m0srmr，若mr=mr则答案是肯定的；若mrmr，则答案是否定的。第二个问题可以描述为：给定m0与mr，寻找sr，使得m0srmr成立。必须指出sr可能不是唯一的，通常都在一定的准则下选取优化的sr。,基本PN性能,有界性与安全性:,定义:给定PN=(P,T,I,O,m0)以及其可达集R(m0)，对于库所pP，若mR(m0)，有m(p)k，则称p是k-有界的，此处k为正整数；若PN的所有库所都是k-有界的，则PN是k-有界的。特别地，k=1时，即当某库所或PN是1-有界的，则称该库所或PN是安全的。若对与任意初始标识m0，PN都是k-有界的，则PN是结构有界的(Structurallybounded)。,基本PN性能,意义：库所用于表示制造系统中的工件、工具、托盘以及AGV的存放区（工件的存放区就是缓冲区），还用于表示资源的可利用情况。确认这些存放区是否溢出(Overflow)或资源的容量是否溢出是非常重要的。,PN的有界性是检查系统是否存在溢出的有效尺度：当库所用于描述一操作，该库所的安全性能够确保不会重复启动一正在进行的操作。我们可直观地看到，右图所示的PN是1-有界的，因此它是安全的。,定义:对于一变迁tT，在任一标识mR下，若存在一变迁序列sr，该变迁序列的激发使得此变迁t使能，则称该变迁是活的(Live)。若一PN的所有变迁都是活的，则该PN是活的。死变迁(Deadtransition)或者死锁(Deadlock)从反面描述PN的活性。若存在mR，不存在从m开始的变迁序列，该序列的激发使得t使能，则变迁t为死变迁。若存在mR，在此m下无任何变迁使能，则称PN包含一死锁、该标识为死标识(Deadmarking)。,基本PN性能,死变迁(Deadtransition)或死锁(Deadlock),基本PN性能,出现死锁的原因是不合理的资源分配策略或某些或全部资源的耗尽。在自动制造系统中，许多资源（如机器、包括AGV与机器人在内的物料搬运设备、以及缓冲区存放空间）是共享的。在这样的资源共享系统中，下列4个情况可能同时满足，从而导致锁死：互斥：一资源不可以为2个或2个以上过程同时使用，一过程排斥其它过程对于该资源的占用。占用且等待：一过程已被许可占用某一或某些资源，同时又在请求占用其它资源。无抢占：已分配给某一过程的资源不能从该过程中抢走，除非该过程使用此资源完毕后而释放。循环等待：2个或更多过程排成一个链，链上每一过程都在等待一个正在被链上下一个过程占用的资源。,制造系统出现死锁的例子,柔性制造系统的某一机器入出缓冲区占用着一托盘，其上存放着已加工完毕的零件。而另一存放待加工工件的托盘也被自动导向车(AGV)传送至该入出缓冲区。假设入出缓冲区只能存放一个托盘，而AGV也只能放置一个托盘。此时，存放着已加工的零件托盘不能从入出缓冲区移至AGV上，AGV也不能进入缓冲区将其上面存放着的待加工的工件的托盘送至入出件堆放区。缓冲区与AGV为2个资源，将托盘从缓冲区移至AGV上与将托盘从AGV上送至缓冲区为2个过程。前者占用着缓冲区而等待着AGV，而后者占用着AGV而等待缓冲区，上述4个条件同时成立，因而出现死锁。,基本PN性能,可逆性(Reversibility)与主宿状态(Homestate)制造系统研究中的一个重要问题是如何使得系统自动地从差错中复原。例如，在利用机器人装配中，零件间可能无法配合，从而出现差错。我们希望在不需要人为干预的情况下，就能够从这一差错中复原。若一PN用于描述装配操作，该操作配备有可行的恢复方案，则可逆网意味着自动地从差错中复原是可能的。定义：一PN是可逆的，若对于每一标识mR(m0)，m0R(m)。标识mrR(m0)称为主宿状态，若mR(m0)，mr是从m可达的。,基本PN性能,由上述定义，可逆性表示初始标识m0是从所有可达标识可达的。这意味着模型可以自身初始化，它对于系统自动地从差错中恢复过来是极为重要的。因为经过有限步骤，系统将回到期望的状态。因此，若PN模型不是可逆的，则控制器应该力图使之可逆；若无法做到，则不得不认为干预。可逆性还确保系统的周期特性，例如重复制造系统。这一特性与可逆性与主宿状态密切相关。可逆行是主宿状态的特例，若mr=m0，即若主宿状态为初始标识，则系统是可逆的。还必须注意，若PN包括一死锁，则它不可能是可逆的。一般地，有界性/安全性、活性、以及可逆性彼此间是独立的。一个PN可以是活的、有界的、可逆的，活的、有界的、不可逆的，或者不是活的、无界的、不可逆的，共有8种组合。,基本PN性能,PN不是活的，是有界的，是不可逆的。,基本PN性能,定义：对于一PN=(P,T,I,O,m0)，若存在一矢量w=(w1,w2,wn)T且wi0,i=1,2,n，使得对于所有mR(m0)：wTm=wTm0，则称该PN相对于矢量w守衡。若PN相对于w=(1,1,1)T守衡，即对于所有mR(m0)：，则称PN为严格守衡的。定义：对于一PN=(P,T,I,O,m0)，若存在一矢量w=(w1,w2,wn)T且wi0,i=1,2,n，但w0，使得对于所有mR(m0)：wTm=wTm0，则称该PN相对于矢量w部分守衡。,基于PN制造系统性能分析,基于可达图与覆盖图的分析,从初始标识m0开始，期望到处PN所有可能的标识，这些标识通过变迁而关联。我们将所有标识以及产生这些标识的变迁用一图形表示，图中的节点为标识，节点之间用表示变迁的带箭头的线或弧连接，带箭头的线起端所连接的标识通过由该线所代表的变迁的激发，产生该线末端所连接的标识。这样的图称为可达图。若PN是无界的或PN所描述的系统具有无限个状态，则可达图将无止境扩展。取而代之，我们将构建覆盖树(Coverabilitytree)，它是无限可达图的有限表达方法。,基于PN制造系统性能分析,定义：标识m2覆盖m1，即m2m1，若pP：m2(p)m1(p)。移入一特别符号，它代表“准-无限大”，用于表示任意大的标识数。遵循以下四个运算规则，使得对于任意正数k，都有：(1)km），则对于那些使m(p)m(p)成立的p：用取代m(p)；3)以m为一节点，从m至m画一有向线，将其并记为t，并将m记为“new”；5.除去m的“new”标志；,基于PN制造系统性能分析,例:构建图(a)所示的具有无限储料空间之间缓冲区的二机器生产线的覆盖树。初始标识为m0=(10010)T,在m0下只有t1使能。激发t1将产生m1=(01010)T。由于m1即不大于m0又不等于m0，因此将记为“new”，并从m0至m1画一有向线并记为t1。,m1为当前唯一的“new”标识，在m1下只有t2使能。激发t2将产生标识m2=(10110)。由于m2m0且m2(p3)m0(p3)，因此，根据步骤4.2，在m2=(10110)T中用取代m(p3)，从而得到标识m2=(1010)T。,在当前唯一的“new”标识下，t1与t3使能。激发t1将产生m3=(0110)T，它不等于从m0至m3路径上任何标识。虽然它大于m1=(01010)T，但没有必要进行步骤4.2，原因是其第3个元素已经是。,激发t3产生m4=(10-101)T=(1001)T（根据-k=）。,目前存在m3=(0110)T与m4=(1001)T2个“new”标识。在m3=(0110)T下，t2与t3使能。激发t2产生m5=(01+110)T=(0110)T，它等于先前产生的m3，因此记为“old”。激发t3产生m6=(0101)T，它是一“new”标识。,目前仍然存在2个“new”标识：m3=(1001)T与m6=(0101)T。继续进行，直至无“new”标识存在.,基于PN制造系统性能分析,根据上述方法，由图(b)所示的覆盖树可知，图(a)所示的PN是无界的，且除了p3其它库所是安全的。还可知该PN不包含死变迁，因为所有变迁都在树中出现。由于树中出现，我们无法作出该PN是否活的与可逆的结论。,基于PN制造系统性能分析,基于覆盖树或可达树，可以做如下分析：当且仅当树中所有节点上均不出现时，PN网是有界的；此时，我们可以在树中找出某一库所中最大的标识数，比如说k，则该库所是k-有界的；若k是树中所有库所中的最大的标识数，则PN是k-有界的。当且仅当树中所有的节点上仅包含0或1时，则PN网是安全的。没有任何死点包含，则树中死点的个数就是PN死标识的数目；若树中死点之一包含，则PN包含无数个死标识；若某变迁在树中不出现，则该变迁是死变迁。在不包含的树中，若给定任何两个节点之间，都存在一有向路径，在该路径上所有变迁都出现，则PN是活的。在无出现的树中，若从任何节点到根节点之间都存在一有向路径，则PN是可逆的。上述(5)仅适用于不包含的覆盖树，即可达树的活性分析（也即有界PN的活性分析），这是因为在出现的覆盖树中，由于的移入而损失一些信息。有研究表明，两个不同的PNs具有相同的覆盖树，其中之一个PN是活的，而另一个不是活的3。,基于PN制造系统性能分析,定义：一PN是关于初始表示m0一致的，若其覆盖树上存在一有向回路（不必要是基本回路），所有变迁都在起上出现至少一次。若该回路，只包含某些变迁，则为部分一致的。定义：一PN是关于初始标识m0重复的，若其覆盖树上存在一有向回路（不必要是基本回路），该有向回路包含所有的变迁无数次。若该有向回路经包含某些变迁，则为部分重复的。,连贯性(Consistency)与重复性(Repetitiveness)有向回路(Directedcircuit)的概念：一有向回路为从某一节点(库所或变迁)出发并返回该节点的路径。若在有向回路上除了起始节点外，其它的节点出现的次数不多于一次，则该有向回路称为基本有向回路或基本回路,基于不变量的PN分析：是一种基于矩阵线性代数。这一方法的优点是依据简单的线性代数方程，就能正规地确定PN性能。这里所建立的线性代数方程决定着由PN所描述的分布系统的动态特性，这与同自动控制理论中状态方程的概念，但其解局限于非负整数，因为它表示某一变迁激发的次数。用mk表示第k次运行(k0)后PN的标识(一次运行就是激发一个变迁序列，它可能包括若干变迁的激发，一个变迁可能在一次运行中激发多次)，则第k+1次运行后PN的表示为：mk+1=mk+Cvk，k0(1)这里vk为激发记数向量，它为一(m1)向量，其第i个元素表示在第k+1次运行中变迁ti激发了的次数。上式称为PN的状态方程。特别地，若一次运行仅包含激发某一变迁1次，即vk只有1个元素为1，而其它元素均为0，则上式将表示PN的激发规则。mk+Cvk0，对于所有k0上式可用于检验在mk下激发某一变迁序列是否合法。,基于PN制造系统性能分析,定义3：P-不变量为一(n1)非负整数向量x，并满足：xTC=0;(2)而T-不变量为(m1)非负向量y，并满足：Cy=0(3)将(1)式两边左乘xT，得到xTmk+1=xTmk+xTCvk。由(2)，则有xTmk+1=xTmk,k0(4)特别地，从k=0开始递推有：xTm0=xTm1=xTm2=xTm3=xTm=常数，即xTm=xTm0=常数(5)上式表明由P-不变量加权的所有库所中初始标识数之和为常量。或者说，P-不变量的非0元素是相应的库所中标识数的权值，使得在任何从m0可达的m下所有库所中的标识加权和为常数。称这些库所被该P-不变量覆盖。,基于PN制造系统性能分析,假设经过激发某一变迁序列（该序列记数向量为v），PN从初始标识又返回初始标识。则由(1)有：m0=m0+Cv必有Cv=0。因此，v为一T-不变量，即y=v。这表明T-不变量中的非负元素为将PN的标识从m0出发经一系列变化而返回m0的变迁序列中相应的变迁激发的次数。PN的不变量不是唯一的。那些不是其它不变量线性组合的不变量为基本不变量。由线性代数可知，若关联矩阵C的秩为r=rank(C)，则其有(n-r)个基本P-不变量与(m-r)个T不变量。P-不变量与T-不变量可以通过求解线性方程xTC=0与Cy=0来获得。,基于PN制造系统性能分析,例：求下图所示PN的不变量。该PN表示两个过程（t1-t2与t3-t4），其中前一过程受第二个过程影响，即只有当第二个过程进行之中（p4中包含标识），第一个过程才能进行。,由于rank(C)=2，因此存在两个基本P-不变量与两个基本T-不变量。,求解xTC=0得：x2=2x1与x4=x3。令x1=x3=1，则x2=2，x4=1，得到P-不变量(1211)T；令x1=1且x3=0，则x2=0，x4=1，得到P-不变量(1200)T。,求解Cy=0得：y=y，y4=y3。令y1=y3=1，则得到T-不变量(1111)T；令y1=0，y3=1，则得到T-不变量(0011)T。,基于PN制造系统性能分析,寻求不变量可帮助分析PN的某些性能。例如，若PN的每一库所都被一P-不变量覆盖，则PN是有界的。然而，这一方法的应用是很有限的，原因是它不能提供分析一般PN的所有信息，它仅适用于普通PN。在上例中，由于PN被正的P-不变量(1211)T覆盖，因此它是有界的。我们还可找到一变迁序列，如t3,t1,t2,t4，它的激发使PN的标识从m0经一系列变化又回到m0。该变迁序列激发记数向量为(1111)T，恰好等于上面求的的T-不变量(1111)T。基于关联矩阵，可以分析PN的某些结构性能：（1）若只要存在一(n1)正实数向量x，使得xTC0，则PN是结构上有界的；（2）若只要存在一(n1)正实数向量x，使得xTC=0，则PN是结构上是守衡的。,基于PN制造系统性能分析,例如：上例的PN，存在x=(1211)T0，满足xTC=0，因此该PN是结构上有界且守衡的。,基于PN制造系统性能分析,如图所示，一生产单元由两台机器（M1与M2）组成，它们公用一机器人R上下工件。一输入传输带输送载有工件的托盘（1个托盘上仅载1个工件），机器人R从其上抓取工件并装载到机器M1上；机器人R将成品从机器M2上卸下并送到输出传输带上，由其送走。2台机器间由一缓冲区，可存放2个中间工件。共有3个托盘可使用，工件安装在其中之一上，先后由机器M1与M2加工。加工完毕后，托盘与成品自动脱离，然后转载新的工件，再回到输入传输带上。,一个生产单元的PN建模,可按以下步骤建立系统PN模型：1.确定系统的所有资源：3个装载工件的托盘、机器M1与M2，机器人R，及缓冲区；2.确定与各资源有关所有活动（操作）及其先后顺序并建立其子模型2.1装载工件的托盘历经的状态与活动；2.2机器M1、M2历经的活动与状态；2.3缓冲区历经的活动与状态；2.4机器人历经的活动与状态；(3)根据各资源之间的关系，合并所有子模型，得到系统模型。,一个生产单元的PN建模,装载工件的托盘历经以下状态与活动：被R装载至机器M1：t1其上工件被M1加工：p2由R从M1上卸载：t2中间工件的托盘存放于缓冲区中：p3由R装载至M2：t3其上中间工件被M2加工：p4由R从M2上卸载：t4,注：p1代表载有工件的托盘可使用,返回,一个生产单元的PN建模,机器M1/M2历经以下活动与状态：R装载工件至机器M1或M2（由t1、t3分别表示）；工件被M1或M2加工（由p2、p4表示）；,注：p5、p7分别表示机器M1、M2可使用；,返回,一个生产单元的PN建模,缓冲区历经以下活动与状态:R将工件送入缓冲区（由t2表示）；载有中间工件的托盘存放于缓冲区中（用p3表示）；R将工件从缓冲区装载至M2（用t3表示）；,注：p6表示空余的缓冲区空位，初始状态下，P6中包含2个标识，表示缓冲区有2个空位,返回,一个生产单元的PN建模,返回,机器人历经以下活动与状态:将工件装载至机器M1或M2（由t1或t3表示）机器人在使用之中，即工件在被M1或M2加工之中（用p2或p4表示）；将工件装载从机器M1或M2上卸载（由t2或t4表示）,注：p8表示机器人是否可使用,一个生产单元的PN建模,各子模型之间存在着共用库所与变迁，虽然这些库所与变迁在不同的子模型中，代表的意义可能不同，但实际上它们表示同一过程，只是不同的子系统从各自的角度用不同的语意予以解释。例如，t2在机器M1模型中解释为“工件由R从M1上卸载”，在缓冲区子模型中解释为“R将工件送入缓冲区”，在机器人子模型中解释为将工件装载从机器M1上卸载”。实际上我们在系统模型可以用语意“工件由机器人从M2上卸载并送入缓冲区”统一这些不同的解释。,一个生产单元的PN建模,p1载有工件的托盘可使用p2机器M1在加工工件之中（机器人被M1占用）p3载有中间工件的托盘存放于缓冲区中p4机器M2在加工工件之中（机器人被M2占用）p5机器M1可使用p6空余的缓冲区空位p7机器M2可使用p8机器人可利用t1机器人将载有工件的托盘装载到机器M1上t2机器人将载有工件的托盘从机器M1上卸载并送入缓冲区并释放机器人t3机器人将载有工件的托盘装载到机器M2上t4机器人将载有工件的托盘从机器M2上卸载并送入缓冲区并释放机器人,赋时Petri网模型,1.赋时库所Petri网2.赋时变迁Petri网3.基于赋时Petri网加工车间分析4.赋时Petri网在FMS生产调度中的应用,引言,基本Petri网不涉及时间，只能用于系统的逻辑建模（与时间无关），分析系统的逻辑结构与行为，如可达性、有界性、活性、可逆性等，它们与时间无关。而系统的许多性能与时间关联，如制造系统的设备利用率、生产率等。为了建立考虑时间的系统模型，在基本PN中引入时间，得到了赋时Petri网(TimedPetrinets,TPN)。,在PN中引入时间的3种方法：（1）则将时间与变迁关联，得到赋时变迁Petri网(TimedTransitionPetriNet,TTPN)。（2）将时间与库所关联，得到赋时库所Petri网(TimedPlacePetriNet,TPPN)。（3）将时间与输出弧关联。,若时间为确定的，则得到确定赋时Petri网(DeterministicTimedPetriNet,DTPN)，或简称为赋时Petri网(TPN)。若在TTPN中，与变迁关联的时间为随机的（服从一定的概率分布），则得到随机Petri网（StochasticPetriNet,SPN）；若部分变迁的时间为随机的，部分变迁为即时变迁(ImmediateTransition)，既所关联的时间为0，则得到广义随机Petri网(GeneratedStochasticPetriNet,GSPN)。,赋时库所Petri网,定义：赋时库所Petri网(TPPN)定义为以下六元素：TPPN=P,T,I,O,m0,D此处：P,T,I,O,m0与基本PN的定义相同；D=d1,dn为所有库所的时延集，其中di为pi的时延；,TPPN的变迁激发按照与基本PN相同的激发规则改变输入与输出库所中的标识，但通过变迁的激发放入输出库所中的标识必须要等待一定时间后才可利用，该时间等于该库所的时延。从标识被放入输出库所起计到延时结束前的这段时间，表示库所所代表的局部状态的实现过程。在此时间段里该状态不能作为其它事件发生的前提条件，也就是说，不能用于使其它变迁可激发。只有此状态实现后，才能作为其它事件发生的前提条件，也就是说，只有标识变得可利用后，才能使其它变迁可激发。,赋时库所Petri网,因此，判别TPPN的变迁是否可激发，除了必须象基本PN那样考虑输入库所是否具有变迁的激发所需要的标识数量外，还要求这些数量（并不是所有的）的标识均为可利用的。也就是说，TPPN的变迁的可激发要求输入库所中包含的可利用的标识的数量不得少于变迁输入函数所规定的数量。根据先进先出(First-in-First-out,FIFO)的原则，激发某变迁所需的输入库所中可利用标识总是从最先到达的标识依次选取。,赋时库所Petri网,TPPN也都具有基本PN的那些性能，如有界性、活性等。但由于时间的移入，某些性能将发生变化。例如，某一非有界的基本PN，当引入一定的时间后，可能变得有界了。这是由于考虑有界性时所涉及的标识标识应为可利用的标识，某一库所中的某些标识在其它标识变得可利用前就已经从该库所中移走。因此在TPPN中库所中的所包含的最大可利用标识数量一定小于基本PN中的库所中所包含的最大标识数，使得非有界的库所可能变得有界。TPPN的动态还呈周期性，即间隔一个固定的时间出现相同的标记。因此TPPN特别适于大中批量生产中重复生产过程的建模。,赋时库所Petri网,可采用关联矩阵法对TPPN进行分析，必须注意TPPN的标识的变化是瞬间完成的。若m(0)与m()分别表示当前时刻0与下一时刻(00，解得到流向量：i3=i1，i4=i2，以及i5=i1+i2。这里，只有两个独立的流向量。接着，构造DOi，从而得到：DOid1i1,d2i4,d3i1,d4i2,d5i5,d6(i4+i3)T,由m0=(R1R200Rt0)T，并分别令xT=x1T,x2T以及x3T，运用式xTm0=xTDOi得到下列三个方程：R1=(d1+d3)i1;R2=(d2+d4)i2;Rt=(d5+d6)(i1+i2)+d3i1+d4i2,例：赋时库所Petri网,因此，当工序1与2所需机器台数分别为R1与R2时，系统要以实现最大生产率，所需要的最少刀具数量Rt必须满足上式。这就建立了初始标识、时延以及激发频率之间的关系。例如，若R1=R2=1，则i1=1/4，i2=1/6，而所需要的刀具最少数量为:Rt=(5+6)(1/4+1/6)+31/4+41/6=6不难理解，若只有1把刀具可用，则系统不可能以最大生产率运行。事实上，系统的最大周期为1/6（为i1与i2的最小值），它等于生产率的倒数。此外，还必须使用某些冲突解决方法分配单一的共享刀具。除了增加时间外，总可以配置一定数量的刀具，使得两个工序间不存在资源竞争。然而，实际中资源是要花费的，因此其数量受到限制。为此，必须采取调度或资源分配措施。,例：赋时库所Petri网,关于流向量的解释：流向量类似于电路中的电流，服从克尔霍夫(Kirchhoff)电流定律（KCL）。若将时延与流向量的积看作电压降，则类似于克尔霍夫电压定律(KVL)，可发现电压降之和等于标识之和。实际上，可以通过P不变量子网解系统的方程。将对P1、P2及P3施用KVL，可以得到相同的解，但求解要更容易。,例：赋时库所Petri网,赋时变迁Petri网,定义：赋时变迁Petri网(TTPN)定义为以下六元素：TTPN=P,T,I,O,m0,D此处：P,T,I,O,m0与基本PN的定义相同；D=d1,dm为所有变迁的时延集，其中di为ti的时延。TTPN的变迁激发规则：与基本PN相同的激发规则改变输入与输出库所中的标识。但是，一旦变迁可激发，则立即从该变迁的每一输入库所中移去一定数量的标识。变迁要延迟一定时间后再激发，并在输出库所中放入一定数量的标识。从标识离开输入库所到标识到达输出库所存在着空隙，在用基本PN方法对于TTPN模型分析时，必须注意这一空隙，不要忽略将延迟到达的标识。,基于赋时Petri网加工车间分析,利用TTPN计算一加工车间的生产周期。当周期为确定量时，其倒数即为系统的生产率。路径问题：在加工车间里的每一工件都需要在特定的一系列机器上加工（并不是非得需要全部机器，也有可能需要使用某些机器若干次），我们称确定工件的加工所需的机器的序列为路径问题。假设：（1）所要分析的路径是已知的，每一工件加工的路径是唯一的，且每一工序所占用的机器的时间是确定的并且是已知的。（2）机器所要加工工件的序列是已知的，且加工车间的输入序列也是已知的。所谓输入序列是指派往加工车间的加工工件的顺序。,基于赋时Petri网加工车间分析,制造系统若干问题：（1）瓶颈：给定任意产品组合下，我们还可以使得某些机器在稳态下得到充分使用。那些被充分使用的机器将对于系统的产量起到决定性的影响，因为它们的生产能力已经饱和。我们称这些机器为瓶颈机器。（2）生产率与中间库存之间权衡：工件通过容器(托盘)、运输车辆进行搬运。这些搬运设施都会消耗一定的成本，而且车辆太多了会造成系统的堵塞。因此，实际中聪明的作法是尽量减少中间库存。然而，正如我们将要看到的那样，这样将很有可能以牺牲系统的生产率为代价的。因此，必须在生产率与中间库存之间权衡。,基于赋时Petri网加工车间分析,加工车间的模型已知：（1）加工车间有m个机器，它们分别表示为M1、M2、Mm，以及n个不同的加工工件，它们分别记为J1、J2、Jn。（2）每一加工工件通过加工车间的路径，用r(Ji)表示工件Ji的路径。（3）对于某一机器Mi，需要加工工件的序列为r(Mi)。（4）加工车间的输入工件序列为周期的，且表示为S0。假设有3台机器、3种不同的工件，其路径及序列如后表所示。每一工件在机器上的加工时间在表中的括弧中列出。周期的输入序列S0表示如下的产品组合：25%的J1、25%的J2以及50%的J3。,基于赋时Petri网加工车间分析,第一步：将输入序列S0中的每一工件的路径描述为一串变迁。如图所示。每一变迁的时延对应着每一工序的加工时间。每一路径中的第一个变迁为即时的（无时延），它表示将工件向系统派送。注意到J3在图中出现2次，这是考虑到J3在产品组合占50%的缘故。,注：这些路径模型中一个标识表示一个工件，相应的库所表示称为堆料库所。,基于赋时Petri网加工车间分析,第二步：描述些制造过程的周期性工序。假设工件被放在托盘上在加工车间里穿梭。当一工件加工完毕，托盘腾空且返回到加工过程的起始处并装载同样类型的新的工件。这一闭环模型如图所示。图中的回路称为加工回路，而封闭回路的库所叫做资源库所。,基于赋时Petri网加工车间分析,第三步：建立描述机器所要加工的工件的序列以及输入序列的模型。这一模型可以通过将对应着由同一机器完成的工序的变迁连接成单一回路来得到。这些回路叫做命令回路，其上变迁的次序由相应的机器所要加工的工件的顺序所确定。,加工回路与命令回路起着不同的作用：加工回路上的标识（可能有一个以上）描述要加工的工件，因此它们代表了实体。命令回路上的一个标识（只能有一个）表示机器是否可以用来进行加工某一特定的工件。命令回路中标识的初始库所由序列中的第一个工件所确定。,由图可见:M1上所完成的工序用t11、t31及t41表示。为了执行r(M1)，必须命令M1先加工J1，然后加工2个J3工件。这在图中已经得以实现，具体地通过命令回路t11、c6、t31、c7、t41及c5来表示。该回路上的库所叫做命令库所。这里，堆料区（缓冲区）、资源及命令库所分别标注为b、r以及c。图中的标识分别表示了加工车间的初始状态，可能包括正在加工之中的工件。,图上所示的网为标识网，而且该网是强连接的（Stronglyconnected），这是由于输入命令回路将所有的加工回路联系在一起的缘故。所谓强连接是指对于网上任意一节点（库所或变迁），都存在从它到任何其它节点的有向路径（Directedpath）。,定理：对于一标识图，其任意基本回路上的标识在激发任意序列的变迁后仍然保持相同。上述基本回路是指从某一节点（库所或变迁）出发再返回该节点的有向路径，除了起始节点外，其它节点在该路径上最多只出现一次。证明：回路上的标识只能被该回路上的变迁产生或消耗。既然每一库所仅有1个输入变迁与1个输出变迁，则不可能创造或消耗掉标识。换句话说，当一变迁消耗掉1个标识，则它将产生1个返回该回路的标识。因此，回路中的标识在激发任意序列的变迁后仍然保持相同。注意的是标识图中的标识数量可能改变，但回路则不然。,基于赋时Petri网加工车间分析,定义：设Si(ni)为ti开始其第ni次激发的时间，则变迁ti的循环周期Ci定义为,Si(ni)/ni为每次激发的平均时间；以上定义的周期显然是系统稳态下变迁ti的周期，即变迁激发两次之间的时间间隔。,定理：标识图上的所有变迁具有相同的周期。（证略）,定理：对于标识网，最小周期（最好的性能）Cm为：,此处：q是模型中回路的个数；Tk是回路k上的变迁的时延之和；Nk是回路k上的标识之和，Tk/Nk为回路k的周期。,基于赋时Petri网加工车间分析,例：求一系统的循环周期。图为一系统的标识网模型(TTPN)，图中D=5,20,4,3,2，试求该系统循环周期。,为此，枚举网中所有基本回路，并计算其周期回路A-t1-C-t2-E-t4-G-t5：Tk/Nk=(5+20+3+2)/2=15；回路A-t1-D-t3-F-t4-G-t5：Tk/Nk=(5+4+3+2)/1=14；回路B-t1-C-t2-E-t4：Tk/Nk=(5+20+3)/2=14；回路B-t1-D-t3-F-t4：Tk/Nk=(5+4+3)/1=12。因此，最小循环时间为：Max(15,14,14,12)=15,基于赋时Petri网加工车间分析,基于赋时Petri网加工车间分析,证明回路A-t1-C-t2-E-t4-G-t5上的t1的周期为15。为此，必须追踪变迁激发历经，并施用定义4.3。我们称图4.8所示的初始标识下的库所A中的标识为标识A，类似地，库所C中的标识为标识C。很显然，标识A在t=0时刻启动变迁t1的激发，且标识C启动变迁t2的激发。在t=5时刻，标识A启动t2的激发。下一个变迁激发开始的时刻为t=20，此时标识C启动变迁t4的激发。然后，在t=23时刻，标识C将启动变迁t5的激发。在t=25时刻，标识A启动t4的激发，而标识C启动t1的激发。在t=28时刻，标识A启动t5，而在t=30时刻t1与t2的激发被启动。这将引起该周期重