离散事件系统的建模方法.ppt

1,离散事件系统的建模方法,2,1 系统建模方法概述,离散事件系统模型 模型是对实际系统本质的抽象与简化，能描述系统结构或行为过程。,3,1 系统建模方法概述,离散事件系统建模方法 实体流图法 用流程图的方法描述事件、状态变化及实体间相互作用的逻辑关系。 活动周期图法 以图形直观地显示系统状态及其变化。 Petri网法 是一种系统的数学和图形描述与分析工具。,4,2 实体流图法,实体流图(Entity Flow Chart, EFC)法的建模思路 辨识系统的实体及属性； 分析实体的状态和运动，队列的状态； 确定系统事件，合并条件事件； 分析事件发生时，实体状态的变化； 在一定的服务流程下，分析与队列有关的特殊操作； 以临时实体的活动为主线，画出系统的实体流图； 给出模型参数的取值； 给出排队规则、服务规则、优先级、换队规则。,5,2 实体流图法,实例：理发店服务系统单队列-单服务台系统 系统分析： 实体 临时实体：顾客 永久实体：服务员 特殊实体：队列 状态 服务员：忙、闲 顾客：等待服务、接受服务 队列：队长,6,2 实体流图法,实例：理发店服务系统单队列-单服务台系统 系统分析： 活动 排队、服务 事件 顾客到达 顾客结束排队（开始接受服务） 顾客服务完毕离开 排队规则 FIFO,7,2 实体流图法,实例：理发店服务系统单队列-单服务台系统 模型属性变量： 顾客到达时间（随机变量） 理发员为一名顾客理发所需要的时间（随机变量）,8,3 活动循环图法,活动循环图(Activity Cycle Diagram)法的基本原理 活动循环图（ACD）法以图形直观地显示系统状态及其变化。 ACD法认为，系统中的每个实体都按照各自的方式循环地发生变化，存在静止（以表示）和活动（以表示）两种状态，这两种状态在实体的循环中交替出现（以表示两种状态之间的转换）。 ACD法认为，系统的状态就是全部个体状态变化的集合。当研究对象比较复杂、包含的实体数目较多时，可以对系统建立不同层次的ACD模型，将高层次模型进一步分解为低层次的模型。,9,3 活动循环图法,ACD法的建模方法与建模过程 常用术语 实体。是指组成系统的各种要素，是ACD产生活动的主体。 活动。表示实体正处于某种动作状态。活动的持续时间也称为周期。 队列。用来表示实体处于静止或等待状态。 实体的行为模式。实体的行为始终遵循“活动队列活动”的交替变化规则。 直联活动和虚拟队列。如果在任何情况下，某一活动完成后，其后续活动就立即开始，则称后续活动为直联活动。直联活动与前面活动之间为一个等待时间为0的队列，即虚拟队列。 合作活动。指一个活动要求有多于一个的实体参加才能开始。,10,3 活动循环图法,ACD法的建模方法与建模过程 举例：某加工系统有两个实体：一台半自动机床和一名操作工。工人负责安装工件和从机床上取下工件。工件安装完毕后，机床就可以自动地完成工件的加工。加工完毕，机床停止，直到工人安装一个新的工件，再开始下一个加工循环。,11,3 活动循环图法,ACD法的建模方法与建模过程,12,3 活动循环图法,ACD法的建模方法与建模过程,13,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,14,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,15,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,16,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,17,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,18,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,19,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,20,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,21,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,22,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,23,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,24,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,25,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,26,3 活动循环图法,ACD模型的仿真运行 假设三台机床加工顺序为,27,4 Petri网建模,1962年（联邦）德国 Carl Adam Petri 博士在他的博士论文“Communication with automate”中首次提出了一种网状结构的信息流模型，后来被称为 Petri 网。已成为控制理论领域处理离散事件系统的有力工具。,28,4 Petri网建模,Petri网主要优点：采用网络图的形式模拟离散事件系统，形式简洁、直观，特别适合于描述系统组织、结构和状态的变化；可以在不同概念级别上表明系统的结构和性质；能有效模拟异步并发系统，直接分析模型实体中是否具有诸如死锁，状态空间无限等异常特征。,29,4 Petri网建模,Petri网基本概念 例：用螺钉将3个零件1，1个零件2和2个零件3连接在一起，得到零件4。,容量 K = , , 500 , ,标识 M = 5 , 3 , 4 , 0,30,4 Petri网建模,Petri网基本概念 Petri 网图是一个五元组：PN = ( P, T, I, O, M ) P是库所(place)节点的集合； T是变迁(Transition)节点的集合； I 是输入函数 P T的有向弧线的集合； O 是输出函数 TP 的有向弧线的集合； M是标识，为一函数向量，M(pi)表示库所pi中所含令牌个数。,31,4 Petri网建模,Petri网基本概念,32,4 Petri网建模,Petri网基本概念,令牌,标识,33,4 Petri网建模,Petri网基本概念,标识,容量函数,34,4 Petri网建模,Petri网基本概念 库所(place)可以用来表示条件、资源和缓冲站。 变迁(Transition)可以用来表示事件、任务和作业。,35,4 Petri网建模,Petri网的变迁规则 变迁的发生表示系统状态的变化，可用变迁的发射（事件的发生）规则来定义。 变迁条件和发射规则： 对于 t T 如果 成立，则变迁是可能的,36,4 Petri网建模,Petri网的变迁规则 变迁后的结果是,37,4 Petri网建模,Petri网的变迁规则,检查t1 ：,O(p1 , t1)=1,变迁t1 可以被点燃，M(p2)=1 ， M(p3)=1 ， M(p6)=0 ， M(p1)=1,I(p2 , t1)=1 , I(p3 , t1)=1 , I(p6 , t1)=1,M(p2)=2 , M(p3)=2 , M(p6)=1,例1：检查变迁发生权，顺序：t1 t2 t3 t4,38,4 Petri网建模,Petri网的变迁规则,例1：检查变迁发生权，顺序：t1 t2 t3 t4,检查t2 ：,t2 没有发生权,39,4 Petri网建模,Petri网的变迁规则,例1：检查变迁发生权，顺序：t1 t2 t3 t4,检查t3 ：,t3 有发生权,点燃后，M(p2)=0， M(p3)=0 ， M(p5)=0 ， M(p4)=1,40,4 Petri网建模,Petri网的变迁规则,例1：检查变迁发生权，顺序：t1 t2 t3 t4,检查t4 ：,t4 有发生权,点燃后 M(p4)=0 M(p3)=1,41,4 Petri网建模,逻辑关系,事件 t1 和 t2 为先后关系,事件 t2 和 t3 为并发关系,42,4 Petri网建模,逻辑关系,事件 t1 和 t2 为冲突关系,事件 t1 和 t2 为冲撞关系,43,4 Petri网建模,逻辑关系,事件 t1 ， t2 ， t3为迷惑关系，取决于它们的发生次序。,44,4 Petri网建模,逻辑关系,事件 t1 和 t2 为死锁关系，事件不可能发生。,45,4 Petri网建模,Petri 网建模举例 例2：机械加工系统,变迁 t1 和 t2 共享一件工具，两个变迁不能同时启动，但每个变迁可以多次启动。,46,4 Petri网建模,Petri 网建模举例 例3：流水生产车间制造系统，由两台机床M1和M2加工两种零件P1和P2。所有零件按相同的顺序通过两台