《3离散事件系统数学模型》由会员分享，可在线阅读，更多相关《3离散事件系统数学模型（31页珍藏版）》请在金锄头文库上搜索。
1、离散事件系统数学模型l建模过程l离散事件系统概述l离散事件系统模型l离散事件仿真模型建模l根据研究目的 、系统的先验 知识以及实验 观测数据，分 析系统，确定 各组成要素以 及表征这些要 素的状态变量 和参数之间的 数学逻辑关系 ，建立被研究 系统的数学逻 辑模型 建模 目的先验知识数据模型构造最终模 型目标 协调演绎 分析归纳 程序可信度分析（有效性 ）离散事件系统概述l离散事件模型，离散事件系统状态变化只在某些离散点或量化区间上发生最能反映系统本质属性的对象离散系统仿真是动态仿真，需不断记录各类离散事 件发生的时刻和状态的变化l研究目的了解系统的控制因素，以及它们对系统稳定性和发 展进程等
2、方面的影响随机离散事件一系列按时序随机 发生的事实，只在 离散、有限的时刻 上发生，使系统中 一个或若干状态变 量的取值发生瞬时 跃变离散事件系统基本要素l系统边界内部的客观对象，构成系统的可单独 辨识和描述的功能单元永久实体 vs. 临时实体l反映实体的特性、性质l在某时间点对系统所有实体和属性的描述需根据系统的内部结构及仿真研究的目的来确定l引起系统状态发生瞬时变化的事实如：实体的产生或消失，实体属性值的变化，活动的 开始或结束时间事件：使系统作业规则在预定时间发生的事件状态/条件事件：当系统状态符合某种条件而发生的 事件实体属性状态事件活动进程离散事件系统基本要素l系统边界内部的客观对象
3、l反映实体的特性、性质l在某时间点对系统所有实体和属性的描述l引起系统状态发生瞬时变化的事实l占用一定时间和资源的，导致系统状态发生变 化的过程l一组按发生时间排列的事件/活动序列实体属性状态事件活动进程离散事件系统模型（形式化规范）l引例：杂货店模型非形式描述实体，描述变量，实体相互关系l模型特点多数模型变量为“逐段常数变量”有些变量为“递减时标变量”当递减时标变量减少为0时，模型状态发生变化若无外部输入，在任一时刻，由递减时标变量决定下次事件发生 时间随机变量生成历经两个步骤：产生【0,1】伪随机数，由该随机 数生成所需样本有外部事件发生时，记录事件发生时间，并安排对事件的处理发生同时事件
4、时，根据预设规则将它们转化为串行事件离散事件系统模型（形式化规范）l输入集合、输出集合、状态集合l时间进程函数/时间拨动函数l状态转移函数l输出函数离散事件系统模型（实体流图法）l采用与计算机程序流程图类似的图示符号和原理，表示 临时实体产生、在系统中流动、接受永久实体“服务”以及 消失等过程l步骤：辨识组成系统的实体、属性分析各种实体的状态和活动，及其相互间的影响考察导致活动开始或结束的行为或标志，以确定事件分析在各种事件发生时实体状态的变化规律以临时实体的流动为主线，用约定图示符号画出实体流图确定模型参变量，给出排队规则实体流图是为描述实体在系统中的流动和相互间逻辑关系而绘制的 与计算机程
5、序框图不同，尚不能直接转成计算机程序例：理发店服务系统l背景描述：一个理发员，顾客排队，单一队列， 先来先服务，理发员不休息l目的：考察理发员忙闲情况辨识组成系统的实体、属性分析各种实体的状态和活动，及其相互间的影响考察导致活动开始或结束的行为或标志，以确定事件分析在各种事件发生时实体状态的变化规律以临时实体的流动为主线，用约定图示符号画出实体流图确定模型参变量，给出排队规则l系统实体流程图：图3.2，p99例：分时计算机系统l背景描述：一个CPU，多个作业输入终端，作业分时接 受服务，单一队列，先进先出，作业完成后才能接受新 作业输入l目的：考察用户的等待时间辨识组成系统的实体、属性分析各种
6、实体的状态和活动，及其相互间的影响考察导致活动开始或结束的行为或标志，以确定事件分析在各种事件发生时实体状态的变化规律以临时实体的流动为主线，用约定图示符号画出实体流图确定模型参变量，给出排队规则l系统实体流程图：图3.4，p102例：售票窗口服务系统l背景描述：一名售票员，同时处理窗口销售和电话咨询 ，先来先服务，电话咨询优先，但不能中断窗口服务l目的：考察售票员的忙闲情况辨识组成系统的实体、属性分析各种实体的状态和活动，及其相互间的影响考察导致活动开始或结束的行为或标志，以确定事件分析在各种事件发生时实体状态的变化规律以临时实体的流动为主线，用约定图示符号画出实体流图确定模型参变量，给出排
7、队规则l系统实体流程图：图3.5，p103离散事件仿真模型l要将系统模型转换为计算机模型，必须要从总 体上确定仿真模型的控制逻辑和仿真时钟推进 机制l仿真策略是仿真模型的核心，反映了仿真模型 的本质，从根本上决定了仿真模型的结构l仿真时钟推进：周期扫描法事件扫描法/下次事件法/变步长法事件 调度活动 扫描进程 交互基于事件调度的离散事件模型lEvent Schedulingl主要关注事件点（事件发生的时刻）和依次引 起的状态变化将“事件例程”作为仿真程序的基本模型单元，按事件 发生的先后顺序不断执行相应的事件例程l强调所有事件的预先安排，由主动型实体的变 量以及时标来安排下次事件，因此，带有递
8、减 时标变量的实体是仿真模型的核心主动型实体：其某个属性是递减时标变量被动型实体：其属性一般是逐段常数变量基于事件调度的离散事件模型仿真步骤：1.初始化2.对每个主动型实体，将对偶（实体事件，事件发生时 间）置于未来事件列表FEL，其元素按时间先后次序排 列3.设仿真时钟为表中第一个对偶的时间，从中调出并选 择将在该时刻发生事件的实体（针对同时事件）4.从FEL中移出该实体对偶，执行其事件例程，若有未 来事件产生，则生成新对偶并插入FEL中相应位置5.若超过仿真终止时间，则停机，否则转3基于活动扫描的离散事件模型lActivity Scanningl主要关注实体的活动和活动的激活条件系统由实体
9、组成，实体包含活动，活动的发生必须满足某些条 件，每个主动型实体均有一个相应的活动子例程按各个主动型实体的递减时标变量值来推进仿真时钟对整个活动集合进行扫描，判断每项活动的开始或终止条件， 按优先次序执行可激活的活动例程l适用于活动持续时间不定，并且是由满足一定条件的 系统状态而决定的情况，但效率低，应用不广泛基于活动扫描的离散事件模型l对于每个主动型实体a，建立一个表示转移函数 的子程序fa，以及表示激活条件的子程序Ca， 并设置一个关联的时间单元Ta作为递减时标。l把主动型实体和检验其激活条件的子程序组成 对偶，形成激活条件表，同时实体按固定优先 次序 排列l在仿真过程中，通过扫描指示器S
10、CAN从表列 的头至尾移动进行扫描基于活动扫描的离散事件模型主要步骤：1.初始化2.令各主动型实体的时间单元为各递减时标变量的初 值3.置SCAN到条件列表的头4.SCAN向下移动直至发现第一个可激活的实体（过 去和现在时），运行表示激活条件的子程序Ca，找出 条件为真的实体5.执行表示转移函数的子程序fa6.若SCAN未达到激活条件表列尾，转47.推进仿真时钟至下次事件的时间，若超过终止时间 则停机，否则转3ES vs. ASl时钟推进仅比较事件预计发 生时间的早晚，而该事件发 生的任何条件测试则放在事 件处理子程序中l在每类事件处理子程序中， 除了要修改系统有关状态外 ，还要预定本类事件的
11、下一 事件发生时间l适合于活动持续时间确定性 较强的系统（可以是服从某 种分布的随机变量）l对于持续时间不确定的系统 ，事件发生不仅与时间有关 ，还与其他条件有关，无法 预定活动的开始/终止时间l包括了对事件发生时间的扫 描，具有事件调度法的功能l活动的发生时间也是事件发 生的条件之一，而且较之于 其他条件来说优先权更高基于进程交互的离散事件模型lProcess Interationl一个进程包含若干有序事件及有序活动l将模型中的主动实体所发生的事件及活动按时间顺序进 行组合，从而形成进程表。一个实体一旦进入进程，则 将完成该进程的全部活动l以实体流动为主线，描述作为仿真对象的实体如何流经 具
12、有一定资源的过程当前事件表CEL 包含从当前时间点开始有资格 执行的事件的记录，但该时间 是否发生的条件（如果有的话 ）尚未判断未来事件表FEL 包含在将来某个仿真时刻发生 的事件。每个事件记录包括该 事件的若干属性，其中必有一 个属性说明该事件在进程中所 处位置基于进程交互的离散事件模型l当仿真钟推进时，将所有事件发生时间不大于仿 真钟的事件记录从FEL移到CELl对CEL中每个事件记录进行扫描：首先判断其属于哪个进程，以及在该进程中的位置；然后判断该事件发生的条件，若条件满足，则尽可能 连续执行事件所在的进程若条件不满足，则退出该进程，记下断点，置于FEL 中l推进仿真钟（把FEL中最早发
13、生的事件记录移到 CEL），直到仿真结束仿真策略的比较1、系统描述l相同：所有策略均提供主动实体及被动实体， 每种实体均能接受其他实体的作用lES中，只有主动型实体才能施加作用，系统的 动态特性表现为主动实体不断产生事件lAS中，主动实体产生活动lPI中，通过实体在其进程中一步步推进来描述仿真策略的比较2、建模要点lES中，用户要对所定义的全部事件建模，条件 测试只能在事件处理子程序中进行lAS中，设有一个条件子例程专用于条件测试， 还有一个活动扫描模块，对所有定义的活动进 行建模lPI中，将一个进程分成若干步骤，每一步都包 括条件测试及执行活动两部分仿真策略的比较3、仿真钟的推进lES中，主
14、动实体的下一事件发生时间保存在事件表中，定时 模块不断从事件表中取出具有最早发生时间的事件记录，将 仿真时钟推进至彼时，并转该事件处理子程序lAS中，除设系统仿真时钟外，每个主动实体还有实体仿真钟 ，定时模块选择那些大于当前系统仿真钟的值，且是所有实 体仿真钟中最小的那个实体仿真钟，推进至彼时，并开始对 活动扫描lPI中，采用FEL和CEL。扫描完CEL中进程后，从FEL中取出 具有最早发生时间的记录送入CEL，仿真钟推进至彼时。一旦 某个进程被执行，则要求尽可能多地走下去，但并不改系统 仿真钟。若该进程未完成，则记录断点，将中断事件及事件 类型放入FEL。若CEL中有一项或几项的发生时间小于
15、当前系 统钟的值，则说明在以前的扫描中，发生该事件的条件未得 到满足，应再次进行扫描仿真策略的比较4、执行控制lES中，由定时模块按下一最早发生时间选择事 件记录，并转向该事件处理子程序lAS中，按优先数递减的顺序对全部活动进行扫 描，只有满足条件（包括资源条件和时间条件等 ）的活动才能被执行lPI中，按优先数递减的顺序对CEL中全部记录进 行扫描，根据该事件在进程中的指针进行条件判 断，尽可能推进进程执行，若遇阻塞则记下断点 ，修改指针，将未来时间记入FEL仿真策略的比较5、适用性lES：建模灵活，可应用范围广，但一般要求用户采用 通用的高级语言编写事件处理子程序，建模工作量大lAS：对各实
16、体相关性很强（活动之间条件多）的系统 来说模型执行效率高，但用户建模时，除要对各实体 的活动进行建模外，仿真执行程序结构比较复杂，其 流程控制要十分小心lPI：建模最为直观，其模型表示接近实际系统，特别适 用于活动可以预测、顺序比较确定的系统，但其流程 控制复杂，建模灵活性不如ES仿真模型的组成l建立仿真模型的框架和算法，负责安排 仿真时钟的推进l描述事件与实体状态之间的影响关系及 实体间的相互作用关系ES：事件例程AS：活动例程PI：进程l生成随机变量、产生仿真结果报告 、收集统计数据等总控 程序基本模型 单元的处 理程序公共子 程序仿真研究的一般步骤l可用系统规范进行形式描述，也 可用流程图、网络图等描述l反映临时实体在系统内部历经的 过程，永久实体对临时实体的作 用，以及它们之间的逻辑关系l包括由观测数据确定随机变量分 布和参数的数据预处理过程系统建模确定仿真算法建立仿真模型设计仿真程序仿真结果分析仿真研究的一般步骤l如何产生所需的随机变量l采用何种方法对离散事件系
