1、工业工程系工业工程系 苏平苏平1离散事件系统的建模方法离散事件系统的建模方法 工业工程系工业工程系 苏平苏平21 系统建模方法概述系统建模方法概述离散事件系统模型离散事件系统模型n模型是对实际系统本质的抽象与简化，能描述系模型是对实际系统本质的抽象与简化，能描述系统结构或行为过程。统结构或行为过程。工业工程系工业工程系 苏平苏平31 系统建模方法概述系统建模方法概述离散事件系统建模方法离散事件系统建模方法n实体流图法实体流图法l用流程图的方法描述事件、状态变化及实体间相互作用流程图的方法描述事件、状态变化及实体间相互作用的逻辑关系。用的逻辑关系。n活动周期图法活动周期图法l以图形直观地显示系统
2、状态及其变化。以图形直观地显示系统状态及其变化。nPetri网法网法l是一种系统的数学和图形描述与分析工具。是一种系统的数学和图形描述与分析工具。工业工程系工业工程系 苏平苏平42 实体流图法实体流图法实体流图实体流图(Entity Flow Chart, EFC)法的建模思路法的建模思路l辨识系统的实体及属性；辨识系统的实体及属性；l分析实体的状态和运动，队列的状态；分析实体的状态和运动，队列的状态；l确定系统事件，合并条件事件；确定系统事件，合并条件事件；l分析事件发生时，实体状态的变化；分析事件发生时，实体状态的变化；l在一定的服务流程下，分析与队列有关的特殊操作；在一定的服务流程下，分
3、析与队列有关的特殊操作；l以临时实体的活动为主线，画出系统的实体流图；以临时实体的活动为主线，画出系统的实体流图；l给出模型参数的取值；给出模型参数的取值；l给出排队规则、服务规则、优先级、换队规则。给出排队规则、服务规则、优先级、换队规则。工业工程系工业工程系 苏平苏平52 实体流图法实体流图法实例：实例：理发店服务系统理发店服务系统单队列单队列-单服务台系统单服务台系统n 系统分析：系统分析： 实体实体n 临时实体：顾客临时实体：顾客n 永久实体：服务员永久实体：服务员n 特殊实体：队列特殊实体：队列 状态状态n 服务员：忙、闲服务员：忙、闲n 顾客：等待服务、接受服务顾客：等待服务、接受
4、服务n 队列：队长队列：队长工业工程系工业工程系 苏平苏平62 实体流图法实体流图法实例：理发店服务系统实例：理发店服务系统单队列单队列-单服务台系统单服务台系统n 系统分析：系统分析： 活动活动n 排队、服务排队、服务 事件事件n 顾客到达顾客到达n 顾客结束排队（开始接受服务）顾客结束排队（开始接受服务）n 顾客服务完毕离开顾客服务完毕离开 排队规则排队规则n FIFO工业工程系工业工程系 苏平苏平72 实体流图法实体流图法实例：理发店服务系统实例：理发店服务系统单队列单队列-单服务台系统单服务台系统n 模型属性变量：模型属性变量：n 顾客到达时间（随机变量）顾客到达时间（随机变量）n 理
5、发员为一名顾客理发所需要的时间（随机变量）理发员为一名顾客理发所需要的时间（随机变量）工业工程系工业工程系 苏平苏平83 活动循环图法活动循环图法活动循环图活动循环图(Activity Cycle Diagram)法的基本原理法的基本原理n活动循环图（活动循环图（ACD）法以图形直观地显示系统状态及其）法以图形直观地显示系统状态及其变化。变化。nACD法认为，系统中的每个实体都按照各自的方式循环法认为，系统中的每个实体都按照各自的方式循环地发生变化，存在静止（以表示）和活动（以表示）地发生变化，存在静止（以表示）和活动（以表示）两种状态，这两种状态在实体的循环中交替出现（以两种状态，这两种状态
6、在实体的循环中交替出现（以表示两种状态之间的转换）。表示两种状态之间的转换）。nACD法认为，系统的状态就是全部个体状态变化的集合。法认为，系统的状态就是全部个体状态变化的集合。当研究对象比较复杂、包含的实体数目较多时，可以对当研究对象比较复杂、包含的实体数目较多时，可以对系统建立不同层次的系统建立不同层次的ACD模型，将高层次模型进一步分模型，将高层次模型进一步分解为低层次的模型。解为低层次的模型。工业工程系工业工程系 苏平苏平93 活动循环图法活动循环图法ACD法的建模方法与建模过程法的建模方法与建模过程n常用术语常用术语n实体。是指组成系统的各种要素，是实体。是指组成系统的各种要素，是A
7、CD产生活动的主体。产生活动的主体。n活动。表示实体正处于某种动作状态。活动的持续时间也称为周活动。表示实体正处于某种动作状态。活动的持续时间也称为周期。期。n队列。用来表示实体处于静止或等待状态。队列。用来表示实体处于静止或等待状态。n实体的行为模式。实体的行为始终遵循实体的行为模式。实体的行为始终遵循“活动活动队列队列活动活动”的交替变化规则。的交替变化规则。n直联活动和虚拟队列。如果在任何情况下，某一活动完成后，其直联活动和虚拟队列。如果在任何情况下，某一活动完成后，其后续活动就立即开始，则称后续活动为直联活动。直联活动与前后续活动就立即开始，则称后续活动为直联活动。直联活动与前面活动之
8、间为一个等待时间为面活动之间为一个等待时间为0的队列，即虚拟队列。的队列，即虚拟队列。n合作活动。指一个活动要求有多于一个的实体参加才能开始。合作活动。指一个活动要求有多于一个的实体参加才能开始。工业工程系工业工程系 苏平苏平103 活动循环图法活动循环图法ACD法的建模方法与建模过程法的建模方法与建模过程n举例举例：某加工系统有两个实体：一台半自动机床和一名：某加工系统有两个实体：一台半自动机床和一名操作工。工人负责安装工件和从机床上取下工件。工件操作工。工人负责安装工件和从机床上取下工件。工件安装完毕后，机床就可以自动地完成工件的加工。加工安装完毕后，机床就可以自动地完成工件的加工。加工完
9、毕，机床停止，直到工人安装一个新的工件，再开始完毕，机床停止，直到工人安装一个新的工件，再开始下一个加工循环。下一个加工循环。工业工程系工业工程系 苏平苏平113 活动循环图法活动循环图法ACD法的建模方法与建模过程法的建模方法与建模过程工业工程系工业工程系 苏平苏平123 活动循环图法活动循环图法ACD法的建模方法与建模过程法的建模方法与建模过程工业工程系工业工程系 苏平苏平133 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机床加工顺序为假设三台机床加工顺序为工业工程系工业工程系 苏平苏平143 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机
10、床加工顺序为假设三台机床加工顺序为工业工程系工业工程系 苏平苏平153 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机床加工顺序为假设三台机床加工顺序为工业工程系工业工程系 苏平苏平163 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机床加工顺序为假设三台机床加工顺序为工业工程系工业工程系 苏平苏平173 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机床加工顺序为假设三台机床加工顺序为工业工程系工业工程系 苏平苏平183 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机床加工顺序为假设三台机床加工顺序
11、为工业工程系工业工程系 苏平苏平193 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机床加工顺序为假设三台机床加工顺序为工业工程系工业工程系 苏平苏平203 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机床加工顺序为假设三台机床加工顺序为工业工程系工业工程系 苏平苏平213 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机床加工顺序为假设三台机床加工顺序为工业工程系工业工程系 苏平苏平223 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机床加工顺序为假设三台机床加工顺序为工业工程系工业工程系 苏平苏平
12、233 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机床加工顺序为假设三台机床加工顺序为工业工程系工业工程系 苏平苏平243 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机床加工顺序为假设三台机床加工顺序为工业工程系工业工程系 苏平苏平253 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机床加工顺序为假设三台机床加工顺序为工业工程系工业工程系 苏平苏平263 活动循环图法活动循环图法ACD模型的仿真运行模型的仿真运行n假设三台机床加工顺序为假设三台机床加工顺序为工业工程系工业工程系 苏平苏平274 Petri网建模网建模1
13、962年（联邦）德国年（联邦）德国 Carl Adam Petri 博士在博士在他的博士论文他的博士论文“Communication with automate”中首次提出了一种网状结构的信息中首次提出了一种网状结构的信息流模型，后来被称为流模型，后来被称为 Petri 网网。已成为控制理。已成为控制理论领域处理离散事件系统的有力工具。论领域处理离散事件系统的有力工具。工业工程系工业工程系 苏平苏平284 Petri网建模网建模Petri网主要优点：网主要优点：采用网络图的形式模拟离采用网络图的形式模拟离散事件系统，形式简洁、直观，特别适合于散事件系统，形式简洁、直观，特别适合于描述系统组织、
14、结构和状态的变化；可以在描述系统组织、结构和状态的变化；可以在不同概念级别上表明系统的结构和性质；能不同概念级别上表明系统的结构和性质；能有效模拟异步并发系统，直接分析模型实体有效模拟异步并发系统，直接分析模型实体中是否具有诸如死锁，状态空间无限等异常中是否具有诸如死锁，状态空间无限等异常特征。特征。工业工程系工业工程系 苏平苏平294 Petri网建模网建模Petri网基本概念网基本概念例：例：用螺钉将用螺钉将3个零件个零件1，1个零件个零件2和和2个零件个零件3连接在连接在一起，得到零件一起，得到零件4。23p1p2p3p4t1k = 500容量容量 K = , , 500 , 标识标识
15、M = 5 , 3 , 4 , 0工业工程系工业工程系 苏平苏平304 Petri网建模网建模Petri网基本概念网基本概念n Petri 网图是一个五元组：网图是一个五元组：PN = ( P, T, I, O, M )n P是库所是库所(place)节点的集合；节点的集合；n T是变迁是变迁(Transition)节点的集合；节点的集合；n I 是输入函数是输入函数P T的有向弧线的集合；的有向弧线的集合；n O 是输出函数是输出函数 TP 的有向弧线的集合；的有向弧线的集合；n M是标识，为一函数向量，是标识，为一函数向量，M(pi)表示库所表示库所pi中所中所含令牌个数。含令牌个数。工业
16、工程系工业工程系 苏平苏平314 Petri网建模网建模Petri网基本概念网基本概念123451, Pp ppppTt( )| ( ,)0( )|( ,)0jjjjIP tpP I p tOP tpP O p t23p1p2p3p4p5t12工业工程系工业工程系 苏平苏平324 Petri网建模网建模Petri网基本概念网基本概念23p1p2p3p4p5t12令牌令牌TTnpmpmpmM00431 )(),.,(),(210标识标识1141215131(, )1(, )1(, )2(, )2(, )3I p tO p tI p tO p tI p t工业工程系工业工程系 苏平苏平334 Pe
17、tri网建模网建模Petri网基本概念网基本概念23p1p2p3p4p5t12TTnpmpmpmM00431 )(),.,(),(210标识标识TnpkpkpkK)(),.,(),(21容量函数容量函数工业工程系工业工程系 苏平苏平344 Petri网建模网建模Petri网基本概念网基本概念n 库所库所(place)可以用来表示可以用来表示条件条件、资源资源和和缓冲站缓冲站。n 变迁变迁(Transition)可以用来表示可以用来表示事件事件、任务任务和和作作业业。工业工程系工业工程系 苏平苏平354 Petri网建模网建模Petri网的变迁规则网的变迁规则变迁的发生表示系统状态的变化，可用变
18、迁的发变迁的发生表示系统状态的变化，可用变迁的发射（事件的发生）规则来定义。射（事件的发生）规则来定义。变迁条件和发射规则：变迁条件和发射规则：对于对于 t T 如果如果成立，则变迁是可能的成立，则变迁是可能的( ),()(,)( ),()( )(,)( )( ),(,)()()(,)(,)jiijjiijjjijiiijijpIP tM pI p tpOP tM pK pO p tpIP tpOP tI p tM pK pI p tO p t工业工程系工业工程系 苏平苏平364 Petri网建模网建模Petri网的变迁规则网的变迁规则变迁后的结果是变迁后的结果是()(,),( )()()(,
19、),( )()(,)(,),( )( )iijijiiijijiijijijijM pI p tpIP tMpM pO p tpOP tM pO p tI p tpIP tpOP t工业工程系工业工程系 苏平苏平374 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(p3)=2 , M(p6)=1例例1：检查变迁发生权，检查变迁发
20、生权，顺序：顺序：t1 t2 t3 t4p1p2p4t1t3p6p3p5t2t4工业工程系工业工程系 苏平苏平384 Petri网建模网建模Petri网的变迁规则网的变迁规则例例1：检查变迁发生权，检查变迁发生权，顺序：顺序：t1 t2 t3 t4检查检查t2 ：t2 没有发生权没有发生权p2p4p1t1t3p6p3p5t2t4工业工程系工业工程系 苏平苏平394 Petri网建模网建模Petri网的变迁规则网的变迁规则例例1：检查变迁发生权，检查变迁发生权，顺序：顺序：t1 t2 t3 t4检查检查t3 ：t3 有发生权有发生权点燃后，点燃后，M(p2)=0， M(p3)=0 ， M(p5)
21、=0 ， M(p4)=1p2p4p1t1t3p6p3p5t2t4工业工程系工业工程系 苏平苏平404 Petri网建模网建模Petri网的变迁规则网的变迁规则例例1：检查变迁发生权，检查变迁发生权，顺序：顺序：t1 t2 t3 t4检查检查t4 ：t4 有发生权有发生权点燃后点燃后 M(p4)=0 M(p3)=1p2p4p1t1t3p6p3p5t2t4工业工程系工业工程系 苏平苏平414 Petri网建模网建模逻辑关系逻辑关系事件事件 t1 和和 t2 为先后为先后关系关系事件事件 t2 和和 t3 为并发为并发关系关系p4p5t2t3p2p3p1t1p2p3p1t1t2p2p3p1t1t2工
22、业工程系工业工程系 苏平苏平424 Petri网建模网建模逻辑关系逻辑关系事件事件 t1 和和 t2 为冲突关系为冲突关系p2p3p1t1t2p1p2p3t1t2事件事件 t1 和和 t2 为冲撞关系为冲撞关系工业工程系工业工程系 苏平苏平434 Petri网建模网建模逻辑关系逻辑关系p4p3p1t1t3p5p2t2p5p4p1t1t3p2p3t2事件事件 t1 ， t2 ， t3为迷惑关系，取决于它们的发生次序。为迷惑关系，取决于它们的发生次序。工业工程系工业工程系 苏平苏平444 Petri网建模网建模逻辑关系逻辑关系事件事件 t1 和和 t2 为死锁关系，事件不可能发生。为死锁关系，事件
23、不可能发生。p3p4p1t1t2p5p2p6t3t4工业工程系工业工程系 苏平苏平454 Petri网建模网建模Petri 网建模举例网建模举例例例2：机械加工系统机械加工系统变迁变迁 t1 和和 t2 共享一件工具，两个变迁不能同时启动，但每共享一件工具，两个变迁不能同时启动，但每个变迁可以多次启动。个变迁可以多次启动。p1t1t0p0t2p2t3p3工件工件到达到达工件等工件等待加工待加工开始开始加工加工正在加工正在加工加工加工完毕完毕加工好加工好的工件的工件运走运走工件工件加工工具闲加工工具闲工业工程系工业工程系 苏平苏平464 Petri网建模网建模Petri 网建模举例网建模举例例例
24、3：流水生产车间制造系统，由两台机床流水生产车间制造系统，由两台机床M1和和M2加工两种零加工两种零件件P1和和P2。所有零件按相同的顺序通过两台机床，每台机床。所有零件按相同的顺序通过两台机床，每台机床的入口处有一个零件库，在系统的出口处也有一个零件库，的入口处有一个零件库，在系统的出口处也有一个零件库，系统作业进度计划要求两种零件交替加工。系统作业进度计划要求两种零件交替加工。工业工程系工业工程系 苏平苏平474 Petri网建模网建模Petri 网建模举例网建模举例例例3：流水生产车间制造系统，由两台机床流水生产车间制造系统，由两台机床M1和和M2加工两种零加工两种零件件P1和和P2。所
25、有零件按相同的顺序通过两台机床，每台机床。所有零件按相同的顺序通过两台机床，每台机床的入口处有一个零件库，在系统的出口处也有一个零件库，的入口处有一个零件库，在系统的出口处也有一个零件库，系统作业进度计划要求两种零件交替加工。系统作业进度计划要求两种零件交替加工。工业工程系工业工程系 苏平苏平人有了知识，就会具备各种分析能力，人有了知识，就会具备各种分析能力，明辨是非的能力。明辨是非的能力。所以我们要勤恳读书，广泛阅读，所以我们要勤恳读书，广泛阅读，古人说古人说“书中自有黄金屋。书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，给我们巨大的精神力量，鼓舞我们前进鼓舞我们前进。
