生产系统建模与仿真.ppt

,生产系统建模与仿真 Production System Modeling & Simulation,面向工程实际的应用型的基础性课程，是工业工程专业的主导课程。,课程介绍,从课程的题目中可以看出： 离散系统建模与仿真 其对象是： 离散系统 生产系统是一个典型的离散系统。 物流系统也是一个离散系统。 目的是：仿真。即用一种抽象的、能够反映系统 研究本质的“虚假”系统，来模拟实际系 统。而这虚假系统就是系统模型。,课程性质：,征求答案,什么是仿真？什么是离散系统的仿真？ 为什么需要做仿真？ 何时需要做仿真？ 如何进行仿真？ 仿真要做那些准备工作？ 仿真的可信度如何评价？ 对仿真模型如何作评价？ 你知道的仿真软件有哪些？各自具有哪些特征？ 你希望通过本课程的学习获得些什么？,课程试图解决的问题：,离散事件系统建模与仿真的基本原理 离散事件系统建模与仿真的方法 Petri网建模与仿真 课程的先修课程： 生产运作与管理 运筹学 计算机编程与应用技术 概率论与数理统计 课程的考核方法： 完成相关作业及期末考核。,课程介绍,课程主要内容：,课程主要内容构成,第一章 离散事件仿真的概述 第二章 离散事件仿真的分析 第三章 离散事件仿真的案例分析 第四章 离散事件仿真的逻辑分析 Petri网,第一章 离散事件仿真的概述,1.1 离散事件系统仿真的基本概念 1.2 生产系统仿真的特征 1.3 服务系统仿真的特征 1.4 离散系统仿真的基本步骤,1.1 离散事件系统仿真的基本概念,什么是系统？ 系统是按照某些规律结合起来的，相互作用、相互依存的所有元素的集合。 系统有哪些种类？ 连续系统 & 离散系统 变量状态 静态系统 & 动态系统 时域状态 确定系统 & 随机系统存在随机变量 单变量系统 & 多变量系统 自由度数量,1.1 离散事件系统仿真的基本概念,什么是系统仿真(Systematic Simulation)? 仿真：对现实中的现象通过某种抽象，建立表达现实变化规律或特征的模型，运用一定的手段加以描述，这就是仿真。 系统仿真：首先针对真实系统建立模型，然后在模型上进行试验，用模型代替真实系统，从而研究系统性能的方法。 系统仿真将能一一仿效实际系统的各种动态活动，并把系统动态过程的状态记录下来。最终得到用户所关心的系统统计性能。,1.1 离散事件系统仿真的基本概念,为什么要采用系统仿真? 系统所涉及到的专业知识较为广泛，如：机械、生产管理、人事管理、产品设计、生产工艺等 现实问题的规律是复杂的，一般很难用一确定的数学方程或数学函数显性地或隐性地表达。 科学技术的发展难以适应生产系统研究的需要,仿真是系统特征无法用数学方程、数学函数描述时，为了研究系统特征所采用的一种研究方法。我们可以这样说：仿真是一种“不得已而为之”的方法,1.1 离散事件系统仿真的基本概念,系统仿真方法适用怎样的领域？,系统仿真的方法适用于任何的领域,工程类,非工程类,机械,电子,化工,交通,管理,经济,政治,1.1 离散事件系统仿真的基本概念,系统模型有哪些？,系统模型,确定型模型,随机型模型,静态,动态,静态,动态,连续,离散,连续,离散,离散事件仿真,蒙特卡洛仿真,什么是离散事件系统？ 离散事件系统是包含事件的发生在时间或空间上都是离散的，例如交通管理、生产自动线、计算机网络、通信系统和社会经济系统都是离散事件系统。 离散事件系统定义为一组元素(实体)的集合，为了达到某些目的，这些元素以某些规则相互作用、关联而集合在一起。例如制造系统由机器、部件以及操作工人组成，银行系统由出纳员和顾客组成。 离散事件系统的变量通常用状态变量表示，如：实体的发生与不发生；事物的计数等等。,1.1 离散事件系统仿真的基本概念,离散事件仿真模型的特点 -随机型：具有随机性的状态变量 -动态性：随时间演变是模型的重要特征 -离散事件：主要的变化发生在离散的时间点上,1.1 离散事件系统仿真的基本概念,事件的发生在时间和空间上都是离散的。系统的数字仿真则经常是面向事件的 离散事件系统定义为一组元素(实体)的集合，为了达到某些目的，这些元素以某些规则相互作用、关联而集合在一起。 离散事件系统状态变量仅仅在可数的一些时间点上才有变化 。系统变量是反映系统各部分相互作用的一些事件，系统模型则是反映这些事件状态的数集，仿真结果是产生处理这些事件的时间历程。 在离散事件系统中，各事件以某种顺序或在某种条件下发生,并且大都是随机性的，不能用常规的方法加以研究。,连续系统事件的发生在时间和空间上都是连续的。 在连续系统的数字仿真中，时间通常被分割成均匀的间隔，并以一个基本的时间间隔计时。 在连续系统仿真中，系统动力学模型是由表征系统变量之间关系的方程来描述的。 仿真的结果为系统变量随时间变化的时间历程。,连续系统与离散系统有何区别？,1.1 离散事件系统仿真的基本概念,离散事件仿真时钟的演变方法有哪些？ 时间离散 系统只在一些特定的时刻，即=t1 , t2, 上被考察。通常，为了便于研究，各时间间隔选定为整常数，t=常数。 事件离散 系统状态的变化，即事件时刻是不连续的、跳跃式的， t= ti+1-ti，i，ti为事件发生时间。,1.1 离散事件系统仿真的基本概念,l 某些系统的建模困难，如，对于大比例系统模型，建模会变得十分复杂，程序的编写与程序的运行都是十分艰巨的。但是随着优质的仿真专业软件的诞生，对于这样系统的仿真日趋简便。 l 仿真需要大量的计算机机时。这一问题随着计算机技术的发展正在逐步得到解决。 l仿真需要大量实际的、准确的数据，这是一般企业所难以提供的，因此对仿真结果的准确性带来了影响，导致了人们对仿真能力的怀疑。 总之，正是由于上述的种种因素，是人们对仿真留下了不好的印象。这里还要说明的是：仿真只是计算机编程的一种游戏，游戏的规则来自于问题的本身，游戏的范围也是问题所约定的。,离散事件仿真运用存在哪些阻碍？,1.1 离散事件系统仿真的基本概念,离散事件仿真模型如何建立？ 如何为一个离散事件系统建立一个模型 确定一个系统目标或仿真目的 建立概念性模型 转换为一个详细模型制定仿真规则 转换为一个计算机计算模型编制程序代码 模型的运行检验特例检验 模型的有效性检验模型检验、可信度检验 典型事件的多次重复仿真循环过程,1.1 离散事件系统仿真的基本概念,离散事件仿真模型的三层次模型 概念模型层 极其概念性的层次模型（通常是语义性的系统描述） 模型是如何构成的？ 什么是模型的状态变量，哪些是动态变量，哪些是重要变量？ 详细模型层 模型的书面整理 模型包括哪些方程，哪些伪随机数，哪些辅助变量等 模型参数如何输入？ 计算模型层 计算机程序 通用编程语言或仿真语言,1.1 离散事件系统仿真的基本概念,系统与系统模型的实质关联是什么？ 系统：研究的本体 系统模型：为研究系统所收集的有关信息的集合。通过研究系统模型来揭示系统的性能。 它和“系统”的定义比较，两者都是集合，系统是以某些规律结合起来、有相互作用的元素组成；而系统模型是为了研究其结合规律相互作用所收集的有关信息。因为收集的信息有详细、粗略之分，加上收集方法的差异和研究目的的不同，因此对于同一个系统就会出现多种不同的系统模型。模型是为系统服务的，因此，所揭示的性能规律应该是稳定的。,1.1 离散事件系统仿真的基本概念,离散事件仿真的输入数据该如何收集和处理？ 仿真的输入数据来源于事件采集稳定的数据 仿真的输入数据应该与实际数据有同样的变化规律拟合度检验 仿真的输入数据应当是相互独立的相关性检验,1.1 离散事件系统仿真的基本概念,离散事件仿真的输出数据应该有哪些分析？ 仿真结果的可信度分析 仿真运行的效率分析 仿真结果的性能分析,离散事件系统仿真模型的简例,某一个工作人员每日的工作是处理文件，他从每天开始工作时即处理文件，直至文件处理完毕或工作结束，每一个文件处理完毕后开始下一个文件的处理，工作间隔一小时休息一次，休息时间为5分钟，但必须是在一个文件处理完毕之后。假设不考虑当天收到的文件，那么文件的数量可以预置，并随着每个作业的完成递减，直至为零。,1.1 离散事件系统仿真的基本概念,实例求解,实例目标：了解仿真 求解方法：手工仿真 求解平台：Excel 求解原理： 每个文件的处理时间（工作时间tw）是一个随机过程，符合一定的概率分布； 该工作人员一上班就开始处理文件，所以第一个文件处理的开始时间就是仿真的开始时间（0时刻），后续文件的开始时间tf上一文件的结束时间或休息后的时间； 每一个文件处理的结束时间文件处理的开始时间文件处理时间； 设置一项统计量：累计工作时间tc=休息后的工作时间之和。当tc 1小时，则置为零，同时标识一次休息；仿真时间推进5分钟。,1.2 生产系统仿真的特征,产品工艺技术与生产管理的结合 相同的结果可以有不同的生产工艺 生产管理策略对生产运作产生何种影响 稳定的生产过程 生产流程的稳定 生产时间规律化变化 生产过程存在不确定变化 人工干预生产作业的不确定变化及学习变化 机器设备的不确定故障停机,1.3 服务系统仿真的特征,服务技术与服务管理的结合 相同结果可以有不同的服务流程 服务策略对服务运作产生何种影响 客户化的服务过程 服务流程随着客户需求而改变 服务时间的不确定变化 服务过程存在不确定变化 服务流程的不确定 服务时间的不确定 服务资源配置的不确定客户数量、需求的不确定,1.4 离散系统仿真的基本步骤,明确离散系统仿真的需要解决的问题 系统运作的流程（确定流程或可能流程） 系统运作的管理策略运作规则 系统的概念性建模：明确系统构成的元素 系统的详细建模：明确系统各元素的参数 系统运行编程：根据管理策略形成系统的运行规则 系统试运行系统模型的有效性检验和可信度检验 系统正式运行,第二章 离散事件仿真的分析,2.1 随机数的产生 2.2 离散事件仿真建模 2.3 输入数据分析 2.4 输出数据分析,2.1 随机数的产生,为什么要产生随机数? 平时我们遇到的随机数符合怎样的分布？ 随机数生产的方法有哪些？,随机事件是所有不确定事件中唯一可以分析的一种事件形式。因此，对于诸多不能明确解析的实际系统中最常见的就是随机系统，随机系统的运行首要解决的问题就是产生随机数。,（0，1）均匀分布的随机数。,线性平移法（适用于均匀分布的随机数产生） 同余法（适用于均匀分布的随机数产生，常用方法） 逆变换法（密度函数的反函数可求的状况） 舍取法（任意给定分布） 组合法（标准分布组合形成的复杂分布） 经验生成法（特殊的常用分布，运用经验公式产生）,2.1 随机数的产生,（0，1）随机数的检验 数字特征检验 分布均匀性检验 独立性检验,服从N(0，1),在给定显著性水平后，即可根据正态分布确定临界值，据此判断与理论平均值及与X2理论平均值之差异是否显著，从而决定能否将产生的随机数看作是(0，1)均匀分布随机变量的N个独立取祥值。,服从自由度为k-1的2分布,服从N(0，1),2.2 离散事件仿真建模,排队系统：由服务机构（服务模式）（可以是服务台、加工机器、搬运设备等）、到达模式及排队规则组成的集合。 库存系统：由订单到达模式、订单规模、补货数量、交货期及补货策略（盘库间隔、到货规则）组成的集合。 流程系统：由特定的一簇服务对象按照其自有的运作流程（顺序及滞留时间）将对应的服务机构（排队系统、库存系统）有序地连接在一起组成的集合。,前后事件多对一,前后事件一对多,前后事件多对多,事件的返回,离散事件系统,事件的合并,事件的拆分,离散事件系统,设备可用性。设备可以加工工件的前提是设备是可用的，设备可用的必要条件有： （1）当前时刻是生产系统工作日志所规定的正常工作时间，而不是休息、保养、大修的时间； （2）当前时刻设备是正常状态，而不是处于损坏、维修、冻结、堵塞等状态； （3）当前时刻设备具备正常运行所需的所有技术条件，包括操作工人、工装、模具等； （4）当前时刻设备空闲或设备的某一工位空闲；,离散事件系统,1）单台机器排序问题 （n/1/ /B),n个工件全部经由一台机器处理,离散事件系统,常见单台机器排序问题的目标函数 1) 平均流程时间最短,2）最大延期量最小,目标函数,为n个零件经由一台机器的平均流程时间。,定义:,目标函数：使平均流程时间最短,Fi= Pi+ Wi,Ti=max0, Li,Li= Ci- di , 工件i的延误时间 Li0 延误,生产系统,离散事件系统,Pi=任务i的作业时间 Wi=任务i的开始作业时间,根据排序目标的不同，可以选择不同的排序规则，又称为确定零件加工的优先权。 常见的排序规则： SPT-Shortest Process Time, 优先选择加工时间最短的工件 EDD-Earliest Due Date 优先选择交货期紧的工件 FCFS-First Come First Served 按工件到达的先后顺序 CR-Critical Rate 优先选择临界比最小的工件 CR=（交货期-当前日期）/剩余加工时间,离散事件系统,2) 求平均流程时间最短的排序问题,求平均流程时间最短的作业顺序，采用SPT原则。 按工件加工时间的长短，从小到大按排作业。 例：一台加工中心，现有5个工件需要该机器加工。相关的加工时间和要求完成时间（交货期）如下表所示，求平均流程时间最短的作业顺序。,离散事件系统,解：根据SPT原则，得出： J4 -J5 -J1 -J2 -J3 有关项目的计算：,发生延迟,发生延迟,=43,生产系统,离散事件系统,3）求最大延期量最小的排序问题,求最大延期量最小的作业顺序采用EDD原则。 例：同上面的例子，按延期量(完工日期-交货期）大小，从小到大排序。 解：根据EDD原则，得出 J3 -J5 -J4-J2 -J1,生产系统,离散事件系统,=18,1、两台机器排序问题的含义(n/2/F/Fmax) n个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。,生产系统,n项任务在两台机器的排序问题,离散事件系统,2、两台机器排序问题的目标,两台机器排序的目标是使生产周期Fmax最短。 Fmax的含义见如下图。,生产系统,离散事件系统,3、两台机器排序问题的算法 约翰逊法(Johnsons Law)， 约翰逊法解决这种问题分为4个步骤： (1)列出所有工件在两台设备上的作业时间。 (2)找出作业时间最小者。 (3)如果该最小值是在设备1上，将对应的工件排在前面，如果该最小值是在设备2上，则将对应的工件排在后面。 (4) 如果同时出现一个以上的最小值,任意选区一个. (5)排除已安排好的工件，在剩余的工件中重复步骤(2)(4)，直到所有工件都安排完毕。,生产系统,离散事件系统,例：某一班组有A、B两台设备，要完成5个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。,生产系统,离散事件系统,解：由约翰逊法可知，表中最小加工时间值是1个时间单位，它又是出现在设备1上，根据约翰逊法的规则，应将对应的工件4排在第一位，即得： J4 - * - * - * - * 去掉J4，在剩余的工件中再找最小值，不难看出，最小值是2个时间单位，它是出现在设备2上的，所以应将对应的工件J1排在最后一位，即： J4 - * - * - * - J1 再去掉J1，在剩余的J2、J3、J5中重复上述步骤，求解过程为： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J3- J5 - J1 当同时出现多个最小值时，可从中任选一个。最后得 J4 - J2 - J3- J5 - J1,生产系统,离散事件系统,（1）计算加工周期（按零件序号加工）,生产系统,离散事件系统,（2）计算加工周期（按约翰逊法）,生产系统,离散事件系统,(a) J1 - J2 - J3- J4 - J5,(b) J4 - J2 - J3- J5 - J1,生产系统,离散事件系统,离散事件系统仿真可在加入随机因素（工时的变化、设备失效）的前提下以更直观的方式获知那种排序规则更好。 离散事件系统仿真是在管理规范化的基础上考虑到更为细节的因素，可使生产线的管理策略更好地适应现实世界。,生产系统,离散事件系统,2.3 输入数据分析,什么是输入数据？ 什么是输入数据分析？ 输入数据分析些什么？,仿真模型中，用于支撑仿真进行的各个已知元素的特征参数。有很多这样的参数呈现出（假设为）随机的特征。,对各个具有随机特征的已知元素的特征参数，运用数理统计的方法来获得其适当的随机概率分布，以支持仿真过程中的随机数产生。,随机概率密度函数（什么分布？分布的参数是多少？） 分布的检验（拟合度检验、独立性检验）,2.3 输入数据分析,输入数据分析的基本步骤 数据过滤：消除非规律性影响因素。 分布的假设：通过频率图的形状估计，假设数据的理论分布 假设分布的参数估计：估计假设给定理论分布函数的参数 分布的拟合度检验：假设理论分布与实际分布值之间的拟合程度检验（ f=k-s-1 的方检验） 变量的相关性检验：系统仿真中随机产生的数据应当符合数据本身独立的特征（f=n-m-1的t检验）,2.4 输出数据分析,离散事件仿真的数据特点？ 不确定性（不可重复性、理论上无统计规律） 离散事件仿真数据的真实性是什么？ 给定置信水平的置信区间 如何提高置信水平？ 增加重复运行的仿真次数。置信度为100%的仿真次数为,2.4 输出数据分析,仿真输出数据的性能测度,上式成立的条件是的某一仿真性能参数之间是独立的。（自相关函数为零） 当自相关函数是负值，上式趋于保守。 当自相关函数为正值，上式不成立。须进行详细地检验。,2.4 输出数据分析,终态仿真的输出分析 什么是终态仿真？ 在某一个持续时间TE内的系统仿真。如：生产设备的使用寿命就是这一类的系统仿真。 终态仿真的特征：系统仿真是在零时刻开始“开启”，至TE时刻“关闭”，其中TE可以是一个随机变量。研究的是不同持续时间TE或“开启”时刻状态对系统性能参数的影响。 终态仿真的输出分析独立重复运行法 假设系统仿真进行了n次独立重复运行，得到n个系统性能测度的仿真观察值Y1, Y2, , Yn ，则系统性能测度的估计量为,2.4 输出数据分析,设仿真重复进行了R组，r(=1，2，R)为其中的一组仿真。令Yri为第r组仿真中的第i次系统性能测度的观察值，i=1，2，nr。此时，对每一次运行r，其样本均值为,， r =1，2，R,R次独立重复运行后，系统性能测度的估计量为,上式可以看到：标准差的估计量 随着R的增加而减小。即仿真的可信度有所提高。,2.4 输出数据分析,稳态仿真的输出分析 什么是稳态仿真？,2.4 输出数据分析,提高仿真效率的数据处理方法,第四章 离散事件仿真的逻辑分析 Petri网,什么是Petri网？,在定义Petri网(Petri Net)时，必须要区别PN结构与标识PN (Marked Petri Net)。它定义了DES (Discrete Event System)可能的状态、事件、及其它们之间的关系，这相当于连续状态变量系统CVDS的状态方程。在PN中，用标识（Marking）描述DES的状态。后者又称PN，它是指具有一定标识的PN，描述处于一定状态下的DES，相当于给定了状态方程的状态变量在一定时刻值的CVDS。,定义：PN的结构是由四要素描述的一个有向图：PNS=(P, T, I, O) 满足： （1） P=p1, , pn是库所(位置)的有限集合，n(0)为位置(库所)的个数; （2） T=t1, , tm是变迁的有限集合，m(0)为变迁的个数； PT= ， PT ； （3） I：PTN是输入函数，它定义了从P到T的有向弧的重复数 或权(Weight)的集合，这里N=0, 1, 为非负整数集； （4） O：TP N是输出函数，它定义了从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)=1 I(p1, t1)=1，m(p2)=1I(p2, t1)=1， 因此变迁t1使能的；而t2=p3，由于m(p3)=0 I(p3, t2)=1，因此t2不使能。,第四章 离散事件仿真的逻辑分析 Petri网,Petri网中变迁的发生激发(Firing)规则？ 所有前提条件得以满足的事件的发生，将“消耗”这些前提状态，同时改变与该事件有关的局部状态（结果状态），即使得这些结果状态实现一定的次数。 在PN中，用使能的变迁的激发来描述事件的发生。 所消耗的前提状态及其次数由变迁的输入函数定义并通过从输入库所中移去相应数量的标识来表示； 所产生的结果状态及其次数由输出函数确定并用输出库所中增加的标识表示。 由于输入库所中的标识的减少以及输出库所中标识的增加，使得PN的标识发生变化。,第四章 离散事件仿真的逻辑分析 Petri网,激发规则的定义 在标识m下使能的变迁t的激发(Firing)将产生新标识m： pP: m(p)=m(p)-I(p, t)+O(p, t) 对于pt，m(p)=m(p)-I(p, t)； 对于pt，m(p)=m(p)+O(p, t)； 对于ptpt（既是t的输入又是输出库所），pP： m(p)=m(p)-I(p, t)+O(p, t)； 对于ptpt（既不是t的输入又不是输出库所），m(p)=m(p)。 称标识m是（通过t的激发）直接从m可达的，记为mtm。,状态转换的例子,在右上图所示的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: TP 0, 1，则此PN称为普通PN（Ordinary Petri net）。 若PN无自闭环，即某一库所同时是某一变迁的输入与输出库所，则此PN称为纯PN（Pure Petri net）。 若PN的每一库所都恰好有1个输入变迁与1个输出变迁，即pP: |p|=|p|=1，则该PN称为标识图(Marked graphs)。 若PN的每一变迁都恰好有1个输入库所与1个输出库所，tT: |t|=|t|=1，则该PN称为状态机(State machine)。,第四章 离散事件仿真的逻辑分析 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的抑制弧 （Inhibitor arc ）,按输入函数的定义，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立即可达的(Immediately reachable)。所有从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是结构有界的(Structurally bounded)。,基本PN性能,意义： 库所用于表示制造系统中的工件、工具、托盘以及AGV的存放区（工件的存放区就是缓冲区），还用于表示资源的可利用情况。确认这些存放区是否溢出(Overflow)或资源的容量是否溢出是非常重要的。,PN的有界性是检查系统是否存在溢出的有效尺度：当库所用于描述一操作，该库所的安全性能够确保不会重复启动一正在进行的操作。 我们可直观地看到，右图所示的PN是1-有界的，因此它是安全的。,定义: 对于一变迁tT，在任一标识mR下，若存在一变迁序列sr，该变迁序列的激发使得此变迁t使能，则称该变迁是活的(Live)。若一PN的所有变迁都是活的，则该PN是活的。 死变迁(Dead transition)或者死锁(Deadlock)从反面描述PN的活性。若存在mR，不存在从m开始的变迁序列，该序列的激发使得t使能，则变迁t为死变迁。若存在mR，在此m下无任何变迁使能，则称PN包含一死锁、该标识为死标识(Dead marking)。,基本PN性能,死变迁(Dead transition)或死锁(Deadlock),基本PN性能,出现死锁的原因是不合理的资源分配策略或某些或全部资源的耗尽。在自动制造系统中，许多资源（如机器、包括AGV与机器人在内的物料搬运设备、以及缓冲区存放空间）是共享的。在这样的资源共享系统中，下列4个情况可能同时满足，从而导致锁死： 互斥：一资源不可以为2个或2个以上过程同时使用，一过程排斥其它过程对于该资源的占用。 占用且等待：一过程已被许可占用某一或某些资源，同时又在请求占用其它资源。 无抢占：已分配给某一过程的资源不能从该过程中抢走，除非该过程使用此资源完毕后而释放。 循环等待：2个或更多过程排成一个链，链上每一过程都在等待一个正在被链上下一个过程占用的资源。,制造系统出现死锁的例子,柔性制造系统的某一机器入出缓冲区占用着一托盘，其上存放着已加工完毕的零件。而另一存放待加工工件的托盘也被自动导向车(AGV)传送至该入出缓冲区。假设入出缓冲区只能存放一个托盘，而AGV也只能放置一个托盘。此时，存放着已加工的零件托盘不能从入出缓冲区移至AGV上，AGV也不能进入缓冲区将其上面存放着的待加工的工件的托盘送至入出件堆放区。 缓冲区与AGV为2个资源，将托盘从缓冲区移至AGV上与将托盘从AGV上送至缓冲区为2个过程。前者占用着缓冲区而等待着AGV，而后者占用着AGV而等待缓冲区，上述4个条件同时成立，因而出现死锁。,基本PN性能,可逆性(Reversibility)与主宿状态(Home state) 制造系统研究中的一个重要问题是如何使得系统自动地从差错中复原。例如，在利用机器人装配中，零件间可能无法配合，从而出现差错。我们希望在不需要人为干预的情况下，就能够从这一差错中复原。若一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所描述的系统具有无限个状态，则可达图将无止境扩展。取而代之，我们将构建覆盖树(Coverability tree)，它是无限可达图的有限表达方法。,基于PN制造系统性能分析,定义：标识m2覆盖m1，即m2m1，若pP： m2(p)m1(p)。 移入一特别符号，它代表“准-无限大”，用于表示任意大的标识数。遵循以下四个运算规则，使得对于任意正数k，都有： (1) k ； (2) ； (3) + k= ； (4) - k = 。,基于PN制造系统性能分析,算法：覆盖树构建方法,1. 让初始标识m0为树根，并作上“new”的记号； 2. 若有“new”标识存在，则做以下事情，否则，若没有“new”表示，则终止。 3. 选择某一“new”标识m； 1) 若m与树中间已有的其它标识相同，则将其记为“old”，然后转向其它“new”标识； 2) 若在m下无变迁使能，则将m记为“dead end”（死点）； 4. 对于m下使能的变迁t，做以下事情： 1) 激发t由m产生标识m； 2) 若在从树根至m的路径上存在一标识m，使得m覆盖m，但 mm（即mm），则对于那些使m(p)m(p)成立的p：用取代 m(p)； 3) 以m为一节点，从m至m画一有向线，将其并记为t，并将m记为“new”； 5. 除去m的“new”标志；,基于PN制造系统性能分析,例: 构建图(a)所示的具有无限储料空间之间缓冲区的二机器生产线的覆盖树。 初始标识为m0=(1 0 0 1 0)T,在m0下只有t1使能。激发t1将产生m1=(0 1 0 1 0)T。由于m1即不大于m0又不等于m0，因此将记为“new”，并从m0至m1画一有向线并记为t1。,m1为当前唯一的“new”标识，在m1下只有t2使能。激发t2将产生标识m2=(1 0 1 1 0)。由于m2m0且m2(p3)m0(p3)，因此，根据步骤4.2，在m2=(1 0 1 1 0)T中用取代m(p3)，从而得到标识m2=(1 0 1 0)T。,在当前唯一的“new”标识下，t1与t3使能。激发t1将产生m3=(0 1 1 0)T，它不等于从m0至m3路径上任何标识。虽然它大于m1=(0 1 0 1 0)T，但没有必要进行步骤4.2，原因是其第3个元素已经是。,激发t3产生m4=(1 0 -1 0 1)T=(1 0 0 1)T（根据-k=）。,目前存在m3=(0 1 1 0)T与m4=(1 0 0 1)T2个“new”标识。在m3=(0 1 1 0)T下，t2与t3使能。激发t2产生m5=(0 1 +1 1 0)T=(0 1 1 0)T，它等于先前产生的m3，因此记为“old”。激发t3产生m6=(0 1 0 1)T，它是一“new”标识。,目前仍然存在2个“new”标识：m3=(1 0 0 1)T与m6=(0 1 0 1)T 。继续进行，直至无“new”标识存在.,基于PN制造系统性能分析,根据上述方法，由图(b)所示的覆盖树可知，图(a)所示的PN是无界的，且除了p3其它库所是安全的。还可知该PN不包含死变迁，因为所有变迁都在树中出现。由于树中出现，我们无法作出该PN是否活的与可逆的结论。,基于PN制造系统性能分析,基于覆盖树或可达树，可以做如下分析： 当