生产系统建模与仿真概述.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,05 十一月 2026,生产系统建模与仿真概述,面向工程实际的应用型的基础性课程，是工业工程专业的主导课程。,课程介绍,从课程的题目中可以看出：,离散系统建模与仿真,其对象是：离散系统,生产系统是一个典型的离散系统。,物流系统也是一个离散系统。,目的是：仿真。即用一种抽象的、能够反映系统,研究本质的,“,虚假,”,系统，来模拟实际系,统。而这虚假系统就是系统模型。,课程性质：,征求答案,什么是仿真？什么是离散系统的仿真？,为什么需要做仿真？,何时需要做仿真？,如何进行仿真？,仿真要做那些准备工作？,仿真的可信度如何评价？,对仿真模型如何作评价？,你知道的仿真软件有哪些？各自具有哪些特征？,你希望通过本课程的学习获得些什么？,课程试图解决的问题：,离散事件系统建模与仿真的基本原理,离散事件系统建模与仿真的方法,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,离散事件系统仿真的基本概念,离散事件仿真时钟的演变方法有哪些？,时间离散,系统只在一些特定的时刻，即=,t,1,t,2,上被考察。通常，为了便于研究，各时间间隔选定为整常数，,t,=常数,。,事件离散,系统状态的变化，即事件时刻是不连续的、跳跃式的，,t,=,t,i,+1,-,t,i,，,i,，,t,i,为事件发生时间,。,1.1,离散事件系统仿真的基本概念,l,某些系统的建模困难，如，对于大比例系统模型，建模会变得十分复杂，程序的编写与程序的运行都是十分艰巨的。但是随着优质的仿真专业软件的诞生，对于这样系统的仿真日趋简便。,l,仿真需要大量的计算机机时。这一问题随着计算机技术的发展正在逐步得到解决。,l,仿真需要大量实际的、准确的数据，这是一般企业所难以提供的，因此对仿真结果的准确性带来了影响，导致了人们对仿真能力的怀疑。,总之，正是由于上述的种种因素，是人们对仿真留下了不好的印象。这里还要说明的是：仿真只是计算机编程的一种游戏，游戏的规则来自于问题的本身，游戏的范围也是问题所约定的。,离散事件仿真运用存在哪些阻碍？,1.1,离散事件系统仿真的基本概念,离散事件仿真模型如何建立？,如何为一个离散事件系统建立一个模型,确定一个系统目标或仿真目的,建立,概念性,模型,转换为一个,详细,模型,制定仿真规则,转换为一个计算机,计算,模型,编制程序代码,模型的运行检验,特例检验,模型的有效性检验,模型检验、可信度检验,典型事件的多次重复仿真,循环过程,1.1,离散事件系统仿真的基本概念,离散事件仿真模型的三层次模型,概念模型层,极其概念性的层次模型（通常是语义性的系统描述）,模型是如何构成的？,什么是模型的状态变量，哪些是动态变量，哪些是重要变量？,详细模型层,模型的书面整理,模型包括哪些方程，哪些伪随机数，哪些辅助变量等,模型参数如何输入？,计算模型层,计算机程序,通用编程语言或仿真语言,1.1,离散事件系统仿真的基本概念,系统与系统模型的实质关联是什么？,系统：,研究的本体,系统模型,：为研究系统所收集的有关信息的集合。通过研究系统模型来揭示系统的性能。,它和“系统”的定义比较，两者都是集合，系统是以某些规律结合起来、有相互作用的元素组成；而系统模型是为了研究其结合规律相互作用所收集的有关信息。因为收集的信息有详细、粗略之分，加上收集方法的差异和研究目的的不同，因此对于同一个系统就会出现多种不同的系统模型。模型是为系统服务的，因此，所揭示的性能规律应该是稳定的。,1.1,离散事件系统仿真的基本概念,离散事件仿真的输入数据该如何收集和处理？,仿真的输入数据来源于事件采集稳定的数据,仿真的输入数据应该与实际数据有同样的变化规律拟合度检验,仿真的输入数据应当是相互独立的相关性检验,1.1,离散事件系统仿真的基本概念,离散事件仿真的输出数据应该有哪些分析？,仿真结果的可信度分析,仿真运行的效率分析,仿真结果的性能分析,离散事件系统仿真模型的简例,某一个工作人员每日的工作是处理文件，他从每天开始工作时即处理文件，直至文件处理完毕或工作结束，每一个文件处理完毕后开始下一个文件的处理，工作间隔一小时休息一次，休息时间为5分钟，但必须是在一个文件处理完毕之后。假设不考虑当天收到的文件，那么文件的数量可以预置，并随着每个作业的完成递减，直至为零。,1.1 离散事件系统仿真的基本概念,实例求解,实例目标：了解仿真,求解方法：手工仿真,求解平台：Excel,求解原理：,每个文件的处理时间（工作时间,t,w,）是一个随机过程，符合一定的概率分布；,该工作人员一上班就开始处理文件，所以第一个文件处理的开始时间就是仿真的开始时间（0时刻），后续文件的开始时间,t,f,上一文件的结束时间或休息后的时间；,每一个文件处理的结束时间文件处理的开始时间文件处理时间；,设置一项统计量：累计工作时间,t,c,=休息后的工作时间之和。当,t,c,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),在给定显著性水平后，即可根据正态分布确定临界值，据此判断与理论平均值及与,X,2,理论平均值之差异是否显著，从而决定能否将产生的随机数看作是(0，1)均匀分布随机变量的,N,个独立取祥值。,服从自由度为,k,-1,的,2,分布,服从,N,(0，1),2.2 离散事件仿真建模,排队系统：由服务机构（服务模式）（可以是服务台、加工机器、搬运设备等）、到达模式及排队规则组成的集合。,库存系统：由订单到达模式、订单规模、补货数量、交货期及补货策略（盘库间隔、到货规则）组成的集合。,流程系统：由特定的一簇服务对象按照其自有的运作流程（顺序及滞留时间）将对应的服务机构（排队系统、库存系统）有序地连接在一起组成的集合。,前后事件多对一,前后事件一对多,前后事件多对多,事件的返回,离散事件系统,事件的合并,事件的拆分,离散事件系统,设备可用性。设备可以加工工件的前提是设备是可用的，设备可用的必要条件有：,（1）当前时刻是生产系统工作日志所规定的正常工作时间，而不是休息、保养、大修的时间；,（2）当前时刻设备是正常状态，而不是处于损坏、维修、冻结、堵塞等状态；,（3）当前时刻设备具备正常运行所需的所有技术条件，包括操作工人、工装、模具等；,（4）当前时刻设备空闲或设备的某一工位空闲；,离散事件系统,1）单台机器排序问题（n/1/B),n个工件全部经由一台机器处理,离散事件系统,常见单台机器排序问题的目标函数,1),平均流程时间最短,2）最大延期量最小,定义:,为最大延期量。,目标函数,为n个零件经由一台机器的平均流程时间。,定义:,目标函数：使平均流程时间最短,F,i,=P,i,+W,i,T,i,=max0,L,i,L,i,=C,i,-d,i,工件,i,的延误时间,L,i,0,延误,生产系统,离散事件系统,P,i,=,任务,i,的作业时间,W,i,=,任务,i,的开始作业时间,根据排序目标的不同，可以选择不同的,排序规则,，又称为确定零件加工的优先权。,常见的排序规则：,SPT-Shortest Process Time,优先选择加工时间最短的工件,EDD-Earliest Due Date,优先选择交货期紧的工件,FCFS-First Come First Served,按工件到达的先后顺序,CR-Critical Rate,优先选择临界比最小的工件,CR=（交货期-当前日期）/剩余加工时间,离散事件系统,2)求平均流程时间最短的排序问题,求平均流程时间最短的作业顺序，采用SPT原则。,按工件加工时间的长短，从小到大按排作业。,例：一台加工中心，现有5个工件需要该机器加工。相关的加工时间和要求完成时间（交货期）如下表所示，求平均流程时间最短的作业顺序。,J,1,J,2,J,3,J,4,J,5,加工时间,11,29,31,1,2,交货期,61,45,31,33,32,离散事件系统,解：根据SPT原则，得出：,J,4,-J,5,-J,1,-J,2,-J,3,有关项目的计算：,发生延迟,发生延迟,加工时间,开始时间,完成时间,交货期,延迟,J4,1,0,1,33,0,J5,2,1,3,32,0,J1,11,3,14,61,0,J2,29,14,43,45,0,J3,31,43,74,31,43,=43,生产系统,离散事件系统,3）求最大延期量最小的排序问题,求最大延期量最小的作业顺序采用EDD原则。,例：同上面的例子，按延期量,(完工日期-交货期）大,小，从小到大排序。,解：根据EDD原则，得出,J,3,-J,5,-J,4,-J,2,-J,1,加工时间,完成时间,交货期,延迟,J,3,31,31,31,0,J,5,2,33,32,1,J,4,1,34,33,1,J,2,29,63,45,18,J,1,11,74,61,13,生产系统,离散事件系统,=18,1、两台机器排序问题的含义(n/2/F/Fmax),n,个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。,生产系统,n项任务在两台机器的排序问题,离散事件系统,2、两台机器排序问题的目标,两台机器排序的目标是使,生产周期,F,max,最短。,F,max,的含义见如下图。,F,max,时间,机器,A,B,在机器A上的作业时间,总加工周期,生产系统,离散事件系统,3、两台机器排序问题的算法,约翰逊法(Johnsons Law)，约翰逊法解决这种问题分为4个步骤：,(1)列出所有工件在两台设备上的作业时间。,(2)找出作业时间最小者。,(3)如果该最小值是在设备1上，将对应的工件排在前面，如果该最小值是在设备2上，则将对应的工件排在后面。,(4)如果同时出现一个以上的最小值,任意选区一个.,(5)排除已安排好的工件，在剩余的工件中重复步骤(2)(4)，直到所有工件都安排完毕。,生产系统,离散事件系统,例：某一班组有A、B两台设备，要完成5个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。,工件在两台设备上的加工时间,工件编号,J1 J2 J3 J4 J5,设备A,3 6 7 1 5,设备B,2 8 6 4 3,生产系统,离散事件系统,解：由约翰逊法可知，表中最小加工时间值是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,生产系统,离散事件系统,工件在两台设备上的加工时间,工件编号,J1 J2 J3 J4 J5,设备A,3,3,6,9,7,16,1,17,5,22,设备B,2,5,8,17,6,23,4,27,3,30,（1）计算加工周期（按零件序号加工）,生产系统,离散事件系统,工件在两台设备上的加工时间,工件编号,J4 J2 J3 J5 J1,设备A,1,1,6,7,7,14,5,19,3,22,设备B,4,5,8,15,6,21,3,24,2,26,（2）计算加工周期（按约翰逊法）,生产系统,离散事件系统,(a)J1-J2-J3-J4-J5,30,A,B,26,A,B,(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 输出数据分析,终态仿真的输出分析,什么是终态仿真？,在某一个持续时间,T,E,内的系统仿真。如：生产设备的使用寿命就是这一类的系统仿真。,终态仿真的特征：系统仿真是在零时刻开始“开启”，至,T,E,时刻“关闭”，其中,T,E,可以是一个随机变量。研究的是不同持续时间,T,E,或“开启”时刻状态对系统性能参数的影响。,终态仿真的输出分析独立重复运行法,假设系统仿真进行了,n,次独立重复运行，得到,n,个系统性能测度的仿真观察值,Y,1,Y,2,Y,n,，则系统性能测度的估计量为,2.4 输出数据分析,设仿真重复进行了,R,组，,r,(=1，2，,R,)为其中的一组仿真。令,Y,ri,为第,r,组仿真中的第,i,次系统性能测度的观察值，,i,=1，2，,n,r,。此时，对每一次运行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,=,p,1,p,n,是,库所,(位置)的有限集合，,n,(0)为位置(库所)的个数;,（2）,T,=,t,1,t,m,是,变迁,的有限集合，,m,(0)为变迁的个数；,P,T,=,，,P,T,；,（3）,I,：,P,T,N,是,输入函数,，它定义了从,P,到,T,的有向弧的重复数 或权(Weight)的集合，这里,N,=0,1,为非负整数集；,（4）,O,：,T,P,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,均表示为,n,m,非负整数矩阵，,O,与,I,之差,C,=,O,-,I,称为,关联矩阵,。,Petri网的实例,例：一PN结构如图所示。按照PN的定义，该PN结构可描述如下：,P,=,p,1,p,2,p,3,；,T,=,t,1,t,2,；,I,(,p,1,t,1,)=1;,I,(,p,2,t,1,)=1;,I,(,p,3,t,1,)=0;,I,(,p,1,t,2,)=0;,I,(,p,2,t,2,)=0;,I,(,p,3,t,2,)=1;,p,2,p,3,p,1,t,1,t,2,O,(,p,1,t,1,)=0;,O,(,p,2,t,1,)=0;,O,(,p,3,t,1,)=1;,O,(,p,1,t,2,)=0;,O,(,p,2,t,2,)=1;,O,(,p,3,t,2,)=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网的实例(续),p,2,p,3,p,1,t,1,t,2,例如，,图题中：,（1）从,p,1,与,p,2,到,t,1,有弧连接，既,I,(,p,1,t,1,),0，I(,p,2,t,1,),0，说明,t,1,所表示的事件的发生以,p,1,与,p,2,所表示的局部状态为前提条件；,（2）而从,p,3,到,t,1,无弧连接，既,I,(,p,3,t,1,)=0，说明,t,1,所表示的事件的发生不取决于,p,3,所表示的局部状态；,（3）从,t,1,到,p,3,有弧连接，即,O,(,p,3,t,1,),0，表明,t,1,所表示的事件发生将影响,p,3,所表示的局部状态；,（4）而从,t,1,到其它库所无弧连接，表明,t,1,所表示的事件发生将不影响这些库所所表示的局部状态。,Petri网的五要素定义,标识PN为一5要素：,PN=PNS,m=,P,T,I,O,m,此处：,(1)PNS=,P,T,I,O,为PN结构，它由Petri网的四要素定义给出；,(2),m,:,P,N,为标识PN的标识，它为一列向量，其第,i,个元素,m,(,p,i,)表示第,i,个库所中的标识数目。,m,=(,m,(,p,1,),m,(,p,2,),m,(,p,n,),T,特别地，DES的初始状态用初始标识表示，记为,m,0,。,相同结构的标识PN不是唯一的？,Petri网的实例(续),例题,如,图（包括库所中的圆点）一个标识PN，正规地描述如下：PN=,P,T,I,O,m,0,*,P,T,I,O,见前例。,*,m,0,=(1,1,0),T,其中第,1,个元素为,m,(,p,1,)=1,第,2,个元素为,m,(,p,2,)=1,第,3,个元素为,m,(,p,3,)=0,p,2,p,3,p,1,t,1,t,2,第四章 离散事件仿真的逻辑分析 Petri网,Petri网的使能？,在DES中某一事件必须在所有前提条件（状态）得以满足（实现）的情况下才可能发生。有时，要求某一前提条件（状态）必须满足多次（实现多次）。,在DES的Petri网中，我们以变迁,t,表示一事件，用变迁的使能(Enabling)表示事件因前提条件得以满足而能够发生。我们还用,t,的输入库所（通过指向,t,的弧连接的库所）表示该事件的发生所需要的前提局部状态，用由输入库所至,t,的输入函数定义这些要求局部前提状态实现的次数；,而局部状态的实现情况由库所中所包含的标识数目来表示。,因此，变迁,t,的使能不仅与其输入函数有关，而且与其所有输入库所中的标识数目有关。为此，引入以下变迁使能规则。,使能的例子,Petri网的使能定义,一变迁,t,T,在标识,m,下使能，当且仅当：,p,t,:,m,(,p,),I,(,p,t,)。,例如：在上例中，变迁,t,1,的使能,t,1,=,p,1,p,2,，,由于,m,(,p,1,)=1,I,(,p,1,t,1,)=1，m(,p,2,)=1,I,(,p,2,t,1,)=1，,因此变迁,t,1,使能的；而,t,2,=,p,3,，由于,m,(,p,3,)=0,m,。,状态转换的例子,在右上图所示的PN中，在,m,0,=(1,1,0),T,下使能的,t,1,激发后，将产生新的标识,m,1,(见右下图)：,m,1,(,p,1,)=,m,0,(,p,1,)-,I,(,p,1,t,1,)+,O,(,p,1,t,1,),=1-1+0=0；,m,1,(,p,2,)=,m,0,(,p,2,)-,I,(,p,2,t,1,)+,O,(,p,2,t,1,),=1-1+0=0；,m,1,(,p,3,)=,m,0,(,p,3,)-,I,(,p,3,t,1,)+,O,(,p,3,t,1,),=0-0+1=1；,m,1,=(0,0,1),T,p,2,p,3,p,1,t,1,t,2,p,2,p,3,p,1,t,1,t,2,上例的计算，似乎给我们告诉了些东西：,几种特殊的PN:,若PN的所有变迁至多有1个输入弧或输出弧，即,I,:,P,T,0,1,O,:,T,P,0,1，则此PN称为,普通PN（Ordinary Petri net）,。,若PN无自闭环，即某一库所同时是某一变迁的输入与输出库所，则此PN称为,纯PN（Pure Petri net）,。,若PN的每一库所都恰好有1个输入变迁与1个输出变迁，即,p,P,:|,p,|=|,p,|=1，则该PN称为,标识图(Marked graphs),。,若PN的每一变迁都恰好有1个输入库所与1个输出库所，,t,T,:|,t,|=|,t,|=1，则该PN称为,状态机(State machine),。,第四章 离散事件仿真的逻辑分析 Petri网,若干制造系统的基本PN模型,缓冲区模型,考虑两台机器,M,1,与,M,2,之间的缓冲区,B,，假设它能够存储,k,个工件。,t,1,：,M,1,结束当前工件的加工并将该工件放入,B,中；,t,2,：从,B,中取出一个工件并在,M,2,上开始加工；,p,v,：,B,的剩余容量；,p,b,：,B,中存放的工件数量；,p,uf,：机器,M,2,是空闲的；,当缓冲区满时，,p,b,中容纳,k,个标识，而,p,v,中无标识。此时,t,1,被抑制而不能激发，机器,M,1,堵塞(Blocked)。一旦一个工件从缓冲区移至机器,M,2,，,p,v,收到1个标识，则,t,1,立即使能，生产得以恢复。,PN,的抑制弧,（Inhibitor arc）,按输入函数的定义，,p,b,中至少有,k,个标识是,t,1,使能条件。,但是，抑制弧的作用应理解为：一旦抑制弧连接的输入库所中拥有与抑制弧的权相等数量的标识，则该抑制弧将抑制该变迁的激发,。,抑制弧用一端带由小圆并旁注权值,k,的弧表示。,若干制造系统的基本PN模型,存储区溢出（Overflow）：,当缓冲区存满工件时，其存储容量已耗尽的现象。,当存储区溢出时，其前端机器被堵塞。,发生溢出时，期望提供存储区溢出的信息，并改变堵塞在机器中工件的路径，将其送至其它机器，而不是原路径上的机器,M,2,。,变迁,t,oi,的激发将输出溢出指示。,由于连接,t,oi,与,p,v,的抑制弧的权为,0,，因此只要,p,v,中包含,1,个及以上的标识(表明储料取仍然有存储空间)，则,t,oi,将被抑制激发，不产生溢出指示。,当,p,1,中包含,1,个标识(表示,1,工件被机器,M,1,加工完毕，等待从,M,1,移出)，且,p,v,中无标识(表明缓冲区堆满工件)，,t,oi,立即激发，输出溢出指示，将,p,1,中的标识送至代表其它路径的入口(图中没有画出)，而不是,p,b,。,若干制造系统的基本PN模型,FCFS,的工件队列,PN,模型,传送带是典型的先来先享受服务,(First-Come-First-Serve,FCFS),工件队列的例子，因为先放置到传送带上的工件先从传送带的另一端离开。工件在传送带上传送的过程可看作是暂时储存在传输带上,。,p,s,表示工件在传送之中，t,a,表示将工件放入传送带上。,传送带所能够传送的最多工件数由t,a,的抑制弧的权N定义。只要p,s,中的标识数不超过N，抑制弧不起作用。此时，一当工件到达，t,a,立即激发，将1标识放入p,s,中，表示工件在传送之中。,只要p,s,中有标识，一旦p,d,中有1标识(表示请求将1工件从传输带上移走)，则t,d,激发，从p,s,中取走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,个加工过程都需要资源,p,4,进行各自的操作，这是一典型的冲突问题。如前面刚提到，,t,1,与,t,3,同时使能，但只有,二,者其一能够激发。,出现冲突时，必须作出决策一决定谁优先激发。最简单的方法是采用随机确定方法。若,t,1,在冲突中获胜，则,t,1,激发并消耗,p,4,中的标识。最终，,t,2,激发从而将,1,标识放回,p,4,，表示资源得以释放。,基本,PN,性能,系统的特性可分为,行为,（Behavioral）与,结构,(Structural)特性。,行为特性是PN与初始标识有关的性能；,而结构特性与初始标识无关，它们取决于PN的拓扑结构,。,重要的结构与行为特性:,可达性(Reachability);有界性(Boundness);,安全性(Safeness);守衡性(Conservativeness);,活性(Liveness);可逆性(Reversibility)。,基本,PN,性能,可达性是PN的一个重要行为特性:,给定一PN，我们期望知道从初始标识,m,0,可以到达哪些标识;,给定一标识,m,t,，是否可以激发一系列变迁从初试标识,m,0,到达该标识。,定义,:,若从,m,0,始标识开始激发一个变迁序列产生标识,m,r,，则称,m,r,是从,m,0,可达的。若只要从,m,0,开始激发一个变迁即可产生,m,r,，则称,m,r,是从,m,0,立即可达的(Immediately reachable)。,所有从,m,0,可达的标识的集合称为可达标识集或可达集，记为R(,m,0,)。,一般地，从,m,0,到,m,r,所激发的变迁序列表示为:,s,r,t,j,1,t,jr,这里,j,1,jr,为1到,m,之间的整数。从,m,0,激发,s,r,产生,m,r,表示为：,m,0,s,r,m,r,。,例,在右图的PN中，,m,0,=(1,0,0,1,1,0,0),T,，,m,0,s,4,m,4,，这里,m,4,=,(0,0,1,1,0,0,1),T,，,s,4,=,t,3,t,4,t,1,t,2,。,对于每一个激发的变迁序列,s,r,，都可以关联一个,m,1激发向量,v,r,，该向量的第,i,个元素，对应着变迁,t,i,在,s,r,中出现的次数,n,i,。一般地，,v,r,=(,n,1,n,m,),T,。,对于一定的,v,r,，其对应的激发的变迁序列可能不是唯一的。例如，上面例子中提到的从,m,0,到达,m,4,，,v,4,=(1,1,1,1),T,所激发的对应变迁序列就有,t,3,t,4,t,1,t,2,与,t,1,t,2,t,3,t,4,两个。,基本,PN,性能,可达性可描述制造系统的,两,个问题：,(1),系统按照一定的轨迹运行,系统是否能够实现一定的状态。典型的问题是生产调度计划的验证，即按照一定的生产调度计划进行生产，一定的生产任务是否能够得以完成；,(2),要求到达一定的状态,如何确定系统的运行轨迹，典型的问题是生产调度问题。,第一个问题可以描述为：给定,s,r,、初始标识,m,0,以及期望达到的标识,m,r,，则有,m,0,s,r,m,r,，若,m,r,=,m,r,则答案是肯定的；若,m,r,m,r,，则答案是否定的。,第二个问题可以描述为：给定,m,0,与,m,r,，寻找,s,r,，使得,m,0,s,r,m,r,成立。必须指出,s,r,可能不是唯一的，通常都在一定的准则下选取优化的,s,r,。,基本,PN,性能,有界性与安全性,:,定义:,给定,PN=(,P,T,I,O,m,0,),以及其可达集,R,(,m,0,),，对于库所,p,P,，若,m,R,(,m,0,),