排队系统和离散事件系统

1、第二讲 排队系统、离散事件系统基本概念系统根据其模型表示可以分为： 连续系统 离散事件系统连续系统n连续系统：其服从于物理学定律（电学、力学、热学），其数学模型可表示为传统意义上的微分方程或差分方程。n其系统的状态变量状态变量随时间而发生连续变连续变化化。n例如：？ 离散事件系统n离散事件系统离散事件系统（Discrete Event Dynamic System)DEDS/DES:n指系统的状态系统的状态在一些离散时间点离散时间点上由于某种事件的驱动而发生变化。其数学模型很难用数学方程来表示。n例如？生产系统是生产系统是DES系统！系统！离散事件系统基本要素离散事件系统基本要素n实体：实体：

2、构成系统的基本元素。是系统中有意义的一个物体。n有些实体在整个仿真过程中始终存在永久永久实体实体。n有些实体在一部分仿真过程中存在，有进入、退出系统的情况临时实体临时实体。n属性：属性：是指某一实体的特性。例如，在银行中，顾客是实体，其属性是帐户。n事件：事件：使系统状态发生变化的、实体的瞬间行为。注：事件还可能触发新的事新的事件件nDES中的事件具有三个特征：n1）离散事件是导致DES状态发生跃变和触发新的离散事件的唯一因素。n2）事件交互影响系统状态的变化。n 3）事件的发生时刻是异步的和不确定的。n状态状态：反映某一特定时间点的系统状态，如顾客的等待状态，机器的当前状态（忙或闲）等n活动

3、活动：实体在一段时间内持续进行的操作或过程。通常表示两个可以区分的事件之间的过程。标志着系统状态的转移。顾客的到达事件与该顾客开始接受服务事件之间可称为一个活动。如等待活动。n进程进程：由若干个有序事件及若干有序活动组成，描述了它所包括的事件及活动的相互逻辑关系及时序关系。三、三、DES系统举例系统举例n理发店理发店：分析其实体、状态、事件、活动 Answer: 实体：顾客、服务员 状态：服务员个数、顾客数、服务员忙闲 事件：顾客到达、服务完毕 活动：顾客等待、理发员服务n柔性制造系统： 请分析其实体、状态、事件Answer:n实体：工件、加工中心n事件：（待加工工件）到达 机床完成加工 状态

4、：各加工中心的繁忙程度 各加工中心的等待队列 活动：工件等待 加工思考：n 1）文件处理系统是否属于DES系统？分析其实体、状态、事件、活动。n2）银行系统是否属于DES系统？分析其实体、状态、事件、活动。排队系统n排队系统的基础四、离散事件系统仿真步骤四、离散事件系统仿真步骤1）问题提出2）系统分析与描述：边界、约束、目标3）建立系统的数学模型数学模型4）数据收集5）建模仿真模型仿真模型： n6）模型验证(verification)n系统模型系统模型是否由准确地仿真模型（计算机程序）表示。n方法：程序调试、程序逻辑流程图n7）模型确认(Validation)n是否模型代表实际系统？仿真钟n用

5、于表示仿真事件的变化n离散事件系统仿真中，由于系统状态变化是不连续的，在相邻两个事件发生之间，系统状态不发生变化，因而仿真钟可以跨越这些“不活动”区域。从一个事件发生时刻，推进到下一个事件发生时刻。n仿真钟的推进呈跳跃性，推进速度具有随机性。n仿真钟一般是仿真的主要自变量，仿真钟的推进是系统仿真程序的核心部分。n仿真钟所显示的是仿真系统对应实际系统的运行时间，而不是计算机运行仿真模型的时间。n仿真时间与真实时间将设定成一定比例关系，使得复杂的系统，真实系统运行若干天、若干月，计算机仿真只需要几分钟可以完成。仿真钟推进方法n固定增量推进方法n按下一最早发生事件的发生时间推进-事件调度法固定步长时

6、间推进机制的特点：n每次步长推进，都要进行事件检查，占用计算和判断的时间，影响仿真效率。步长t越小，问题越严重。n该机制将发生在同一步长内的事件都视为发生在该步长的末尾，即认为它们是同步的。由此产生误差，影响仿真精度。步长t越大，误差越严重。 合理确定t ，是固定步长时间推进机制中的重要问题。 下次事件时间推进机制：n仿真时钟按照下一个事件预计将要发生的时刻，以不等的时间间隔向前推进。即仿真时钟每次都要跳跃性地推进到下一个事件发生的时刻上去。n该推进机制中，仿真时钟的增量不定，取决于被仿真系统。n仿真时，需将事件按发生时间的先后次序排列，仿真时钟时间则按事件顺序发生的时刻推进。当某一事件发生时

7、，需立即计算下一事件发生的时刻，以便推进仿真时钟，直到仿真运行结束。离散事件系统的仿真策略n仿真策略是仿真模型的核心，反映了仿真模型的本质，从根本上决定了仿真模型的结构。n仿真策略有三种：n事件调度法n活动扫描法n进程交互法模型的非形式化描述术语n成分（Component）：相对于系统中的实体，用于构造模型中的各个部分，分为主动成分（Activetype Component）与被动成分（Passivetype Component） C=1, 2 ,n表示系统中n个成分； CA =1, 2 ,m表示系统中m个主动成分； CP =m1, m2 ,n表示系统中n - m个被动成分；n描述变量：成分的

8、状态与属性 S为所有成分的状态变量，值域为S； P=p1, p2, ,pK为系统中的参数（属性）集合； t 为成分的状态的下一变化时刻，值域为R+ D (S)表示成分在状态S时的条件是否满足，True/False TIME为模型仿真时钟的值，值域为R+成分间的相互关系事件调度法（Event Scheduling）n基本思想：将事件作为仿真模型的基本单元，按事件发生的先后顺序不间断地执行相应的事件，每一事件可预先知其发生时间的确定事件都带有一个例程。n实现方法：模型中所有待发生的事件都放于事件表中，模型中设一个时间控制成分，从事件表选择最早发生的事件，并将仿真时钟推进到该事件发生的时刻；这样事件

9、的选择与处理不断进行直至仿真终止。n事件调度法的算法流程：n置初始时间tt0，结束时间tte；n事件表初始化，置系统初始事件；n成分状态初始化：S(s1,t 1 ), ,(sm,t m ), sm+1, sn)；n操作事件表：取出具有t(s)=mint| CA事件记录；修改事件表；n推进仿真时钟：TIMEt(s)；nWhile（TIME= t ）则执行case 根据事件类型i：i1 执行第1类事件处理程序；i2 执行第2类事件处理程序；im 执行第m类事件处理程序；end case取出具有t(s)=mint| CA事件记录；修改事件表；推进仿真时钟：TIMEt(s)； end whilen事件

10、调度方法-手工仿真活动扫描法（Activity Scanning）n策略思想：系统由成分构成，而成分包含活动，这些活动必须满足某些条件；每一主动成分均有一个活动子例程；活动的发生时间也作为条件之一，而是较之其他条件具有更高的优先权。n实现方法：设D(S)表示成分在系统状态S的条件是否满足，t表示成分的状态下一发生变化的时刻。活动扫描每一步要对系统中所有的主动成分进行扫描，当tTIME 表示该活动将在将来某一时刻发生； tTIME 表示该活动如果条件满足，则应立即发生； tTIME, PRESENT(S)= |t=TIME,PAST(S)= |tTIME；将满足下列条件： PRESENT(S)U

11、 PAST(S),且D(S)=True的成分置于可激活(Activable)的成分集合中，此时仿真时钟不推进，仅仅处理成分活动，修改成分仿真时钟；n如果可激活成分集合为空，则将系统仿真时钟推进到下一最早发生的活动生成时刻，即TIMEmin（t FUTURE(S)）n活动扫描法的典型算法：n置初始时间tt0，结束时间tte；n设置主动成分的仿真时钟t（i）（i1，2，m）；n成分状态初始化：S(s1,t 1 ), ,(sm,t m ), sm+1, sn)；n设置系统仿真时钟TIMEt0；nWhile（TIME= t ）则执行扫描for j最高优先级 到 最低级 将优先级为j的成分置成 i， i

12、f ( t(i)TIME 且 Di(S)= True )执行活动子例程i；退出，重新扫描该优先级的余下主动成分 end ifend for TIMEmin(t FUTURE(S) end while进程交互法（Process Interactive）n策略思想：采用进程描述系统，他将模型中的主动成分所发生的事件及活动按事件顺序进行组合，从而形成表，一个成分一旦进入进程，他将该进程可执行的全部活动。n实现方法：系统仿真时钟的控制程序采用两张事件表，其一是当前事件表(CEL)，它包含了从当前时间点开始有资格执行的事件的记录，但是该事件是否发生的条件尚未判断；其二是将来事件表(FEL)，它包含在将来

13、某仿真时刻发生的事件的事件记录。当仿真时钟推进时，满足t=TIME的所有事件记录FEL转移到CEL中，然后对CEL中的每一事件进行扫描，若D(S)=True,则发生该事件，只要条件允许该进程尽可能推进直至进程结束；若D(S)=False或仿真时钟要求其停止，则退出该进程。然后处理下一CEL中的事件，直至CEL扫描完毕。继续推进仿真时钟，直至仿真结束。n进程交互法的一般算法：n置初始时间tt0，结束时间tte；n设置初始化事件，并置于FEL中；n将FEL中有关的事件记录置于CEL中，n成分状态初始化：S(s1,t 1 ), ,(sm,t m ), sm+1, sn)；n设置系统仿真时钟TIMEt

14、0；nWhile（TIME= t ）则执行1. CEL扫描while (CEL中最后一个记录未处理完) 则 while (Di(S)= True有关成分未处理完) 则执行该成分的活动确定该成分的下一事件 end whileend while2. 推进仿真时钟TIME = FEL 中安排的最早时间 if （TIME= t ）则 将FEL中所有在TIME时刻发生的事件记录转移到CEL中 end ifend while离散事件系统仿真策略的比较n系统描述：n所有策略均描述主动成分与被动成分。在事件调度法中只有主动成分CA才能施加作用；而其他策略中主动成分CA与被动成分CP都可以施加作用。n事件调度法：事件；活动扫描法：活动；进程交互法：进程n建模要点：n事件调度法：只对无条件执行事件建模，条件测试与执行包含于无条件事件执行例程中；n活动扫描法：对所有活动建模，专设条件初始模块；n进程交互法：将进程分若干步，每一步包括条件测试于执行两部分；n事件调度法：主动成分的下一事件时间保存在事件表中，定时模块不断从中取出最早发生的事件，推进仿真时钟到该事件的发生时间，并中心该事件例程。n活动扫描法：每一主动成分设一个成分时钟，定时模块选择那些成分时钟大于当前系统仿真时钟的主动成分中成分时钟最小的成分时钟，然后推进系统仿真时钟到该时刻，并开始活动扫描。n