离散事件动态系统仿真.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 离散事件动态系统仿真,.,1,4.1,离散事件系统与模型基本概念,4.3,离散事件系统仿真策略,4.4,排队系统仿真,.,2,离散事件系统简介,离散事件系统是指系统状态由事件驱动的一类系统。银行服务系统是一种简单的离散事件系统，属于排队论。特别是近年来涌现出了一大批反映现代科学技术成果的人造系统，如计算机通信网络、柔性制造系统,(FMS),、计算机集成制造系统,(CIMS),、现代城市交通网络、军事指挥中的,C3I,系统等等，是一类非常复杂的系统。,.,3,离散事件系统简介,与传统的物理系统不同，这类系统中均存在着大量的离散事件过程，其运行规律难以用物理定律加以描述，而是服从于一些人为的规则。系统普遍投资巨大，运行费用昂贵，如何提高系统的利用率和运行效率是决策者、设计者与使用者普遍关注的研究课题，迫切需要在理论方面进行深入的研究。,.,4,简单的离散事件例子,某银行如图示，只有一个服务台为顾客提供服务，顾客随机地以,18,分钟间隔到达，到达间隔时间等概率出现的。顾客到达后如服务台空闲则接受服务，否则排入队列等待，直到最后得到服务并离开系统，排队规则先到先服务,(FIFO),。服务时间为,16,分钟，也是等概率出现。假定顾客到达间隔时间及服务时间取整数值。要求对该系统进行,10,个顾客的仿真，并给出其运行情况的评价，如顾客的平均等待时间，服务台的忙闲程度等。,.,5,简单的离散事件例子,服务台,等候队列,进入队列,顾客离去,顾客,1,2,3,4,5,6,7,8,9,10,到达间隔时间,8,6,1,8,3,8,7,2,3,服务时,间,4,1,4,3,2,4,5,4,5,3,.,6,基本数据及手动仿真,手动仿真关键是计算如下页图示仿真表，根据需要处理的相关问题而设计。第一个顾客,在,0,时刻到达，立即开始接受服务，并在,4,时刻结束其服务，该顾客在系统中逗留,4,分钟，第二个顾客在第,8,时刻到达，并能立即开始接受服务，此前服务台空闲,4,分钟，同理可考查第三个顾客，第,4,个顾客的到达的时间为,15,，因为此时服务台正在为第三个顾客服务，它需等待,3,个时刻，并在,18,时刻时接受服务，这个过程可以继续进行下去，直到全部,10,个顾客处理完毕。,.,7,手动仿真数据列表,.,8,离散事件仿真系统手动仿真所关心的内容主要有,:,顾客在系统中平均逗留时间、服务台空闲概率、顾客在队列中的平均等待时间、顾客需要等待的概率、需要等待的顾客的平均等待时间。,顾客在系统中平均逗留时间,=,顾客在系统中总的逗留时间,/,顾客总数,=44/10=4.4,离散事件系统手动仿真,.,9,离散事件仿真系统评价指标,服务台空闲概率,=,服务员总空闲时间,/,仿真运行时间,=(18/53)*100%=34%,顾客在队列中的平均等待时间,=,顾客在系统中总的逗留时间,/,顾客总数,=9/10=0.9,顾客需要等待的概率,=,等待的顾客数,/,顾客总数*,100%,=(3/10)=30%,.,10,离散事件仿真系统评价指标,需要等待的顾客的平均等待时间,=,顾客在系统中总的等待时间,/,等待的顾客数,=9/3=3.0,仿真结果表明，系统的功能是很好的，只有,30%,的顾客需要等待，平均等待的时间为,0.9,分钟，大约,34%,的时间服务台是空闲的。,.,11,离散事件动态系统所研究的主要问题,上面的仿真实例虽然简单，但却表明了离散事件仿真中需要解决的主要问题，包括如下几个方面：,1),如何确定输入数据的模式,(,如到达间隔时间分布与服务时间分布,)?,2),如何生成具有某一特定统计分布的随机变量,?,3),什么样的问题可由离散事件仿真解决,?,4),仿真是如何设计及实现的,?,5),仿真需要运行多长时间,?,.,12,离散事件动态系统所研究的主要问题,6),为了统计目的，需要运行多少次不同的仿真,?,7),为了分析仿真结果，需要采用什么样的统计技术,?,上面这种较小计算量的仿真是可以通过手动仿真实现的，但这种方式解决的问题的复杂性是极为有限的。通常需要仿真的顾客数是远远大于,10,的，为了进行统计，需要运行的仿真次数也将是很多的，因此应用计算机进行离散事件仿真是必须的。,.,13,4.1,离散事件系统与模型,.,14,离散事件动态系统,DEDS,（,Distributed Event Dynamic System,),固有的随机性，对这类系统的研究往往十分困难。,经典的概率及数理统计理论和随机过程理论虽然为这类系统提供了理论基础，并能对一些简单系统提供解析解。,对工程实际中的大量实用系统，唯有依靠计算机仿真技术才能提供较为完整的结果。,难点,核心问题,建立描述系统动态行为的仿真模型,不存在规范、形式化的、解析的形式,通常用流程图、状态转移图的形式,.,15,4.1.1,描述离散事件系统的基本要素,事件,活动,进程,临时实体：,在系统中只存在一段时间的实体(顾客)。,永久实体：,永远驻留在系统中的实体(服务员)。,实体,引起系统状态变化的行为，用于协调两个实体之间的同步活动和信息传递。比如顾客到达、离开、设备故障等。,通常用于表示两个可以区分的事件之间的过程，它标志着系统状态的转移.例如顾客开始接受服务到服务结束之间。,进程由若干个有序事件及若干个有序活动组成,它描述了所包含的事件及活动间的相互逻辑关系及时序关系。,顾客到达事件,服务开始事件,服务结束事件,排队活动,服务活动,进程,.,16,离散事件仿真的基本要素,实体,（,Entity,）：实体是系统的成分，如出纳员、顾客、机床、毛胚等。临时实体和永久实体。临时实体，如银行服务系统中的顾客，永久实体，如银行服务系统中的出纳员；,属性,(Attribute),：每一实体具有的有效特征称为实体属性，如银行服务系统中顾客到达时间，队列中等待的优先级，出纳员忙与闲等；,状态,（,State,）：实体状态是指在某一时刻该实体的所有属性值，系统状态由系统中各实体的状态合成。在银行系统中，一般状态有服务台忙闲，等待服务的顾客数，队列长度等；,.,17,活动,（,Activity,）：任何使系统状态发生某种变化的过程或行为。一般活动具有一定的持续时间，如顾客在银行中接受出纳员服务的过程称为服务活动；,事件,（,Event,）：改变系统状态的某一瞬时事变称为事件。事件通常发生在活动的开始或结束时刻；,进程,（,Process,）：实体的进程是由若干个该实体若干事件及活动构成的，它包含了这些事件和活动的逻辑关系和时序关系，例如，顾客的到达，排队、再经过出纳员服务到离去构成了一个进程。,.,18,事件、活动及进程的概念,顾客,3,顾客,2,顾客,1,出纳员,E1 E2 E3 E4 E5 E6,时间,顾客,2,的进程,顾客,2,的活动,其中：,E,事件，,X,顾客到达，,-,实体闲，,实体忙,X,X,X,.,19,4.3,离散事件系统仿真模型和策略,4.3.1,离散事件系统仿真模型,仿真程序的主要成分,仿真时钟：仿真时间的当前值；,事件表：有关未来事件表，包括事件名称和时间；,系统状态变量：描述系统状态的变量；,初始化子程序：用于模型初始化；,事件子程序：每一类事件的服务程序；,调度子程序：将未来事件插入事件表中的子程序；,时钟推进子程序：根据事件表决定下次事件，然后将仿真时钟推进到该事件发生的时刻；,随机数产生子程序：产生给定分布的随机数的子程序；,输出函数子程序：用于系统性能分析的子程序；,统计计数器：用来存放与系统性能分析有关的统计数据的各变量值；,主程序：调用上述各子程序并完成仿真任务的全过程。,.,20,仿真程序的流程管理,仿真时钟的推进方式,时间步长法,.,21,仿真程序的流程管理,仿真时钟的推进方式,事件步长法,.,22,仿真程序的流程管理,仿真时钟的推进方式,两者都是以时间增量来考察系统状态的变化，在时间步长法中，仿真时钟以等步长前进；事件步长法中，仿真时钟的步长取决于事件之间的间隔；,时间步长法在一个步长内，认为系统所处的状态相同，所选步长大小将影响系统仿真的精度；事件步长法中，每个事件的发生不需要人为的选取步长，步长的大小对仿真精度影响较小；,时间步长法每步进一个步长就要对整个系统进行一次全面考察，即使状态没发生变化也要扫描；事件步长法只有在某一事件发生时才进行扫描；,事件步长法与时间步长法的主要区别,:,.,23,仿真程序的流程管理,事件表,事件表是一个有序的记录表，每个记录包括事件发生的时间、事件类型等内容；,在某些离散事件的仿真中，采用事件表的形式进行调度；,同时事件管理方法,同时同类事件管理,混合同时事件管理：一步法和解结法,.,24,4.3,离散事件系统仿真模型和策略,4.3.2,离散事件系统仿真策略,仿真过程的控制和事件的调度方法，即采用什么样的方法安排事件并推进仿真时间，目前主要存在三种仿真策略。,.,25,4.3.2,离散事件系统仿真策略,事件调度法,用事件的观点分析真实系统，通过定义事件及每个事件引起系统状态的变化，按时间顺序确定并执行每个事件发生时有关的逻辑关系；,1),执行初始化操作,初始时间和结束时间设置,初始化事件表，设置系统初始事件,成分状态初始化,2,）操作事件表,取出具有,t(s)=mint,a,|a C,A,事件记录,修改事件表,3,）推进仿真时钟,TIME,=t(s),While,(,TIME,结束时间）,根据事件类型执行相应的事件处理程序,取出具有,t(s)=mint,a,|a C,A,事件记录,置仿真时间,TIME,=t(s),endwhile,.,26,4.3.2,离散事件系统仿真策略,事件调度法程序结构,.,27,4.3.2,离散事件系统仿真策略,活动扫描法,.,28,2025/1/15 周三,29,4.3.2,离散事件系统仿真策略,活动扫描法在具体实现时所采取的措施,.,30,4.3.2,离散事件系统仿真策略,活动扫描法的算法,.,31,4.3.2,离散事件系统仿真策略,活动扫描法程序结构,.,32,4.3.2,离散事件系统仿真策略,进程交互法,.,33,4.3.2,离散事件系统仿真策略,.,34,4.3.2,离散事件系统仿真策略,进程交互法程序结构,.,35,4.4,排队系统仿真,排队系统组成,1),到达模式：,临时实体按怎样的规律到达，一般用到达时间间隔来描述。,平均到达时间间隔：,T,a,=T/a,平均到达速率：单位时间内到达的临时实体,1/T,a,到达时间的分布函数,A,0,(t),：到达时间间隔大于,t,的概率,到达时间变化系数：到达间隔时间的标准差与平均到达间隔时间的比值,2,）,服务机构：,指同一时刻有多少服务台可以接纳临时实体，他们的服务要多长时间；,3,）,排队规则：,先到先服务、后到先服务、随机服务、优先权服务。,.,36,4.4,排队系统仿真,排队系统的性能的性能指标,.,37,4.4,排队系统仿真,排队系统的性能的性能指标,.,38,单服务台排队系统,.,39,离散事件仿真模型的设计与实现,仿真时钟,(CLOCK),的推进机制及其相应的仿真方法,离散事件系统仿真进行的是一种动态仿真，即仿真过程与时间有关，所以在仿真过程中按仿真时钟的推进机制离散事件仿真分为以下两类：,1,面向时间间隔的仿真方法,仿真时钟按较小且相同的时间间隔向前推进，推进一步需判断在所推进的这一时间间隔内是否有事件发生，并依此来改变系统状态变量值。,.,40,2,面向事件的仿真方法,仿真时钟每次推进到系统中下一事件将要发生的时刻。因为两个事件的发生间隔通常是非固定的，并大多具有随机性，因此每次时钟推进的时间间隔是不同的。,由于面向时间间隔的仿真方法中，在每一时间间隔内发生的事件都被当作在该时间间隔的末端发生来处理，这为仿真带来了误差。该方法的另一个缺点是当两个相邻事件间的时间相差比所给定的时间间隔大很多时，仿真器可能要连续推进多个时间间隔，但并不会产生任何影响，系统的状态也不会产生任何改变，无疑这会降低仿真系统运行的效率。因此，当今离散事件仿真多采用面向事件的仿真方法。面向时间间隔的仿真方法适用于系统中状态变量很多时的场合。,.,41,3,仿真模型的设计事件调度法,事件调度法是面向事件的仿真方法中最主要的方法，框图如下图示。应用事件调度法进行离散事件仿真，需建立一未来事件表,(FEL),，对未来事件进行排序，仿真时钟每次推进时，扫描未来事件表，并将时钟推进到下一最早发生事件的发生时刻并在,FEL,中清除、执行该事件，同时对系统状态变量、统计变量进行相应调整，产生的新未来事件加入到,FEL,中。,.,42,事件调度法程序框图,1.,仿真时钟,CLOCK=0;2.,产生初始,FEL;,3.,累计统计量置初值,;4,给定初始状态。,1.,从,FEL,中搜索下一事件,;,2.,将仿真时钟推进到该事件的发生,。,1.,修改系统状态变量,;,2.,收集、计算累积统计量,;,3.,产生未来事件并将其放入,FEL,中,。,1.,计算统计量,;,2.,打印报告。,仿真结束吗,Yes,No,结束,调用相应的事件,子程序,推进仿真时钟,初始化,.,43,排队系统基本知识,排队系统的两个最基本要素为顾客和服务台。一般排队系统都具有两个基本组成部分：,a.,到达模式,:,顾客到达模式由到达间隔时间或单位时间内到达顾客数量表示，泊松分布是常用随机到达模式，表示每个时间单位到达顾客数。,b.,服务机构,:,服务台个数，及服务台前单独排队多队列，服务时间的概率分布如何等。如指数分布及正态分布均是常见的服务时间分布。,c.,排队规则,:,排队规则是指对队列中排队的顾客进行服务的选择原则。常用的排队规则有以下几种：,.,44,先到先服务,(FIFO),顾客按到达先后次序接受服务，是最通常的情形；,-,后到先服务,(LIFO),后到的顾客首先接受服务，如仓库中堆积货物等；,-,随机服务,(SIRO),服务台空闲时，随机地选取一名顾客进行服务；,最短服务时间先服务,(SPT),服务台空闲时，选服务时间最短的顾客。,.,45,排队系统可用符号,GI/G/s,来表示，其中,:,GI,为到达模式，用,M,表示马尔科夫过程，若为确定性时间间隔，用,D,表示,;,G,为服务时间分布，分布函数的符号与,GI,相同,;,S,为单队多服务台的数目，且按,FIFO,方式服务。,例如一个具有指数分布到达间隔时间与服务时间，且按,FIFO,规则服务的单服务台单队列排队系统可记为,M/M/1,.,46,对排队系统常用的性能指标有如下几种：,顾客在系统中的稳态平均逗留时间,队列中稳态的平均队长,顾客平均等待时间,.,47,系统中稳态的平均顾客数,上述,4,个指标存在的条件是服务台利用率 ，其中的定义为,由上式可知服务台空闲的概率为,.,48,应用事件调度法对排队系统进行仿真,系统的各要素如下：,实体 顾客及服务台，其中顾客是临时实体，服务台是永久实体；,事件 系统中共有两类事件，即顾客到达事件,(A),和服务结束事件,(D),；,状态 系统的状态为队列中的顾客数及服务台忙闲,(,忙,=1;,空闲,=0),；,活动 到达间隔时间与服务时间见下表。,到达事件及服务结束事件的执行过程见下页图,1,及图,2,。,.,49,表,顾客的到达间隔时间及服务时间,顾客,1,2,3,4,5,6,7,8,9,10,到达间隔时间,-,8,6,1,8,3,8,7,2,3,服务时间,4,1,4,3,2,4,5,4,5,3,.,50,Clock=t,时,出现的到达事件,置出纳员为忙态,LST=1,产生服务时间，在,clock+,安排新的离开事件,FEL2,服务台忙,(LST=1),吗,?,队列个数,+1.,LQT=LQT+1,产生到达间隔时间，在,clock+,安排新的到达事件,FEL1,收集统计,返回主程序,是,Clock=t,时,出现的离开事件,队列个数,-1.,LQT=LQT-1,产生服务时间，在,clock+,安排新的离开事件,FEL2,队列非空,(LQT1),吗,?,置服务台空闲,LST=0,收集统计,返回主程序,是,否,图,1,到达事件子程序,ARRVL,框图,图,2,离开事件子程序,DPART,框图,.,51,在事件调度法模型中,FEL,最多含有两个事件，下页的表在,FEL,中的事件写成,(,事件类型，事件时间，顾客号,),的形式，此处加入顾客号,(,第,I,个顾客用,Ci,表示,),是为了对顾客进行跟踪。如,(D,，,4,，,C1),的含义为顾客,1,将在,4,时刻结束服务并离开系统。为了考查各顾客在系统中的逗留时间及排队时间，需知道各顾客的到达时间，这是通过,(,顾客号，该顾客到达时间,),来记录的，如,(C2,，,8),表示第,2,个顾客是在第,8,时刻到达的。,.,52,仿真中将收集以下,4,个累计统计量：,顾客在系统中总的逗留时间；,顾客在系统中总的等待时间；,服务台总的空闲时间；,需等待的顾客总数。,例如一个具有指数分布到达间隔时间与服务时间，且按,FIFO,规则服务的单服务台单队列排队系统可记为,M/M/1,。,下页是上述事件调度法仿真的模拟表。,.,53,表,4-4,事件调度法的模拟表,仿真,时钟,队列中的顾客数,服务台忙闲,系统中顾客的到达时间,未来事件表,FEL,顾客总逗留时间,顾客总等待时间,需等待的顾客总数,服务台总空闲时间,0,0,1,(C1,，,0),(D,，,4,，,C1)(A,，,8,，,C2),0,0,0,0,4,0,0,(A,，,8,，,C2),4,0,0,0,8,0,1,(C2,，,8),(D,，,9,，,C2)(A,，,14,，,C3),4,0,0,4,9,0,0,(A,，,14,，,C3),5,0,0,4,14,0,1,(C3,，,14),(A,，,15,，,C4)(D,，,18,，,C3),5,0,0,9,15,1,1,(C3,，,14)(C4,，,15),(D,，,18,，,C3)(A,，,23,，,C5),5,0,1,9,18,0,1,(C4,，,15),(D,，,21,，,C4)(A,，,23,，,C5),9,3,1,9,21,0,0,(A,，,23,，,C5),15,3,1,9,23,0,1,(C5,，,23),(D,，,25,，,C5)(A,，,26,，,C6),15,3,1,11,25,0,0,(A,，,26,，,C6),17,3,1,11,26,0,1,(C6,，,26),(D,，,30,，,C6)(A,，,34,，,C7),17,3,1,12,30,0,0,(A,，,34,，,C7),21,3,1,12,34,0,1,(C7,，,34),(D,，,39,，,C7)(A,，,41,，,C8),21,3,1,16,39,0,0,(A,，,41,，,C8),26,3,1,16,41,0,1,(A,，,43,，,C9)(D,，,45,，,C8),26,3,1,18,43,1,1,(C9,，,43)(C8,，,41),(D,，,45,，,C8)(A,，,46,，,C10),26,3,2,18,45,0,1,(C9,，,43),(A,，,46,，,C10)(D,，,50,，,C9),30,5,2,18,46,1,1,(C9,，,43)(C10,，,46),(D,，,50,，,C9),30,5,3,18,50,0,1,(C10,，,46),(D,，,53,，,C10),37,9,3,18,53,0,0,44,9,3,18,.,54,随机数与随机变量的产生,事件的发生具有随机性，进行离散事件系统仿真时要遇到多个随机变量并对其进行随机采样以得到仿真输入。例如，对排队服务系统进行仿真时，需要生成到达间隔时间、服务时间，它们是从某些分布（如指数分布）中抽取的样本值，产生随机变量的基础是随机数产生。,1,随机数的产生,0,，,1,区间上的均匀分布 是最简单最基本的随机数，其分布的概率密度函数为,是最简单最基本的随机分布，但它在离散事件系统仿真中起着特殊作用，各种其它形式的分布为的随机变量均可经过适当的变换与其互相转换。,随机数产生方法应满足以下要求：,a.,生成的随机数应具备随机样本统计性质，如均匀性、独立性等,b.,所产生的随机数序列是可重现的，以利于仿真实验的重复进行,c.,生成速度快、占用计算机内存少,d.,产生的随机数序列在足够长度内不会重复出现即应具有足够长的周期。,产生随机数的方法很多，大致可以归纳为如下三种：,a.,利用专门的随机数表；,b.,物理方法,产生随机数,；,c.,数学方法,产生随机数,。,.,55,2,常用的随机数产生方法，线性同余法,线性同余法,1951,年,Lehmer,由提出，随机数序列中的数是由下面递推公式产生,初始值 称为该随机数发生器的种子，常数 称为乘子，常数 称为增量，而常数,m,称为模数。,显然，根据上式有 即得到的随机数均在,0,，,m,-1,之间。为了得到,0,1),区间上分布的随机数，可以令：,例：若取 可以得到,从 开始，该序列将出现循环。,当 时称该算法为乘同余法，当 时，且 时称该算法为加同余法，当 且 时称该算法为混合同余法。从例子可以看出，由于模数,m,的位数有限，使得用,线性同余法产生的序列到了一定长度后，总会出现重复循环的现象，这种重复循环序列的长度被称为周期，当周期为,m,时称为满周期。为了使周期足够的长，必须选择适当的参数 、,m,、及 的值。,.,56,2025/1/15 周三,57,