生产系统建模与仿真课件.ppt

南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 4.14.1系统建模方法概述系统建模方法概述 连续系统可以借助相关数学理论，对系统加以描述和连续系统可以借助相关数学理论，对系统加以描述和求解。求解。离散事件系统研究最早以排队现象和排队网络为对象。离散事件系统研究最早以排队现象和排队网络为对象。上世纪上世纪7070年代前后，年代前后，FMSFMS、大规模计算机、网络通信、大规模计算机、网络通信、机场调度等复杂离散事件系统的相继出现，推动了离散事机场调度等复杂离散事件系统的相继出现，推动了离散事件动态系统（件动态系统（DEDS)DEDS)理论的形成和发展。理论的形成和发展。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 DEDSDEDS系统的特征：系统的特征：离散事件离散事件是构成系统的是构成系统的基本要素基本要素，也是导致系统，也是导致系统状状态演变态演变并触发并触发新的事件新的事件的基本原因。的基本原因。离散离散事件事件发生的发生的时刻时刻受系统受系统结构、参数、状态结构、参数、状态以及以及环境环境的共同的共同影响影响，具有，具有随机性随机性和不确定性，使得系统和不确定性，使得系统状态的变化也具有状态的变化也具有不确定性不确定性。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 研究研究DEDSDEDS的过程就是分析因离散事件发生而导的过程就是分析因离散事件发生而导致的系统状态演变的过程，研究的致的系统状态演变的过程，研究的目标包括目标包括：控：控制制不期望事件不期望事件的发生，使的发生，使事件按预定的时刻或顺事件按预定的时刻或顺序序发生。发生。DEDSDEDS的运行和控制的运行和控制多基于人为多基于人为的运行规则或决的运行规则或决策逻辑，而不是物理学定律。策逻辑，而不是物理学定律。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 模型模型反映了系统反映了系统结构结构、参数参数及其主要及其主要行为行为之间的之间的关系，是系统关系，是系统设计设计、运行运行和和控制控制的基础。的基础。模型的表征形式：数学方程、曲线、图表、程序、模型的表征形式：数学方程、曲线、图表、程序、语言、数据集等。语言、数据集等。与连续系统相比，离散事件系统建模存在不少困与连续系统相比，离散事件系统建模存在不少困难，主要表现在：难，主要表现在：离散事件发生在离散事件发生在某个时刻某个时刻，具有，具有离散性离散性。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 离散系统的性能指标常具有离散系统的性能指标常具有离散特征离散特征，如制造，如制造系统的系统的产量产量、零件的、零件的加工时间加工时间。系统中随机性因素和概率化特征普遍存在。系统中随机性因素和概率化特征普遍存在。复杂离散系统常具有复杂离散系统常具有分层分层和和递阶递阶特征。特征。如：企业生产计划：长期、中期和短期，如：企业生产计划：长期、中期和短期，组织结构：集团、公司、分公司、车间、班组等组织结构：集团、公司、分公司、车间、班组等 南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 对于复杂离散事件系统，为降低建模和分析的对于复杂离散事件系统，为降低建模和分析的难度，通常将系统分解为若干既难度，通常将系统分解为若干既相对独立相对独立又相互又相互作用的作用的子系统子系统。在完成局部和低层次系统建模的基础上，再构在完成局部和低层次系统建模的基础上，再构建建整个系统模型整个系统模型。如进销存系统：如进销存系统：采购子系统、销售子系统和库存管理子系统。采购子系统、销售子系统和库存管理子系统。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 存在状态爆炸性和计算可行性问题。存在状态爆炸性和计算可行性问题。离散事件系统的离散事件系统的状态数量状态数量与与系统变量系统变量之间呈之间呈排列排列组合组合的关系。的关系。一般地，系统一般地，系统状态状态随着系统规模按随着系统规模按指数指数方式增方式增加，存在加，存在“状态爆炸状态爆炸”问题，由此导致模型求解问题，由此导致模型求解时计算量的急剧增加，给模型的求解带来困难。时计算量的急剧增加，给模型的求解带来困难。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 根据建模手段和目标，可以将根据建模手段和目标，可以将DEDSDEDS模型分为三个模型分为三个层次：层次：逻辑层次逻辑层次 代数层次代数层次 统计性能层次。统计性能层次。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 逻辑层次逻辑层次：分析和研究：分析和研究事件事件与系统与系统状态状态的的对应对应关系关系。主要数学工具：主要数学工具：形式语言有限自动机、活动形式语言有限自动机、活动循环图法、循环图法、PetriPetri网、马尔可夫链（网、马尔可夫链（Markov Markov chainchain）等。）等。代数层次：代数层次：研究研究DEDSDEDS的代数特性和运动过程。的代数特性和运动过程。主要数学工具主要数学工具：极大极小代数等：极大极小代数等南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 统计性能层次：统计性能层次：研究随机条件下研究随机条件下DEDSDEDS的统计性的统计性能特性及其优化问题。能特性及其优化问题。主要建模工具：主要建模工具：排队论、库存模型、摄动分析排队论、库存模型、摄动分析法、半马尔可夫过程等。法、半马尔可夫过程等。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 离散事件动态系统是一门处于离散事件动态系统是一门处于发展中发展中的学科。的学科。目前还目前还没有没有形成形成统一的统一的和具有和具有普适性普适性的建模理论的建模理论与方法。与方法。本章以本章以制造系统制造系统为主要建模为主要建模对象对象，介绍几种，介绍几种体系体系较完整较完整且得到且得到较多较多工程工程应用应用的离散事件系统建模的离散事件系统建模方法。方法。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 4.24.2活动循环图法活动循环图法4.2.14.2.1活动循环图法的基本原理活动循环图法的基本原理活动循环图（活动循环图（ACDACD）法：）法：以图形直观地显示系统状态及其变化，具有形象、以图形直观地显示系统状态及其变化，具有形象、便于理解和分析等特点，在制造系统（如作业车便于理解和分析等特点，在制造系统（如作业车间、柔性制造系统等）中的应用较为广泛。间、柔性制造系统等）中的应用较为广泛。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 ACDACD（活动循环图法活动循环图法）实体状态循环发生变化，有静止（也称队列）和实体状态循环发生变化，有静止（也称队列）和活动两种状态，且交替出现。活动两种状态，且交替出现。以以圆圈圆圈（）表示实体的）表示实体的静止状态静止状态以以矩形矩形（）表示实体的）表示实体的活动状态活动状态以有向弧（以有向弧（）表示状态与状态之间的转换。）表示状态与状态之间的转换。如系统中有如系统中有多个实体多个实体时，用时，用不同颜色不同颜色或或线型线型的的有向弧，以区分不同的实体。有向弧，以区分不同的实体。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 系统的状态系统的状态是全部是全部实体状态实体状态变化的变化的集合集合。因此，单个实体的活动在因此，单个实体的活动在ACDACD法中占有重要地位。法中占有重要地位。当对象比较复杂、实体数目较多时，可以对系统建当对象比较复杂、实体数目较多时，可以对系统建立不立不同层次同层次的的ACDACD模型模型，将高层次模型进一步分解为，将高层次模型进一步分解为低层次的模型。低层次的模型。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 4.2.2 ACD4.2.2 ACD法的建模方法与建模过程法的建模方法与建模过程 一个活动的发生要满足条件：一个活动的发生要满足条件：所有前置队列（进所有前置队列（进入活动的实体队列）入活动的实体队列）中都具有符合规则的、足够数中都具有符合规则的、足够数量的令牌（量的令牌（tokentoken）。）。一个活动可以同时发生多起（如生产车间中几台一个活动可以同时发生多起（如生产车间中几台机床同时处于加工活动）机床同时处于加工活动）活动持续时间可以是活动持续时间可以是常数常数，或，或随机数随机数，或者按照，或者按照某种规律变化。某种规律变化。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 在绘制活动循环图时，可将实体按照某种行为特征在绘制活动循环图时，可将实体按照某种行为特征加以分类。加以分类。例如，将机床分为例如，将机床分为“加工加工”与与“空闲空闲”状态，工状态，工人分为人分为“工作工作”与与“等待等待”状态等。状态等。另外，还可以对同类型的实体进行分类，如将机另外，还可以对同类型的实体进行分类，如将机床分为床分为“铣床铣床”与与“车床车床”，工人分为，工人分为“操作工操作工”和和“维修工维修工”等。等。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 ACDACD法常用术语有：法常用术语有：（1)1)实体（实体（entity)entity)。实体是指组成系统的各种。实体是指组成系统的各种要素，它是要素，它是ACDACD中产生活动的主体。中产生活动的主体。例如，例如，FMSFMS中的机床、工件、托盘、小车、机械中的机床、工件、托盘、小车、机械手等。手等。可用文字说明或不同线型表示不同的实体。可用文字说明或不同线型表示不同的实体。实体数量实体数量可在实体名称后用圆括号加数字说明。可在实体名称后用圆括号加数字说明。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 （2)2)活动（活动（activity)activity)。活动表示实体正处于。活动表示实体正处于某种动作状态。某种动作状态。一般用一般用矩形框矩形框表示。表示。活动名称用文字标注在活动名称用文字标注在矩形框矩形框中。中。活动持续活动持续时间时间（也称活动（也称活动周期周期），可标注在），可标注在活动的活动的矩形框下方矩形框下方。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 (3)(3)队列（队列（queue)queue)。队列用来表示实体处于。队列用来表示实体处于静止静止或或等待等待状态。状态。一般，队列用一般，队列用圆圈圆圈来表示，并在圆圈中注明队来表示，并在圆圈中注明队列的性质。列的性质。(4(4）实体的行为模式：在）实体的行为模式：在ACDACD模型中，实体行为模型中，实体行为始终始终遵循遵循“活动活动队列队列活动活动 ”的交替变的交替变化规则，称为实体的行为模式。化规则，称为实体的行为模式。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 (5)(5)直联活动直联活动和和虚拟队列虚拟队列 如某一活动完成后，其后续活动就立即开始，如某一活动完成后，其后续活动就立即开始，则称后续活动为则称后续活动为直联活动直联活动。为为遵循遵循实体的行为模式（状态交替变化），在实体的行为模式（状态交替变化），在这两个活动之间插入一个这两个活动之间插入一个等待时间为零等待时间为零的的队列队列，这种队列称为这种队列称为虚拟队列虚拟队列。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 （6 6）合作活动合作活动 如果一个活动要求如果一个活动要求有多于一个有多于一个（或一类）的实（或一类）的实体参加才能开始，则称这种活动为体参加才能开始，则称这种活动为合作活动合作活动。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 例：某机械加工系统例：某机械加工系统两个实体两个实体：一台半自动：一台半自动机床机床和一个操作和一个操作工人工人。工人：工人：安装工件和取下工件。安装工件和取下工件。工件安装完毕后，机床自动完成工件加工。工件安装完毕后，机床自动完成工件加工。加工完毕，机床停止，直到工人安装一个新的工加工完毕，机床停止，直到工人安装一个新的工件，再开始下一个加工循环。件，再开始下一个加工循环。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 完成各实体活动循环图之后，可将活动循环图集完成各实体活动循环图之后，可将活动循环图集成起来，构成成起来，构成活动循环图活动循环图。D D表示持续时间。表示持续时间。图图4.3 4.3 机械加工系统的活动循环图机械加工系统的活动循环图南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 系统中的实体之间存在合作关系。系统中的实体之间存在合作关系。合作活动合作活动：只有当参与合作活动的实体都在该活动的：只有当参与合作活动的实体都在该活动的前置队列存在时。前置队列存在时。如如“安装安装”是是机床和工人机床和工人的的合作活动合作活动：要同时有：要同时有工工人人在在“等待等待”状态和状态和机床机床处于处于“空闲空闲”状态。状态。如果只满足其中一个条件，则另一个实体将在队列如果只满足其中一个条件，则另一个实体将在队列中等待，从而造成设备和资源闲置、系统性能下降。中等待，从而造成设备和资源闲置、系统性能下降。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 当一个当一个活动开始活动开始时，相应的时，相应的实体实体从从前置队列（静止前置队列（静止状态）状态）中移至该中移至该活动状态活动状态。在在ACDACD图中，令牌（图中，令牌（tokentoken）表示实体当前的状态。）表示实体当前的状态。当当活动结束活动结束时，时，令牌令牌从该活动移人相关的从该活动移人相关的后续队列后续队列。一个活动完成后，实体被释放，从而为后续活动创一个活动完成后，实体被释放，从而为后续活动创造条件。造条件。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 图图4.14.1机床的活动循环图机床的活动循环图 4.24.2工人的活动循环图工人的活动循环图 南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 ACDACD模型是按照实体模型是按照实体类型类型建立的，与建立的，与同类型同类型实体的实体的数量无关数量无关。即使系统中的实体类型和活动周期不同，只要系统即使系统中的实体类型和活动周期不同，只要系统的行为模式相同，也可以用同一个的行为模式相同，也可以用同一个ACDACD图加以描述。图加以描述。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 为了表示不同类型的为了表示不同类型的实体数量实体数量，可在各实体，可在各实体名称后面括号中的数字表示，缺省值为名称后面括号中的数字表示，缺省值为1 1。图图4.4 4.4 表示系统中有表示系统中有3 3台机床和台机床和1 1个工人个工人南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 在系统模型中，存在所谓的在系统模型中，存在所谓的逻辑实体逻辑实体。例例:工人除工人除 “安装安装”活动外，还安排有活动外，还安排有“休息休息”活动。活动。图图4.5 4.5 有工人休息活动的机械加工系统活动循环图有工人休息活动的机械加工系统活动循环图 南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 在在ACDACD建模过程中，系统中的一些实体需要建模过程中，系统中的一些实体需要与与周围环境周围环境发生交互发生交互作用作用，例如待加工的毛坯就，例如待加工的毛坯就是来自于环境的。是来自于环境的。因此，在因此，在ACDACD建模时，需要考虑实体的建模时，需要考虑实体的到达到达活动活动，即实体从系统外，即实体从系统外越过边界越过边界进人系统的进人系统的活活动动。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 4.2.3 ACD4.2.3 ACD模型的仿真运行模型的仿真运行 ACDACD模型反映了系统中的实体及其所具有的活动。模型反映了系统中的实体及其所具有的活动。ACDACD模型如何运行？模型如何运行？以图以图4-54-5中的工人而言，系统运行时他将面临中的工人而言，系统运行时他将面临“活动选择活动选择”问题，即当某一时刻问题，即当某一时刻“安装安装”和和“休息休息”两个活动都可以开始时，究竟应该选择哪一个活动两个活动都可以开始时，究竟应该选择哪一个活动作为下一个活动？作为下一个活动？南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 ACD ACD模型通过定义活动的优先权（模型通过定义活动的优先权（prioritypriority）和制）和制定活动的规则（定活动的规则（rulerule）等方法加以解决此类问题。）等方法加以解决此类问题。优先权方法：优先权方法：根据活动的重要性给活动分配不同的级根据活动的重要性给活动分配不同的级别，当两个活动可以同时发生时，别，当两个活动可以同时发生时，优先级高优先级高的活动优的活动优先安排先安排。对于多数机械加工系统，对于多数机械加工系统，“安装安装”活动的优先级活动的优先级应高于应高于“休息休息”活动的优先级。活动的优先级。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 当机床的前置队列为当机床的前置队列为“空闲空闲”时（表示系统中有机时（表示系统中有机床可以利用），工人将先进行床可以利用），工人将先进行“安装安装”活动。活动。只有在只有在“安装安装”活动不能进行且符合活动不能进行且符合“休息休息”活动活动的时间安排时，工人才能的时间安排时，工人才能“休息休息”。如果如果“休息休息”活动的级别比活动的级别比“安装安装”活动的级别活动的级别高，可能会因工人的高，可能会因工人的“休息休息”活动而使得机床处于活动而使得机床处于“空闲空闲”状态，影响系统的效率。状态，影响系统的效率。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 另外，也可以根据系统实际，制定控制系统运行的另外，也可以根据系统实际，制定控制系统运行的调度规则调度规则，合理地安排系统的，合理地安排系统的活动次序活动次序，提高系统的，提高系统的运行效率运行效率。下面以图。下面以图4-64-6所示的所示的ACDACD为例，分析为例，分析规则在系统仿真中的作用。规则在系统仿真中的作用。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 另外，也可以根据系统实际，制定控制系统运行的另外，也可以根据系统实际，制定控制系统运行的调度规则调度规则，合理地安排系统的活动次序，提高系统的，合理地安排系统的活动次序，提高系统的运行效率。以图运行效率。以图4-64-6为例，为例，调度规则作用。调度规则作用。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 该机械加工系统由三台半自动机床（图中以该机械加工系统由三台半自动机床（图中以、表示）和一个工人组成，初始时三台机床均处于表示）和一个工人组成，初始时三台机床均处于“空闲空闲”状态，工人处于状态，工人处于“等待等待”状态。状态。若三台机床若三台机床“加工加工”活动和活动和“安装安装”活动的周期各活动的周期各不相等，工人应该先为哪一台机床提供不相等，工人应该先为哪一台机床提供“安装安装”服务服务？“加工加工”周期最长或最短？周期最长或最短？“安装安装”周期最长或最短？周期最长或最短？南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 ACD ACD法有直观、形象等优点，但也有明显的缺点：法有直观、形象等优点，但也有明显的缺点：当系统结构复杂、实体数量多时，活动循环图将当系统结构复杂、实体数量多时，活动循环图将十分复杂，给建模与分析等带来困难。十分复杂，给建模与分析等带来困难。ACDACD法只能描述系统的稳态特征，而不研究系统的法只能描述系统的稳态特征，而不研究系统的瞬态（如动作的开始、结束等）。瞬态（如动作的开始、结束等）。ACDACD法法缺乏定量缺乏定量的分析工具。的分析工具。上述缺点限制了上述缺点限制了ACDACD法的推广。法的推广。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 4.34.3马尔可夫过程马尔可夫过程 马尔可夫过程（马尔可夫过程（Markov processMarkov process）是研究离散事件）是研究离散事件动态系统状态空间的重要方法，它的数学基础是随机动态系统状态空间的重要方法，它的数学基础是随机过程理论。如果一个随机过程的概率分布函数具有如过程理论。如果一个随机过程的概率分布函数具有如下特性下特性:南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 马尔可夫特性：马尔可夫特性：当给定当给定t t时刻随机过程的状态为时刻随机过程的状态为X Xn n，则该过程的后续状态及其出现的概率与，则该过程的后续状态及其出现的概率与t t之之前的历史前的历史无关无关。即，过程当前的状态包括了过。即，过程当前的状态包括了过程所有的历史信息，而与当前状态之前的历史程所有的历史信息，而与当前状态之前的历史无关，这种性质也称作无关，这种性质也称作无后效性无后效性或或无记忆性无记忆性（memorylessmemoryless）。）。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 对于连续型随机变量对于连续型随机变量X X，满足无记忆特性的概，满足无记忆特性的概率分布函数为：率分布函数为：南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 离散状态空间的马尔可夫过程也称为马尔可离散状态空间的马尔可夫过程也称为马尔可夫链（夫链（Markov ChainMarkov Chain，MCMC）。对于离散时间马）。对于离散时间马尔可夫链（尔可夫链（DTMCDTMC），驻留时间必定是满足），驻留时间必定是满足几何几何分布分布的随机变量。以的随机变量。以s s表示随机过程在一个状态表示随机过程在一个状态i i的驻留时间，则有：的驻留时间，则有：南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 状态驻留时间状态驻留时间是检验随机过程是否是检验随机过程是否属于马尔属于马尔可夫过程可夫过程的重要标志。的重要标志。可采用以下几种方法：可采用以下几种方法：检查一个随机过程检查一个随机过程是否满足马尔可夫特性。是否满足马尔可夫特性。状态驻留时间分布是否是无记忆的。状态驻留时间分布是否是无记忆的。过程过程从一个状态到另一个状态的概率是否仅依赖于从一个状态到另一个状态的概率是否仅依赖于要离开的状态和目的状态。要离开的状态和目的状态。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 马尔可夫模型常使用马尔可夫模型常使用状态转移图状态转移图来描述系统的运行来描述系统的运行情况。情况。图图4-74-7为一个可修复系统的状态转移图，系统存在为一个可修复系统的状态转移图，系统存在“正常（正常（S)S)”和和“故障（故障（F)F)”两种状态。两种状态。p p、q q就是状态转移的概率就是状态转移的概率 南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 也可采用也可采用状态转移率矩阵状态转移率矩阵来描述来描述南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 系统经过多次转移后，通常会达到一个与系统经过多次转移后，通常会达到一个与时间无关时间无关的的稳定状态稳定状态。即即各状态逗留的概率各状态逗留的概率不再发生变化。不再发生变化。求解系统处于各种状态的求解系统处于各种状态的稳态概率稳态概率是研究是研究离散事件系统特性的重要手段。系统各状态离散事件系统特性的重要手段。系统各状态稳定概率通稳定概率通常有以下两种解法：常有以下两种解法：南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 （1)1)已知瞬态概率，求极限：已知瞬态概率，求极限：S Si i(t)(t)为系统为系统i i状态的瞬态概率状态的瞬态概率A Ai i为为i i状态的稳态概率状态的稳态概率南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 (2)(2)同构法同构法 当系统达到稳定状态以后，各种状态继续当系统达到稳定状态以后，各种状态继续转移，但是每种状态出现的转移，但是每种状态出现的概率基本不变概率基本不变，从而形成一个稳定的从而形成一个稳定的状态空间状态空间。求解状态空。求解状态空间方程组，就可求得系统各种状态的稳态概间方程组，就可求得系统各种状态的稳态概率。率。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 以图以图4-74-7所示的模型为例，由求解下列线性所示的模型为例，由求解下列线性方程组可以求得系统处于正常状态的稳态概方程组可以求得系统处于正常状态的稳态概率率1 1 和处于故障状态的稳态概率和处于故障状态的稳态概率2 2 ：南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 4.4 Petri4.4 Petri网建模理论网建模理论 19621962年，德国人年，德国人Petri Carl AdamPetri Carl Adam首次使首次使用网状结构描述模拟通信系统中条件与事件用网状结构描述模拟通信系统中条件与事件的关系，之后逐步形成的关系，之后逐步形成PetriPetri网理论。网理论。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 PetriPetri网的发展大致经历了三个阶段：网的发展大致经历了三个阶段：1)1)网系统：网系统：6060年代，研究分析技术和应用方法年代，研究分析技术和应用方法;2)2)通用网论通用网论:70:70年代，研究网的分类及各类网年代，研究网的分类及各类网 之间的关系之间的关系;3)3)理论与工程理论与工程:80:80年代，综合发展，新的扩展年代，综合发展，新的扩展 形式不断产生，并开始出现基于形式不断产生，并开始出现基于PetriPetri网的网的 计算机辅助工具。计算机辅助工具。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 PetriPetri网建模具有下列优点：网建模具有下列优点：1)1)具有简捷、直观和准确的图形化建模能力，具有简捷、直观和准确的图形化建模能力，能定性与定量地分析系统中顺序、并发、随机、能定性与定量地分析系统中顺序、并发、随机、因果和冲突等事件关系，描述和表达能力强。因果和冲突等事件关系，描述和表达能力强。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 2)2)具有较严密的数学基础，不仅可以分析系具有较严密的数学基础，不仅可以分析系 统静态结构特征，还能分析系统有界性、统静态结构特征，还能分析系统有界性、活性及可重用性等动态特性。活性及可重用性等动态特性。3)3)可以方便地生成系统的控制、调度及仿真逻可以方便地生成系统的控制、调度及仿真逻 辑代码，得到系统产量、设备利用率等系统辑代码，得到系统产量、设备利用率等系统 性能指标。性能指标。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 4)4)提供了丰富的模型信息。提供了丰富的模型信息。应用领域应用领域：计算机科学、通信协议、数据库系：计算机科学、通信协议、数据库系统、人机系统、统、人机系统、制造系统制造系统、系统维修系统维修等，成为等，成为系统分析与评价、调度控制、仿真与决策等的系统分析与评价、调度控制、仿真与决策等的支持工具。支持工具。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 4.4.1 Petri4.4.1 Petri网的基本概念网的基本概念 一般地，系统模型主要由两类元素构成：一般地，系统模型主要由两类元素构成：表示表示系统状态的元素系统状态的元素和表示系统和表示系统变化的元素变化的元素。与之相对应，与之相对应，PetriPetri网中：网中：库所表示库所表示：资源状态、条件等，如机床、缓冲：资源状态、条件等，如机床、缓冲区、仓库、工人等；区、仓库、工人等；变迁表示变迁表示：事件或资源的消耗、使用等，如切：事件或资源的消耗、使用等，如切削加工、装配、维修、工件安装等操作。削加工、装配、维修、工件安装等操作。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 库所库所和和变迁变迁是是PetriPetri网中最基本概念。网中最基本概念。变迁发生要满足一定条件，受系统状态限制。变迁发生要满足一定条件，受系统状态限制。变迁一旦发生，某些前置条件将不再满足，某些变迁一旦发生，某些前置条件将不再满足，某些后置条件得到满足，系统状态也将随之改变。后置条件得到满足，系统状态也将随之改变。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 库所和变迁之间的库所和变迁之间的有向弧线有向弧线表示状态与事件之表示状态与事件之间的关系：间的关系：令牌令牌：库所中拥有的：库所中拥有的资源数量资源数量，库所中令牌数量的变化表示系统的不同状态。库所中令牌数量的变化表示系统的不同状态。库所中有令牌存在，后续的变迁可以被激发；库所中有令牌存在，后续的变迁可以被激发；否则不能被激发。否则不能被激发。PetriPetri网就是通过网就是通过令牌在库令牌在库所之间的移动所之间的移动来模拟系统的来模拟系统的动态变化过程动态变化过程。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 PetriPetri网的数学定义：网的数学定义：定义定义4-14-1：一个三元组：一个三元组 N=(P,T;F)N=(P,T;F)。其中其中为库所集，为库所集，n n为库所数量为库所数量 为变迁集为变迁集 ，m m为变迁数量为变迁数量 南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 构成一个构成一个PetriPetri网的充分必要条件是：网的充分必要条件是：非空性，至少有一个元素。非空性，至少有一个元素。1 1）2 2）库所和变迁是两类不同元素库所和变迁是两类不同元素 3)F3)F是一个是一个P P元素和一个元素和一个T T元素组成的元素组成的有序偶有序偶 的集合，称为的集合，称为流关系流关系 南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 F F（流关系（流关系)满足满足 它建立了从库所到变迁、从变迁到库所的它建立了从库所到变迁、从变迁到库所的单方向单方向联系，并且规定联系，并且规定同类元素同类元素之间之间不能不能直接直接联系。联系。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 (4)(4)不与任何变迁相连的资源为孤立的库所，不与任何变迁相连的资源为孤立的库所，不引起资源流动的变迁为孤立的变迁。不引起资源流动的变迁为孤立的变迁。令令domdom（F F）和）和codcod（F F）分别为）分别为F F中有序偶的中有序偶的第一个元素和第二个元素组成的集合，分别构第一个元素和第二个元素组成的集合，分别构成了成了F F的定义域和值域，它们满足的定义域和值域，它们满足 dom(F)cod(F)=PT dom(F)cod(F)=PT 该条件规定了网中该条件规定了网中不能有孤立的元素不能有孤立的元素。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 Petri Petri网的形式化定义了系统的静态结构和网的形式化定义了系统的静态结构和组成，所描述的信息较少。是组成，所描述的信息较少。是PetriPetri网理论的网理论的基础。不形象、不直观，也不易于理解。基础。不形象、不直观，也不易于理解。图形化是图形化是PetriPetri网的另一种表示方法。网的另一种表示方法。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 以圆圈（以圆圈（）表示）表示库所库所以实线（以实线（）或方框（）或方框（）表示）表示变迁变迁以带箭头的弧线（以带箭头的弧线（）表示库所与变迁）表示库所与变迁 之间的变迁之间的变迁以黑点表示库所中拥有以黑点表示库所中拥有资源的数量资源的数量。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 图图4-84-8为为PetriPetri网图形化表示的最基本形式。网图形化表示的最基本形式。图图a a表示从库所表示从库所P P到变迁到变迁t t，即，即图图b b表示从变迁表示从变迁t t到库所到库所P P，即，即 南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 变迁变迁需要满足一定的需要满足一定的条件条件才能才能发生发生。一般地，一般地，输入库所输入库所中至少都有一个资源可用中至少都有一个资源可用（即有一个令牌），变迁才可能被激发，即变迁（即有一个令牌），变迁才可能被激发，即变迁所代表的事件可以发生。所代表的事件可以发生。一旦变迁被激发，每个输入库所中都会减少一一旦变迁被激发，每个输入库所中都会减少一个令牌，而输出库所中都会增加一个令牌，从而个令牌，而输出库所中都会增加一个令牌，从而改变了系统中改变了系统中令牌令牌的的分布分布。系统状态发生变化系统状态发生变化。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 也存在以下情况：输入库所中的资源数量大于也存在以下情况：输入库所中的资源数量大于1 1，变迁才激发。，变迁才激发。如，某装配操作需要用如，某装配操作需要用1 1个半成品和个半成品和4 4个螺钉。个螺钉。“半成品半成品”库所中至少要有库所中至少要有1 1个半成品；个半成品；“螺钉螺钉”库所中至少要有库所中至少要有4 4个螺钉；个螺钉；“装配装配”变迁激发后，变迁激发后，“半成品半成品”库所的资源库所的资源数量将减少数量将减少1 1个，个，“螺钉螺钉”库所中的资源数将减库所中的资源数将减少少4 4个。个。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 一个变迁的激发也可能在一个变迁的激发也可能在输出库所输出库所中产生中产生大于大于1 1的令牌数。的令牌数。例如，上述例如，上述“装配装配”变迁的逆变迁变迁的逆变迁“拆卸拆卸”。“拆卸拆卸”变迁激发后，输出库所中分别会多变迁激发后，输出库所中分别会多产生产生1 1个和个和4 4个令牌数。个令牌数。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 PetriPetri网中以网中以权函数权函数表示每个变迁发生时引表示每个变迁发生时引起的相关关资源数量上的变化，也称权重。起的相关关资源数量上的变化，也称权重。通常，通常，w(p,t)w(p,t)：库所：库所P P指向变迁指向变迁t t w(t,p)w(t,p)变迁变迁t t指向库所指向库所P P，标注在有向弧线旁。标注在有向弧线旁。缺省时，表示权重为缺省时，表示权重为1 1。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 一般地，权函数满足以下条件：一般地，权函数满足以下条件：另外，另外，PetriPetri网尊重网尊重资源有限资源有限的事实，主要的事实，主要表现在：变迁发生所需的表现在：变迁发生所需的资源数资源数以及库所的以及库所的容量容量是有限的。是有限的。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 以集合以集合K K表示表示库所库所的的容量容量，称为，称为容量函数容量函数。当一个库所为有限容量时，以当一个库所为有限容量时，以K(p)K(p)标注在标注在库所库所P P的旁边。的旁边。当库所容量不会对系统的行为构成限制时，当库所容量不会对系统的行为构成限制时，也允许某些库所的容量也允许某些库所的容量为无穷为无穷。另外，当另外，当K(p)=1K(p)=1时，可不标注。时，可不标注。南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 7 7个库所和个库所和2 2个变迁。个变迁。P P1 1、P P2 2、P P3 3表示半成品表示半成品P P4 4、P P6 6表示零件表示零件P P5 5表示螺钉表示螺钉P P0 0表示旋具表示旋具t t1 1、t t2 2表示两个装配操作。表示两个装配操作。图图4-94-9某装配线的某装配线的PetriPetri网模型网模型 南昌大学南昌大学第四章第四章 制造系统建模方法制造系统建模方法 该装配线的功能如下：该装配线的功能如下：变迁变迁t t1 1用两个螺钉用两个螺钉P P5 5将半成品将半成品P