生产与服务系统建模与仿真课件

生产与服务系统建模与仿真生产与服务系统建模与仿真Production&Service System Modeling&Simulation 面向工程实际的应用型的基础性课程，是工业工程专业的面向工程实际的应用型的基础性课程，是工业工程专业的主导课程。主导课程。课程介绍从课程的题目中可以看出：从课程的题目中可以看出：离散系统建模与仿真离散系统建模与仿真其对象是：其对象是：离散系统离散系统生产系统是一个典型的离散系统。生产系统是一个典型的离散系统。物流系统也是一个离散系统。物流系统也是一个离散系统。目的是：仿真。即用一种抽象的、能够反映系统目的是：仿真。即用一种抽象的、能够反映系统 研究本质的研究本质的“虚假虚假”系统，来模拟实际系系统，来模拟实际系 统。而这虚假系统就是系统模型。统。而这虚假系统就是系统模型。课程性质：征求答案征求答案什么是仿真？什么是离散系统的仿真？什么是仿真？什么是离散系统的仿真？为什么需要做仿真？为什么需要做仿真？何时需要做仿真？何时需要做仿真？如何进行仿真？如何进行仿真？仿真要做那些准备工作？仿真要做那些准备工作？仿真的可信度如何评价？仿真的可信度如何评价？对仿真模型如何作评价？对仿真模型如何作评价？你知道的仿真软件有哪些？各自具有哪些特征？你知道的仿真软件有哪些？各自具有哪些特征？你希望通过本课程的学习获得些什么？你希望通过本课程的学习获得些什么？课程试图解决的问题：课程试图解决的问题：离散事件系统建模与仿真的基本原理离散事件系统建模与仿真的基本原理离散事件系统建模与仿真的方法离散事件系统建模与仿真的方法PetriPetri网建模与仿真网建模与仿真课程的先修课程：课程的先修课程：生产运作与管理生产运作与管理运筹学运筹学计算机编程与应用技术计算机编程与应用技术概率论与数理统计概率论与数理统计课程的考核方法：课程的考核方法：完成相关作业及期末考核。完成相关作业及期末考核。课程介绍课程主要内容：课程主要内容：课程主要内容构成第一章第一章离散事件仿真的概述离散事件仿真的概述第二章第二章离散事件仿真的分析离散事件仿真的分析第三章第三章离散事件仿真的案例分析离散事件仿真的案例分析第四章第四章离散事件仿真的逻辑分析离散事件仿真的逻辑分析Petri网网第一章第一章第一章第一章 离散事件仿真的概述离散事件仿真的概述离散事件仿真的概述离散事件仿真的概述 1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念1.2生产系统仿真的特征生产系统仿真的特征1.3服务系统仿真的特征服务系统仿真的特征1.4离散系统仿真的基本步骤离散系统仿真的基本步骤1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念什么是系统？什么是系统？系统是按照某些规律结合起来的，相互作用、相互依存的所有元素的集合。系统有哪些种类？系统有哪些种类？连续系统&离散系统变量状态静态系统&动态系统时域状态确定系统&随机系统存在随机变量单变量系统&多变量系统自由度数量1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念什么是系统仿真什么是系统仿真(SystematicSimulation)?仿真仿真：对现实中的现象通过某种抽象，建立表达现实变化规律或特征的模型，运用一定的手段加以描述，这就是仿真。系统仿真系统仿真：首先针对真实系统建立模型，然后在模型上进行试验，用模型代替真实系统，从而研究系统性能的方法。系统仿真将能一一仿效实际系统的各种动态活动，并把系统动态过程的状态记录下来。最终得到用户所关心的系统统计性能。1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念为什么要采用系统仿真为什么要采用系统仿真?系统所涉及到的专业知识较为广泛，如：机械、系统所涉及到的专业知识较为广泛，如：机械、生产管理、人事管理、产品设计、生产工艺等生产管理、人事管理、产品设计、生产工艺等现实问题的规律是复杂的，一般很难用一确定现实问题的规律是复杂的，一般很难用一确定的数学方程或数学函数显性地或隐性地表达。的数学方程或数学函数显性地或隐性地表达。科学技术的发展难以适应生产系统研究的需要科学技术的发展难以适应生产系统研究的需要仿真是系统特征无法用数学方程、数学函数描述仿真是系统特征无法用数学方程、数学函数描述时，为了研究系统特征所采用的一种研究方法。我们时，为了研究系统特征所采用的一种研究方法。我们可以这样说：仿真是一种可以这样说：仿真是一种“不得已而为之不得已而为之”的方法的方法1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念系统仿真方法适用怎样的领域？系统仿真方法适用怎样的领域？系统仿真的方法适用于任何的领域工程类非工程类机械电子化工交通管理经济政治1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念系统模型有哪些？系统模型有哪些？系统模型确定型模型随机型模型静态动态静态动态连续离散连续离散离散事件仿真蒙特卡洛仿真什么是离散事件系统？什么是离散事件系统？离散事件系统是包含事件的发生在时间或空间上离散事件系统是包含事件的发生在时间或空间上都是离散的都是离散的，例如交通管理、生产自动线、计算机，例如交通管理、生产自动线、计算机网络、通信系统和社会经济系统都是离散事件系统。网络、通信系统和社会经济系统都是离散事件系统。离散事件系统定义为一组元素离散事件系统定义为一组元素(实体实体)的集合，的集合，为了达到某些目的，这些元素以某些规则相互作用、为了达到某些目的，这些元素以某些规则相互作用、关联而集合在一起关联而集合在一起。例如制造系统由机器、部件以例如制造系统由机器、部件以及操作工人组成，银行系统由出纳员和顾客组成。及操作工人组成，银行系统由出纳员和顾客组成。离散事件系统的变量通常用状态变量表示，如：离散事件系统的变量通常用状态变量表示，如：实体的发生与不发生；事物的计数等等。实体的发生与不发生；事物的计数等等。1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念离散事件仿真模型的特点离散事件仿真模型的特点 -随机型：具有随机性的状态变量 -动态性：随时间演变是模型的重要特征 -离散事件：主要的变化发生在离散的时间点上1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念q事件的发生在时间和空间上都是离散的。事件的发生在时间和空间上都是离散的。系统的数字仿真则经常是面向事件的系统的数字仿真则经常是面向事件的q离散事件系统定义为一组元素离散事件系统定义为一组元素(实体实体)的集的集合，为了达到某些目的，这些元素以某些合，为了达到某些目的，这些元素以某些规则相互作用、关联而集合在一起。规则相互作用、关联而集合在一起。q离散事件系统状态变量仅仅在可数的一些离散事件系统状态变量仅仅在可数的一些时间点上才有变化时间点上才有变化。系统变量是反映系统。系统变量是反映系统各部分相互作用的一些事件，系统模型则各部分相互作用的一些事件，系统模型则是反映这些事件状态的数集，仿真结果是是反映这些事件状态的数集，仿真结果是产生处理这些事件的时间历程。产生处理这些事件的时间历程。q在离散事件系统中，各事件以某种顺序或在离散事件系统中，各事件以某种顺序或在某种条件下发生在某种条件下发生,并且大都是随机性的，并且大都是随机性的，不能用常规的方法加以研究。不能用常规的方法加以研究。连续系统事件的发生在时间和连续系统事件的发生在时间和空间上都是连续的。空间上都是连续的。在连续系统的数字仿真中，时在连续系统的数字仿真中，时间通常被分割成均匀的间隔，间通常被分割成均匀的间隔，并以一个基本的时间间隔计时。并以一个基本的时间间隔计时。在连续系统仿真中，系统动力在连续系统仿真中，系统动力学模型是由表征系统变量之间学模型是由表征系统变量之间关系的方程来描述的。关系的方程来描述的。仿真的结果为系统变量随时间仿真的结果为系统变量随时间变化的时间历程。变化的时间历程。连续系统与离散系统有何区别？1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念离散事件仿真时钟的演变方法有哪些？时间离散时间离散系统只在一些特定的时刻，即=t1,t2,上被考察。通常，为了便于研究，各时间间隔选定为整常数，t=常数。事件离散事件离散系统状态的变化，即事件时刻是不连续的、跳跃式的，t=ti+1-ti，i，ti为事件发生时间。1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念l某些系统的建模困难，如，对于大比例系统模型，建模会变得十分复杂，程序的编写与程序的运行都是十分艰巨的。但是随着优质的仿真专业软件的诞生，对于这样系统的仿真日趋简便。l仿真需要大量的计算机机时。这一问题随着计算机技术的发展正在逐步得到解决。l仿真需要大量实际的、准确的数据，这是一般企业所难以提供的，因此对仿真结果的准确性带来了影响，导致了人们对仿真能力的怀疑。总之，正是由于上述的种种因素，是人们对仿真留下了不好的印象。这里还要说明的是：仿真只是计算机编程的一种游戏，游戏的规则来自于问题的本身，游戏的范围也是问题所约定的。离散事件仿真运用存在哪些阻碍？离散事件仿真运用存在哪些阻碍？1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念离散事件仿真模型如何建立？离散事件仿真模型如何建立？如何为一个离散事件系统建立一个模型1)确定一个系统目标或仿真目的2)建立概念性概念性模型3)转换为一个详细详细模型制定仿真规则4)转换为一个计算机计算计算模型编制程序代码5)模型的运行检验特例检验6)模型的有效性检验模型检验、可信度检验典型事件的多次重复仿真循环过程1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念离散事件仿真模型的三层次模型离散事件仿真模型的三层次模型概念模型层极其概念性的层次模型（通常是语义性的系统描述）模型是如何构成的？什么是模型的状态变量，哪些是动态变量，哪些是重要变量？详细模型层模型的书面整理模型包括哪些方程，哪些伪随机数，哪些辅助变量等模型参数如何输入？计算模型层计算机程序通用编程语言或仿真语言1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念系统与系统模型的实质关联是什么？系统与系统模型的实质关联是什么？系统：系统：研究的本体研究的本体系统模型系统模型：为研究系统所收集的有关信息的集合。：为研究系统所收集的有关信息的集合。通过研究系统模型来揭示系统的性能。通过研究系统模型来揭示系统的性能。它和它和“系统系统”的定义比较，两者都是集合，系统是的定义比较，两者都是集合，系统是以某些规律结合起来、有相互作用的元素组成；而系以某些规律结合起来、有相互作用的元素组成；而系统模型是为了研究其结合规律相互作用所收集的有关统模型是为了研究其结合规律相互作用所收集的有关信息。因为收集的信息有详细、粗略之分，加上收集信息。因为收集的信息有详细、粗略之分，加上收集方法的差异和研究目的的不同，因此对于同一个系统方法的差异和研究目的的不同，因此对于同一个系统就会出现多种不同的系统模型。模型是为系统服务的，就会出现多种不同的系统模型。模型是为系统服务的，因此，所揭示的性能规律应该是稳定的。因此，所揭示的性能规律应该是稳定的。1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念离散事件仿真的输入数据该如何收集和处理？仿真的输入数据来源于事件采集稳定的数据仿真的输入数据应该与实际数据有同样的变化规律拟合度检验仿真的输入数据应当是相互独立的相关性检验1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念离散事件仿真的输出数据应该有哪些分析？仿真结果的可信度分析仿真运行的效率分析仿真结果的性能分析离散事件系统仿真模型的简例 某某一一个个工工作作人人员员每每日日的的工工作作是是处处理理文文件件，他他从从每每天天开开始始工工作作时时即即处处理理文文件件，直直至至文文件件处处理理完完毕毕或或工工作作结结束束，每每一一个个文文件件处处理理完完毕毕后后开开始始下下一一个个文文件件的的处处理理，工工作作间间隔隔一一小小时时休休息息一一次次，休休息息时时间间为为5 5分分钟钟，但但必必须须是是在在一一个个文文件件处处理理完完毕毕之之后后。假假设设不不考考虑虑当当天天收收到到的的文文件件，那那么么文文件件的的数数量量可可以以预预置置，并并随随着着每每个个作作业业的的完完成成递递减减，直直至为零。至为零。1.1离散事件系统仿真的基本概念离散事件系统仿真的基本概念实例求解实例目标：了解仿真实例目标：了解仿真求解方法：手工仿真求解方法：手工仿真求解平台：求解平台：Excel求解原理：求解原理：每个文件的处理时间（工作时间每个文件的处理时间（工作时间tw）是一个随机过程，符合一定的）是一个随机过程，符合一定的概率分布；概率分布；该工作人员一上班就开始处理文件，所以第一个文件处理的开始时该工作人员一上班就开始处理文件，所以第一个文件处理的开始时间就是仿真的开始时间（间就是仿真的开始时间（0时刻），后续文件的开始时间时刻），后续文件的开始时间tf上一文上一文件的结束时间或休息后的时间；件的结束时间或休息后的时间；每一个文件处理的结束时间文件处理的开始时间文件处理时间；每一个文件处理的结束时间文件处理的开始时间文件处理时间；设置一项统计量：累计工作时间设置一项统计量：累计工作时间tc=休息后的工作时间之和。当休息后的工作时间之和。当tc1小时，则置为零，同时标识一次休息；仿真时间推进小时，则置为零，同时标识一次休息；仿真时间推进5分钟。分钟。1.2 1.2 生产系统仿真的特征生产系统仿真的特征产品工艺技术与生产管理的结合相同的结果可以有不同的生产工艺生产管理策略对生产运作产生何种影响稳定的生产过程生产流程的稳定生产时间规律化变化生产过程存在不确定变化人工干预生产作业的不确定变化及学习变化机器设备的不确定故障停机1.3 1.3 服务系统仿真的特征服务系统仿真的特征服务技术与服务管理的结合相同结果可以有不同的服务流程服务策略对服务运作产生何种影响客户化的服务过程服务流程随着客户需求而改变服务时间的不确定变化服务过程存在不确定变化服务流程的不确定服务时间的不确定服务资源配置的不确定客户数量、需求的不确定1.4 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+WiTi=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个工件需要该机器加工。相关的加工时间和要求完成时间（交货期）如下表所示，求平均流程时间最短的作业顺序。J1J2J3J4J5加工时间11293112交货期6145313332离散事件系统解：根据SPT原则，得出：J4-J5-J1-J2-J3有关项目的计算：发生延迟发生延迟加工时间开始时间完成时间交货期延迟J4101330J5213320J111314610J2291443450J33143743143=43生产系统离散事件系统3）求最大延期量最小的排序问题 求最大延期量最小的作业顺序采用EDD原则。例：同上面的例子，按延期量(完工日期-交货期）大小，从小到大排序。解：根据EDD原则，得出 J J3 3-J-J5 5-J-J4 4-J-J2 2-J-J1 1加工时间完成时间交货期延迟J33131310J5233321J4134331J229634518J111746113生产系统离散事件系统=181、两台机器排序问题的含义、两台机器排序问题的含义(n/2/F/Fmax)n个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。生产系统n项任务在两台机器的排序问题离散事件系统2、两台机器排序问题的目标、两台机器排序问题的目标两台机器排序的目标是使生产周期Fmax最短。Fmax的含义见如下图。Fmax 时间 机器AB在机器A上的作业时间总加工周期生产系统离散事件系统3、两台机器排序问题的算法、两台机器排序问题的算法约翰逊法(JohnsonsLaw)，约翰逊法解决这种问题分为4个步骤：(1)列出所有工件在两台设备上的作业时间。(2)找出作业时间最小者。(3)如果该最小值是在设备1上，将对应的工件排在前面，如果该最小值是在设备2上，则将对应的工件排在后面。(4)如果同时出现一个以上的最小值,任意选区一个.(5)排除已安排好的工件，在剩余的工件中重复步骤(2)(4)，直到所有工件都安排完毕。生产系统离散事件系统例：某一班组有A、B两台设备，要完成5个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。工件在两台设备上的加工时间工件编号J1J2J3J4J5设备A36715设备B28643生产系统离散事件系统解：由约翰逊法可知，表中最小加工时间值是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生产系统离散事件系统工件在两台设备上的加工时间工件编号J1J2J3J4J5设备A3369716117522设备B25817623427330（1）计算加工周期（按零件序号加工）生产系统离散事件系统工件在两台设备上的加工时间工件编号J4J2J3J5J1设备A1167714519322设备B45815621324226（2）计算加工周期（按约翰逊法）生产系统离散事件系统(a)J1-J2-J3-J4-J530AB26AB(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，RR次独立重复运行后，系统性能测度的估计量为上式可以看到：标准差的估计量随着R的增加而减小。即仿真的可信度有所提高。2.4输出数据分析输出数据分析稳态仿真的输出分析什么是稳态仿真？2.4输出数据分析输出数据分析提高仿真效率的数据处理方法第四章第四章离散事件仿真的逻辑分析离散事件仿真的逻辑分析Petri网网什么是Petri网？在定义Petri网(PetriNet)时，必须要区别PN结构与标识PN(MarkedPetriNet)。它定义了DES(DiscreteEventSystem)可能的状态、事件、及其它们之间的关系，这相当于连续状态变量系统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：TPN是输出函数，它定义了从T到P的有向弧的重复数或权的集合。在表示PN结构的有向图中，库所用圆表示；变迁用长方形或粗实线段表示；若从位置p到变迁t的输入函数取值为非负整数w，记为I I(p p,t t)=)=w w，则用从p到t的一有向弧并旁注w表示；若从变迁t到位置p的输出函数取值非负整数w，记为O O(p p,t t)=)=w 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;p2p3p1t1t2O(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网的实例(续)p2p3p1t1t2例如，例如，例如，例如，图题中：（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。相同结构的标识相同结构的标识相同结构的标识相同结构的标识PNPN不是唯一的？不是唯一的？不是唯一的？不是唯一的？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)=0p2p3p1t1t2第四章第四章离散事件仿真的逻辑分析离散事件仿真的逻辑分析Petri网网Petri网的使能？在DES中某一事件必须在所有前提条件（状态）得以满足（实现）的情况下才可能发生。有时，要求某一前提条件（状态）必须满足多次（实现多次）。在DES的Petri网中，我们以变迁t表示一事件，用变迁的使能(Enabling)表示事件因前提条件得以满足而能够发生。我们还用t的输入库所（通过指向t的弧连接的库所）表示该事件的发生所需要的前提局部状态，用由输入库所至t的输入函数定义这些要求局部前提状态实现的次数；而局部状态的实现情况由库所中所包含的标识数目来表示。因此，变迁因此，变迁因此，变迁因此，变迁t t 的使能不仅与其输入函数有关，而且与其所有输的使能不仅与其输入函数有关，而且与其所有输的使能不仅与其输入函数有关，而且与其所有输的使能不仅与其输入函数有关，而且与其所有输入库所中的标识数目有关。为此，引入以下变迁使能规则。入库所中的标识数目有关。为此，引入以下变迁使能规则。入库所中的标识数目有关。为此，引入以下变迁使能规则。入库所中的标识数目有关。为此，引入以下变迁使能规则。使能的例子Petri网的使能定义一变迁一变迁t t T T在标识在标识m m下使能，当且仅当：下使能，当且仅当：p pt t:m m(p p)I I(p p,t t)。例如：在上例中，变迁t1的使能t1=p1,p2，由于m(p1)=1I(p1,t1)=1，m(p2)=1I(p2,t1)=1，因此变迁t1使能的；而t2=p3，由于m(p3)=0 mm。状态转换的例子在右上图所示的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；m m1 1=(0,0,1)=(0,0,1)T Tp2p3p1t1t2p2p3p1t1t2上例的计算，似乎给我们告诉了些东西：几种特殊的几种特殊的几种特殊的几种特殊的PN:PN:若PN的所有变迁至多有1个输入弧或输出弧，即I:PT0,1,O:TP0,1，则此PN称为普通普通普通普通PNPN（OrdinaryPetrinetOrdinaryPetrinet）。若PN无自闭环，即某一库所同时是某一变迁的输入与输出库所，则此PN称为纯纯纯纯PNPN（PurePetrinetPurePetrinet）。若PN的每一库所都恰好有1个输入变迁与1个输出变迁，即pP:|p|=|p|=1，则该PN称为标识图标识图标识图标识图(Markedgraphs)(Markedgraphs)。若PN的每一变迁都恰好有1个输入库所与1个输出库所，tT:|t|=|t|=1，则该PN称为状态机状态机状态机状态机(State(Statemachine)machine)。第四章第四章离散事件仿真的逻辑分析离散事件仿真的逻辑分析Petri网网若干制造系统的基本若干制造系统的基本PNPN模型模型缓冲区模型缓冲区模型缓冲区模型缓冲区模型考虑两台机器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的弧表示。若干制造系统的基本若干制造系统的基本PNPN模型模型存储区溢出（存储区溢出（Overflow）：）：当缓冲区存满工件时，其存储容量已耗尽的现象。当存储区溢出时，其前端机器被堵塞。当存储区溢出时，其前端机器被堵塞。发生溢出时，期望提供存储区溢出的信息，并改变堵塞在机器中工件的路径，将其送至其它机器，而不是原路径上的机器M2。变迁toi的激发将输出溢出指示。由于连接toi与pv的抑制弧的权为0，因此只要pv中包含1个及以上的标识(表明储料取仍然有存储空间)，则toi将被抑制激发，不产生溢出指示。当p1中包含1个标识(表示1工件被机器M1加工完毕，等待从M1移出)，且pv中无标识(表明缓冲区堆满工件)，toi立即激发，输出溢出指示，将p1中的标识送至代表其它路径的入口(图中没有画出)，而不是pb。若干制造系统的基本若干制造系统的基本PNPN模型模型FCFSFCFS的工件队列的工件队列的工件队列的工件队列PNPN模型模型模型模型 传送带是典型的先来先享受服务(First-Come-First-Serve,FCFS)工件队列的例子，因为先放置到传送带上的工件先从传送带的另一端离开。工件在传送带上传送的过程可看作是暂时储存在传输带上。ps表示工件在传送之中，ta表示将工件放入传送带上。传送带所能够传送的最多工件数由ta的抑制弧的权N定义。只要ps中的标识数不超过N，抑制弧不起作用。此时，一当工件到达，ta立即激发，将1标识放入ps中，表示工件在传送之中。只要ps中有标识，一旦pd中有1标识(表示请求将1工件从传输带上移走)，则td激发，从ps中取走1标识，一工件离开传送带。若干制造系统的基本若干制造系统的基本PNPN模型模型描述制造系统的并行与同步特征描述制造系统的并行与同步特征PN模型模型制造过程中，许多操作同时进行。例如，某一部件由2个零件装配而成，2个零件分别由2条独立的生产线加工，则装配只能在每一零件加工完毕后才能进行。2个零件的加工过程是并行的(Concurrent)，通过装配的开始而同步(Synchronized)。左图所示的PN，假设p1中的标识表示放置在一托盘上的2个工件到达，t1表示拆卸操作：将一个工件从托盘上移走并放入p2中，如此同时将另一工件连同托盘送至p3。可以看到PN中的一个初始标识现在变为2个标识，也就是说，网中总标识数是可变的。还发现该模型中从t1分出2条不同的路径，每一路径代表一个加工过程，它们是并行的；两个过程在t3处合并从而同步。若干制造系统的基本若干制造系统的基本PNPN模型模型制造系统另一常见的现象是两个以上的操作共享同一资源，例2台机器共享一套刀具。对于资源的竞争将导致冲突冲突冲突冲突(Conflict)(Conflict)。在PN中，资源表示为库所，操作表示为变迁。因此，在在在在PNPN中，资源的冲突表现为某一库所被中，资源的冲突表现为某一库所被中，资源的冲突表现为某一库所被中，资源的冲突表现为某一库所被2 2个及其以上个及其以上个及其以上个及其以上变迁共享同一个输入库所变迁共享同一个输入库所变迁共享同一个输入库所变迁共享同一个输入库所。根据标识图的定义，它不能描述资源冲突。左图中2个加工过程都需要资源p4进行各自的操作，这是一典型的冲突问题。如前面刚提到，t1与t3同时使能，但只有二者其一能够激发。出现冲突时，必须作出决策一决定谁优先激发。最简单的方法是采用随机确定方法。若t1在冲突中获胜，则t1激发并消耗p4中的标识。最终，t2激发从而将1标识放回p4，表示资源得以释放。基本基本PN性能性能系统的特性可分为行为行为行为行为（Behavioral）与结构结构结构结构(Structural)特性。行为特性是行为特性是行为特性是行为特性是PNPN与初始标识有关的性能；与初始标识有关的性能；与初始标识有关的性能；与初始标识有关的性能；而结构特性与初始标识无关，它们取决于而结构特性与初始标识无关，它们取决于而结构特性与初始标识无关，它们取决于而结构特性与初始标识无关，它们取决于PNPN的拓扑结的拓扑结的拓扑结的拓扑结构构构构。重要的结构与行为特性重要的结构与行为特性重要的结构与行为特性重要的结构与行为特性:可达性(Reachability);有界性(Boundness);安全性(Safeness);守衡性(Conservativeness);活性(Liveness);可逆性(Reversibility)。基本基本PN性能性能可达性是可达性是可达性是可达性是PNPN的一个重要行为特性的一个重要行为特性的一个重要行为特性的一个重要行为特性:给定一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，m0s s4m4，这里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)(Deadtransition)或者死锁死锁死锁死锁(Deadlock)(Deadlock)从反面描述PN的活性。若存在mR，不存在从m开始的变迁序列，该序列的激发使得t使能，则变迁t为死变迁。若存在mR，在此m下无任何变迁使能，则称PN包含一死锁包含一死锁包含一死锁包含一死锁、该标识为死标识死标识死标识死标识(Deadmarking)(Deadmarking)。基本基本PN性能性能死变迁死变迁死变迁死变迁(Deadtransition)(Deadtransition)或死锁死锁死锁死锁(Deadlock)(Deadlock)基本基本PN性能性能出现死锁的原因是不合理的资源分配策略或某些或全部资源的耗尽。在自动制造系统中，许多资源（如机器、包括AGV与机器人在内的物料搬运设备、以及缓冲区存放空间）是共享的。在这样的资源共享系统中，下列4个情况可能同时满足，从而导致锁死：互互互互斥斥斥斥：一资源不可以为2个或2个以上过程同时使用，一过程排斥其它过程对于该资源的占用。占占占占用用用用且且且且等等等等待待待待：一过程已被许可占用某一或某些资源，同时又在请求占用其它资源。无无无无抢抢抢抢占占占占：已分配给某一过程的资源不能从该过程中抢走，除非该过程使用此资源完毕后而释放。循循循循环环环环等等等等待待待待：2个或更多过程排成一个链，链上每一过程都在等待一个正在被链上下一个过程占用的资源。制造系统出现死锁的例子制造系统出现死锁的例子 柔性制造系统的某一机器入出缓冲区占用着一托盘，其上存放着已加工完毕的零件。而另一存放待加工工件的托盘也被自动导向车(AGV)传送至该入出缓冲区。假设入出缓冲区只能存放一个托盘，而AGV也只能放置一个托盘。此时，存放着已加工的零件托盘不能从入出缓冲区移至AGV上，AGV也不能进入缓冲区将其上面存放着的待加工的工件的托盘送至入出件堆放区。缓冲区与AGV为2个资源，将托盘从缓冲区移至AGV上与将托盘从AGV上送至缓冲区为2个过程。前者占用着缓冲区而等待着AGV，而后者占用着AGV而等待缓冲区，上述4个条件同时成立，因而出现死锁。基本基本PN性能性能可逆性可逆性可逆性可逆性(Reversibility)(Reversibility)(Reversibility)(Reversibility)与主宿状态与主宿状态与主宿状态与主宿状态(Home state)(Home state)(Home state)(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，则称该PNPN相对于矢量相对于矢量相对于矢量相对于矢量w 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部分守衡。基于基于PNPN制造系统性能分析制造系统性能分析 基于可达图与覆盖图的分析基于可达图与覆盖图的分析 从初始标识m0开始，期望到处PN所有可能的标识，这些标识通过变迁而关联。我们将所有标识以及产生这些标识的变迁用一图形表示，图中的节点为标识，节点之间用表示变迁的带箭头的线或弧连接，带箭头的线起端所连接的标识通过由该线所代表的变迁的激发，产生该线末端所连接的标识。这样的图称为可达图可达图可达图可达图。若PN是无界的或PN所描述的系统具有无限个状态，则可达图将无止境扩展。取而代之，我们将构建覆盖树覆盖树覆盖树覆盖树(Coverabilitytree)，它是无限可达图的有限表达方法。它是无限可达图的有限表达方法。基于基于PNPN制造系统性能分析制造系统性能分析定义定义定义定义：标识m2覆盖m1，即m2m1，若pP：m2(p)m1(p)。移入一特别符号，它代表“准-无限大”，用于表示任意大的标识数。遵循以下四个运算规则，使得对于任意正数k，都有：(1)k m），则对于那些使m(p)m(p)成立的p：用取代m(p)；3)以m为一节点，从m至m画一有向线，将其并记为t，并将m记为“new”；5.除去m的“new”标志；基于基于PNPN制造系统性能分析制造系统性能分析例:构建图(a)所示的具有无限储料空间之间缓冲区的二机器生产线的覆盖树。初始标识为m0=(10010)T在m0下只有t1使能。激发t1将产生m1=(0 1 0 1 0)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”标识存在.基于基于PNPN制造系统性能分析制造系统性能分析根据上述方法，由图(b)所示的覆盖树可知，图(a)所示的PN是无界的，且除了p3其它库所是安全的。还可知该PN不包含死变迁，因为所有变迁都在树中出现。由于树中出现，我们无法作出该PN是否活的与可逆的结论。基于基于PNPN制造系统性能