离散事件系统的建模方法课件

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