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