版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
--19・-19--19-第4章离散事件系统仿真方法4.1离散事件系统仿真一般概念4.1.1一般概念离散事件系统:系统中的状态只在离散时间点上发生变化,而且这些离散时间点一般是不确定的。系统状态是离散变化的,而引发状态变化的事件是随机发生的,因此这类系统的模型很难用数学方程来描述。随着系统科学和管理科学的不断发展及其在军事、航空航天、CIMS和国民经济各领域中应用的不断深入,逐步形成一些与连续系统不同的建模方法:流程图、网络图等。(1)实体:是描述系统的三(四)要素之一,是系统中可单独辨识和刻画的构成要素。如:工厂中的机器,商店中的服务员,生产线上的工件,道路上的车辆等。从仿真角度看,实际系统就是由相互间存在一定关系的实体集合组成的,实体间的相互联系和作用产生系统特定的行为。实体可分为两大类:临时实体和永久实体临时实体一一在系统中只存在一段时间的实体。一般是按一定规律由系统外部到达系统,在系统中接受永久实体的作用,按照一定的流程通过系统,最后离开系统。临时实体存在一段后即自行消失,消失有时是指实体从物理意义上退出了系统的边界或自身不存在了;有时仅是逻辑意义上的取消,意味着不必再予以考虑。如:进入商店的顾客、路口的车辆、生产线上的工件、进入防空火力网的飞机、停车场的汽车等。永久实体一一永久驻留在系统中的实体。是系统产生功能的必要条件。系统要对临时实体产生作用,就必须有永久实体的活动,也就必须有永久实体。可以说临时实体与永久实体共同完成了某项活动,永久实体作为活动的资源而被占用,如:理发店中的理发员、生产线上的加工装配机械、路口的信号灯等。临时和永久是相对的属性和行为相同或相近的实体可以用类来描述,这样可以简化系统的组成和关系。如:理发店服务系统可以看成是由“服务员”和“顾客”两类实体组成的,两类实体之间存在服务与被服务的关系。⑵属性是实体特征的描述,一般是系统所拥有的全部特征的一个子集,用特征参数或变量表示。选用哪些参数作为实体的属性与建模目的有关,一般按以下原则:便于实体分类:如按理发店顾客的性别;便于实体行为的描述:如飞机的速度便于排队规则的确定:如生产线上待处理工件的优先级水平。⑶活动实体在一段时间内持续进行的操作或过程。活动所占用的时间段称为忙期,忙期可以是定时的或随机的。般要给出忙期的计算公式或概率分布函数,保证一个实体一进入某一活动,其忙期就可以计算或从概率分布函数中抽取得到,如“服务员”对“顾客”的服务,其忙期就可以从指数分布函数抽样得到(服务时间)。很多情况下的活动是由几个实体协同完成的。⑷状态对实体活动的特征状况划分,其表征量称为状态变量。在理发中,顾客有等待服务、接受服务等状态,服务员有忙、闲等状态。活动总是与一个或几个实体的状态相对应。状态可作为动态属性进行描述。--19・--19・⑸事件导致系统状态产生变化的瞬间操作或行为。从某种意义上说,系统是由事件来驱动的。事件发生的时刻称为事件点。不关心事件所代表的操作和行为意义时,事件与事件点是同义语。若事件发生是有前提的,则称为条件事件。活动、状态和事件三者间关系:事件的发生导致状态的变化,实体的活动可以与一定的状态相对应,因此可以用事件来标识活动的开始和结束。见下图:SiS3SiSiS2E\ E2A2 E3活动、状态、事件及逬程S2S2E\ E2A2 E3活动、状态、事件及逬程⑹进程一组按发生时间排列的事件/活动序列称为一个进程(见上图)。(7)队列处于等待状态的实体序列。一般按新到的实体排在队尾的次序组成。在建模中,队列可作为一种状态或特殊实体对待。⑻仿真钟用于表示仿真时间的变化。其推进方法与仿真策略有关。⑼统计计数器离散事件系统的有些变化是随机的,一次仿真运行得到的状态变化过程只不过是随机过程的一次取样。如果进行另一次独立的仿真运行所得到的状态变化过程可能完全是另一种情况。一般只在统计意义下有参考价值!一般在仿真中需要一个统计计数部件,以便统计系统中的有关变量。如:服务系统中的平均队长.顾客的平均等待时间、服务员的利用率等。4.1.2离散事件系统仿真的一般步骤基本步骤与连续系统仿真类似,但有些特殊问题:(1)系统建模系统模型一般用流程图或网络图的方式来描述。反映了临时实体在系统内部历经的过程、永久实体对临时实体的作用以及它们之间的逻辑关系0⑵确定仿真算法包括两方面内容,一是如何产生所需求的随机变量;二是釆用怎样的方法进行仿真,即仿真策⑶建立仿真模型根据已经确定的仿真算法,进行变量定义、流程图确定,完成仿真程序实现。⑷仿真结果分析离散事件系统固有的随机性,每次仿真计算结果仅仅是随机变量的一次取样,要运行多次,并釆用适当的方法进行分析。
4.2离散事件系统建模方法4.2.1实体流4.2.1.1实体流程图釆用与计算机程序流程图相类似的图示符号和原理,建立表示临时实体产生、在系统中流动.接受永久实体“服务”以及消失等过程的流程图。借助实体流程图,可以表示事件、状态变化及实体间相互作用的逻辑关系。计算机程序框图思想和编制方法已广为接受,实体流程图的编制方法虽然简单,但对离散计算机程序框图事件系统的描述却比较全面,应用比较普遍。用实体流图方法建模没有特别的技巧和理论可言:一是要对实际系统的工作过程有深刻的理解和认识;二是要将事件.状态变化、活动和队列等概念贯穿于建模过程中。常用符号:◊菱形框一一判断;◊矩形框一一事件、状态、活动等中间过程;16I端矩形框一一开始和结束;
16I端矩形框一一开始和结束;◊箭头线一一逻辑关系。具体建模思路:确定组成系统的实体及属性,将队列作为一种特殊的实体来考虑。分析各种实体的状态和活动,及其相互间的影响。队列实体的状态是队列的长度。考虑有哪些事情(事件)导致了活动的开始或结束,或者可以作为活动开始或结束的标志,以确定引起实体状态变化的事件,并合并条件事件。分析各种事件发生时,实体状态的变化规律。在一定的服务流程下,分析与队列实体有关的特殊操作(如换队等)。(7)通过以上分析,以临时实体的流动为主线,用约定的图示符号画出被仿真系统的实体流程图。(7)给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法。属性描述变量,如顾客到达时间、服务时间等,可以取一个固定值(由某一计算公式取值);也可以是一个随机变量,要给出其分布函数。(8)给出队列的排队规则。有多个队列存在时,还应给出其服务规则(包括队列的优先序、换队规则等)4.2.1.2举例例4・1:理发店服务系统小理发店,只有一个理发员。顾客来到理发店后,如果有人正在理发,就坐在一旁等候。理发
员按先来先理的原则为每一个顾客服务,而且只要有顾客就不停歇。建模目的是研究在假定顾客到达间隔和理发所花的时间服从一定概率分布时,考察理发员的忙闲情况。分析:实体理发员(永久)顾客(临时)顾客队列活动理发与理发员协同完成理发活动状态忙/闲等待/接受服务队列长度本问题只有一个队列,顾客不会因排队人数太多而离去,因此队列规则很简单,没有特殊的队列操作。--19・--19・-19・-19・理发店服务系统实体流图需给出的模型属性变量:顾客的到达时间(随机变量),从分布函数中获取;理发员为一个顾客理发所需的服务时间(随机变量),从分布函数中获取;◊队列的排队规则:先到先服务(FIFO),每到一位顾客就排在队尾,服务员先为排在队首的顾客服务。例4・2:售票窗口服务系统剧院雇佣一名售票员同时负责剧票的窗口销售和对电话问询者的咨询服务:>窗口服务比电话服务的优先级高。>问询者打来电话由电话系统存储后,按先来先服务的原则一一予以答复。>建模目的:研究售票员的忙闲率。>此例中有两类实体同时流动,可能出现资源冲突。分析:实体售票员(永久)购票者(临时)电话问询者(临时)购票者队列电话问询者队列活动窗□售票/电话服务买票(与售票员协同)冋询(与售票员协同)状态空闲/回电话/售票等待/接受服务等待/接受服务长度长度售票窗□服务系统实体流图模型属性变量:•购票者到达时间•电话问询者到达时间•售票服务时间•电话服务时间。排队规则:•窗口购票者和电话问询者分别排队;•优先进行窗口服务。注:实体流图是为描述实体流动和相互间逻辑关系而绘制的,与计算机程序框图不同,与编程实现的要求还有较大距离。--19・--19・4.2.1.3模型的人工运行模型人工运行一一建立实体流图模型后,选取有代表性的例子将流图全部走一遍。人工运行要求遍历流程图的各个分支和实体的各种可能状态,在时间逐步变化的动态条件下,分析事件的发生及状态的变化过程,以检查模型的组成和逻辑关系是否正确。例4・1中,假定:系统初始状态:•永久实体“理发员”及特殊实体“队列”的状态。•初始时刻是指仿真开始的时刻,可以对应为实际系统(理发店)开门营业的时间。此时理发员为“闲”,队列长度为“0”(空)。模型参数及变量的取值:•第i个顾客与第个顾客到达的时间间隔•以及理发员为第i个顾客的理发时间$。•一般来说,4。、S,•均为随机变量,因根据其分布函数产生。•为举例方便,取其样本值为:♦A/=15,A2=32,43=24,A4=40,As=22, ♦S/=43,S2=36,S3=34,Sf28,模型的人工运行规则规则1一一确定当前时间运行开始时,取当前时间TIME=to(为仿真初始时刻)。运行开始后,当前时间逐步向前推移,且递推至下一个最早发生事件的发生时刻。如果当前时间有顾客到达事件发生,转规则2;若有顾客离去事件发生,转规则3。规则2一一顾客到达事件处理假定在时刻"ME有顾客,到达,根据实体流程图可知,如果此时理发员忙,则入队列等待,队列长度加1;否则置理发员为“忙”状态,顾客开始理发,且在么="ME+S「•时刻理毕离去。规则3—一顾客离去事件处理假定在时刻"ME有顾客/离去,根据实体流程图可知,如果此时队列长度为0,则置理发员为“闲”状态;否则,队列中排在队首的一名顾客开始理发,队列长度减1,并且该顾客在d^TIME^Si时刻理毕离去。上述规则体现了“事件调度法”的基本思想。如果还存在其它事件或复杂的服务流程时,则需增加相应的规则。
理发店模型人工运行结果时间事件理发员状态队列状态下一最早事件当前将来tt+/t长度0No15/1A闲闲015/1A151A47/2A,58/ID闲Bl047/2A472A71/3ABlBl158/ID58ID94/2DBlB2071/3A713A111/4AB2B2194/2DA/=15,A2=32,Aj=24,?L/=40,A5=22, Sl=43,S2=36,S3=34,S4=28, 4.2.2活动周期图法4.2.2.1活动周期图实体流图法中:实体的行为模式在有限的几种情况之间周而复始地变化,表现出一定的生命周期形式。理发员实体:状态在“忙”和“闲”之间不断变化,“忙”意味着理发员与顾客正在协同完成“理发”活动。顾客实体:群体行为是在“到达”、“等待”、“理发”和“离去”之间周而复始变化。活动周期图法正是基于这种思想逐步形成的一种离散事件系统建模方法。以直观的方式显示了实体的状态变化历程和各实体之间的交互作用关系,便于理解分析。可以充分反映各类实体的行为模式,并将系统的状态变化以“个体”状态变化的集合方式表示出来,因此可以更好地表达众多实体的并发活动和实体之间的协同。但是,它只描述了系统的稳态,而没有表示系统的瞬态,即活动的开始和结束事件。活动周期图:活动周期法基本图符实体状态:静寂(Dead)、激活(Active)活动周期法基本图符状态之间:用箭头连接,不同的实体用不同的线型,表示各种实体的变化历程。激活状态:通常是实体的活动,模型中活动的忙期可釆用随机抽样的方法事先加以确定;静寂状态:通常表示无活动发生,是实体等待参加某一活动的状态,其持续时间在模型中无法事先确定,取决于有关活动的发生时刻与忙期。每一类实体的生命周期都有一系列状态组成。随着时间的推移和实体间的相互作用,各个实体从一个状态变化到另一个状态,形成一个变化过程。活动周期图建模过程如下:确定组成系统的实体及属性:确定组成系统的永久实体和临时实体,队列不作为实体考虑。分别画出各实体的活动周期图:要以实际过程为依据,队列作为排队等待状态来处理;实体流程图中当作事件看待的某些操作或行为,要拓展为活动来处理。活动周期图服从两个原则:•交替原则:静寂状态和活动状态必须交替出现。如果实际系统中某一活动完成后其后续活动就立即开始,则后续活动为直联活动。为使直联活动与其前置活动的连接仍符合交替原・19---19・--19・则,规定这两个活动之间存在一个虚拟的队列。•闭合原则:每类实体的活动周期图都必须是闭合的,其中临时实体的活动周期图表示一个或单位实体从产生到消失的循环过程,而永久实体的活动周期图则表示一个或几个实体被占用和被释放的循环往复过程。将实体的活动周期图联结成系统的活动周期图:以各实体之间的协同活动为纽带,将各种实体的活动周期图合并在一起。增添必需的虚拟实体:在活动周期图中,当一个活动的所有前置静寂状态均取非零值(队列不空)时,该活动才有可能发生。利用这一特性,可以增添某些必要的虚拟实体,并假定它们与另外的实体协同完成某项活动。利用这种办法可以为实体活动的发生加上某种附加条件,从而实现“隔时发生”的建模效果。标明活动发生的约束条件和占用资源的数量:>活动是否可以发生的判断条件,这些条件应是用活动周期图示符号无法或不便表达的。活动发生的条件一般为某种表达式,标在活动框的旁边。永久实体在参加一次协同活动时被占用和活动完成时释放的数量。协同活动发生时占用/释放永久实体(资源)的数量标在相应箭头线的旁边(带有+/•符号),数量为一时不标。(6)给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法,并给出排队规则和服务规则。4.2.2.2举例举例(例4.2):售票窗口服务系统剧院雇佣一名售票员同时负责剧票的窗口销售和对电话问询者的咨询服务:>窗口服务比电话服务有更高的优先级。>问询者打来电话由电话系统存储后按先来先服务的原则一一予以答复。占建模目的:研究售票员的忙闲率。>此例中有两类实体同时流动,可能出现资源冲突。实体售票员(永久)购票者(临时)电话问询者(临时)活动窗□售票/电话服务买票(与售票员协同)问询(与售票员协同)状态售票/回电话(激活)空闲(静寂)接受服务(激活)等待(静寂)接受服务(激活)等待(静寂)电话二0购票后消失•假想进入系统外部。交替原则:存在一个静寂状态(外部)备的购票者从系统外部到达.排队。交替原则、封闭原贝I」:存在一个激活状态(到达)。外剖顾客=0到达 、约朿条件,表明前一顾客到达活动完成后,下一顾客才能开始到达。排队等待开关引入虚拟实体“门”.来代替给活动施加的约束“顾客=0”。计肘活动的忙期取决于顾客到达的时间间隔。引入虚拟实体后的到达活动购票者的活动周期图电话问询者的活动周期图售票员活动周期图••购票者到达时间活动周期图在描述两类以上临时实体资源竞争问题时较简练、清晰。模型属性变量:•电话问询者到达时间•售票服务时间•电话服务时间。排队规则:•窗口购票者和电话问询者分别排队电话二0售票窗□服务系统活动周期图•优先进行窗口服务。
电话二0售票窗□服务系统活动周期图4.2.2.3模型的人工运行确定初始状态(符合被仿真系统运行前的实际情况):标记临时实体在初始状态下的位置。一般情况下,它们处于生命周期起始点所对应的静寂状态,如例题中的“外部”状态;有时部分实体可能处在“排队等待”等中间状态。标记永久实体在初始状态下的位!标记永久实体在初始状态下的位!般情况下,它们处于“等待”或“空闲”等静寂状态。确定运行规则:规则1一一活动的发生与执行按照服务优先级,依次检查临时实体每一项活动的前置状态(均为静寂状态)和标在活动上方的发生条件,判断活动是否可以开始。满足以下两个条件的活动可以开始:(1)活动的所有前置状态中均有实体停留,且各类永久实体的数量超过或等于相应箭头线上所标明的占用量。(2) 活动发生的约束条件已经满足。如果某项活动可以开始,则在相应的活动框中标出正在进行该活动的临时实体标号;对于哪些被确定可以开始的活动,需根据各项活动的忙期分别确定其终止时间(等于当前时间加上活动忙期),并将终止时间标在活动框外。
规则2——确定当前时间检査所有活动的终止时间,从中选择最小者作为当前时间规则3—一活动的完成从所有已发生的活动中,检出终止时间等于当前时间的临时实体,删掉其标在活动框外的终止时间。运行过程中要注意标注:实体的状态、时间等。■■■运行过程中要注意标注:实体的状态、时间等。■■■1=1在对从系统“外部”到达的临时实体标注时要注意:/“外部”状态中一般有无数个临时实体存在,因此无法一一标注,可采用特殊符号e进行标注,代表有很多临时实体存在于系统“外部”。/从前置活动进入到“外部”状态的临时实体不必再行标注。4.3离散事件系统仿真方法离散事件仿真要解决两个问题:随机变量的产生和仿真策略。4.3.1随机变量的产生离散事件系统仿真过程中要用到许多服从不同分布类型及参数的随机变量。产生随机变量的基础是产生[0,1]区间上均匀分布的随机变量一一也称为伪随机数发生器。其他各类分布,如正态分布、丫分布、卩分布.泊松分布等,都可以用某种方法通过对均匀分布进行某种变换来实现。严格地说,计算机中的随机数发生器不是概率意义下的真正随机数,只能称为伪随机数,原因是无论哪一种随机数发生器都采用递推算法。但如果算法选择合适,得到的数据通过统计检验后能具有较好的统计特性(如均匀性、独立性等)。这种伪随机数可以用于仿真。随机数发生器(线性同余发生器):应用较广泛,递推公式为:X”= i+c)modmUn=Xng初值比其中:f--第比个随机数a——乘子(乘数)c——增量(加数)m 模数5--[0,1]区间上的随机数表示对N进行模数为加的求余运算如果血取得足够大,结果屁是[0,1]之间均匀分布的。一般计算机语言中都提供相应的语句或函数。但使用前最好做检验。(随机数发生器测试)4.3.L2随机变量的生成反变换法等,一般提供标准的,但具体使用时要根据需要做相应变换。4.3.2离散事件系统仿真方法4.321离散事件系统仿真的基本原理仿真机制:实体.事件和活动是离散事件系统的重要组成部分,其中最能反映系统本质属性的对象就是随机离散事件。离散事件系统仿真过程的核心,就是安排和处理离散事件和仿真钟的推进。因此,离散事件系统仿真具有事件安排和时间推进的基本仿真机制一一面向事件的仿真方法。如下图:--19・--19・在较为复杂的离散事件系统中,一般都存在诸多的实体,这些事体之间相互联系、相互影响,然而其活动的发生却统一在同一时间基上,釆用何种方式推进仿真钟,建立起各类实体之间逻辑关系,是离散事件仿真的重要内容。仿真钟的推进方式(有两种):⑴事件单位推进(面向事件的仿真钟推进)仿真钟是按下一最早发生事件的发生时间推进,即时间控制部件从事件表中选择具有最早发生时间的事件记录,然后将仿真钟推进到该事件发生的时刻。对于每一类事件,仿真模型应建立相应的事件子程序/函数(事件例程),并根据最早发生事件的类型调用相应的事件子程序/函数,进行事件处理,然后返回时间控制部件。这样,事件的选择与处1=1■—»<理不断地进行,1=1■—»<仿真时钟的推进呈现跳跃性。由于事件的产生具有随机性,仿真钟的推进速度也是随机的。⑵时间单位推进(面向时间间隔的仿真钟推进)类似于连续系统仿真的等步长策略,即仿真钟以固定的时间间隔推进,在每一个时间间隔点,判断是否有事件发生,若有事件发生则按优先顺序进行处理事件,改变系统状态,且事件发生在该步结束时刻,然后再向前推进一个时间单位。事件单位推进方式效率较高,一般情况下可以节省时间,广泛釆用,但其设计和实现比较复杂。对于大多数离散事件系统,由于一般都具有较强的随机性,故最常釆用面向事件的仿真钟推进方式。时间单位推进将每步内发生的所有事件都当作该步末端时刻发生的,使得一些时间间隔较小的事件表现为同步发生,这样就会产生较大的偏差。为了克服这个缺点,需要将时间单位取得足够小,这又使计算量增大。基于时间单位推进方式的特点,它主要用于系统事件发生时间具有较强周期性的模型,如定期订货的库存系统,以年月为单元的经济计划系统等。43.2.2离散事件系统仿真策略连续系统仿真方法主要是研究满足不同精度和速度要求的连续模型的离散化方法。离散事件系统的模型难以采用某种规范的形式,一般采用流程图或网络图的形式才能准确地定义实体在系统中的活动。(1)事件调度法1963年兰德公司的SIMSCRIPT语言的早期版本中。美国广泛釆用,欧洲不很流行。基本思想:将事件(处理)例程作为仿真模型的基本模型单元,按照事件发生的先后顺序不断执行相应的事件例程。每一事先可预知其发生时间的确定事件都带有一个事件例程,用以处理事件9-9-19・发生后对实体状态所产生的影响,并安排后续事件;条件事件并不具有事件例程,对它的处理隐含在某一确定事件例程中。因此,事件调度法中所说的事件是指确定事件。对实体流图法建立的模型,一般釆用事件调度法。事件调度法的仿真策略:(1)初始化I仿真的开始时间力和结束时间SI实体的初始状态;/置初始事件及其发生时间ts.仿真时钟TIMERS确定当前时钟"ME下发生的事件类型E,i=l,2,3,…用,并按规则排序如果执行{caseEtofEiz执行E,的事件例程;产生后续事件类型及发生时间;
E〃:执行E〃的事件例程;产生后续事件类型及发生时间;endcase}否则,转(6);(5)将仿真时钟"ME推进到下一最早事件发生时刻,转(3);(6)仿真结束。上述第(5)步体现了仿真时钟的推进机制,是将仿真时钟推进到下一最早事件的发生时刻。与连续系统仿真中的时间推进方法固定时间增量法不同,反映了离散事件系统状态仅在离散时刻点上发生变化的特点,这种事件推进方法为离散事件系统仿真策略所普遍采用,称为下一事件增量法,f--19・--19・称事件增量法。举例(例4.2):售票窗口服务系统剧院雇佣一名售票员同时负责剧票的窗口销售和对电话问询者的咨询服务:总控程序如上图,设计事件例程的逻辑流程图。有4个事件需要考虑:①购票者到达事件EizQ事件例程逻辑上与实体流程图是一致的,但要加以细化,描述也发生后所需完成的一组操作。总控程序调用E/事件例程(购票者到达)--19・--19・②购票者服务结束事件民:民事件例程逻辑流程见下图。总控程序调用E2事件例程(购票者服务结束)③电话到达事件En艮事件例程逻辑流程见下图。总控程序调用总控程序调用-19-19总控程序调用总控程序调用-19-19事件例程(电话到达事件)--19・--19・④通话结束事件艮:血见下图。总控程序调用E/事件例程(通话结束)注意:所有事件例程中都有安排将来事件的操作,其中下一顾客到达时间和服务时间的产生由--19・--19・随机抽样公共程序完成,将来事件通过总控程序插入事件表。如果事件殆(电话到达)与其它事件同时发生,则总控程序赋予它较低的优先级。为了在仿真运行过程中定时釆集系统数据,可以再增加一类数据釆集事件:数据采集事件例程⑵活动扫描法事件调度法中,仿真钟的推进仅仅依据对下一个最早发生的事件的判断,而该事件发生的任何条件的测试则必须在该事件处理程序内部去处理。如果条件满足,该事件发生,而如果条件不满足的话,则推迟或取消该事件的发生。此,从本质上讲,事件调度法是一种“预定事件发生时间”的策略。这样,仿真模型中必须预定系统中最先发生的事件,以便启动仿真进程。在每一类事件处理例程中,除了要修改系统的有关状态外,还要预定本类事件的下一事件将要发生的时间。该策略对于活动持续时间确定性较强(可以是服从某种分布的随机变量)的系统是比较方便的。但是,事件的发生不仅与时间有关,而且与其它条件有关,即只有满足某些条件时才会发生。这种情况下,事件调度法策略的弱点就表现出来了,由于这类系统的活动持续时间具有不确定性,因而无法预定活动的开始或终止时间。活动扫描法就是针对上述特点产生的。在英国很流行,最早出现在1962年Buxton和Laski发布的CSL语言中。活动扫描法与活动周期模型有较好的对应关系。活动周期图中的任一项活动活动都可以由开始和结束两个事件来表示,每一事件都有相应的活动例程。例程中的操作能否进行取决于一定的测试
条件,该条件一般与时间和系统状态有关,而且时间条件需优先考虑。确定事件的发生时间可以事先确定,因此其活动例程的测试条件只与时间有关;条件事件的例程测试条件与系统状态有关。一个实体可以有几个活动例程;协同活动的活动例程只归属于参与的一个实体(一般是永久实体)。在活动扫描法中,除设置系统仿真时钟外,每一实体都带有标志自身时钟值的时间元Ctime-cell\时间元的取值由所属实体的下一确定事件刷新。活动周期法的基本思想是,用各实体时间元的最小值推进仿真时钟;将仿真钟推进到一个新的时刻点后,按优先序执行可激活实体的活动例程,使测试通过的事件得以发生并改变系统的状态和安排相关确定事件的发生时间。因此,与事件调度法中的事件例程相当,活动例程是活动扫描法的基本模型单元。活动扫描法的仿真策略:(1)初始化/置仿真的开始时间巾和结束时间圳/置实体的初始状态;[实体时间元time-cell[i]的初值;i=l,2,3[实体时间元time-cell[i]的初值;i=l,2,3•…m;加是实体个数。置仿真时钟TIME=to如果转(4);否则,转(6)o活动例程扫描forj=l,n(优先序从高到低)例程令隶属于实体Ei;ifQtime-cell[i]^TIME或A/的测试条件D[j]=True}then执行活动例程旳;若令中安排了E•的下一事件,贝!I刷新time-cell[i];退出当前循环,重新开始扫描;endifendfor推进仿真时钟TIME=min{time-cell[i]/time-cell[i]>TIME};仿真结束。从上面算法可知,活动扫描法要求在某一仿真时刻点上对所有当前Oime・c€ll[i]=TIME)可能发生的和过去abnzell[i]<TIME)应该发生的事件反复进行扫描,直到确认已没有可能发生的事件才推进仿真时钟。
在活动扫描法仿真中,每一活动例程都有两部分构成:◊在活动扫描法仿真中,每一活动例程都有两部分构成:◊探测头:活动例程中所带的测试条件;◊动作序列:活动例程所要完成的具体操作,只有在测试通过后才被执行。总控程序的主要任务是进行时间扫描,以确定仿真时在事件调度法中,时间扫描是通过事件表完成的;而在活动扫描法中,时间扫描是通过时间元time-cell完成的。time-cell是各个实体的地方时钟,而系统仿真时钟是全局时钟。time-cell的取值方法有两种:◊绝对时间法:将time-cell的时钟值设定在相应实体的确定事件发生时刻;◊相对时间法:将time-cell的时钟值设定在相应实体确定事件发生的时间间隔上。不管釆用哪一种时间扫描方法,进行活动例程扫描时time-ce〃的取值小于0的永久实体,表明其处于等待状态。上面给出的仿真策略釆用的是绝对时间法。与事件调度法不同,这里进行时间扫描时也可釆用表的方法,但表处理的结果仅仅是求出最小时间值,而不需确定当前要发生的事件。因此,time-cell表中只存放时间值即可,与事件表相比,其结构与处理过程要简单得多。举例(例4.2):售票窗口服务系统剧院雇佣一名售票员同时负责剧票的窗口销售和对电话问询者的咨询服务:总控程序采用上图结构,设计活动例程的逻辑流程图。有6个活动例程需要考虑:A/:购票者到达;A2:开始为购票者服务;43:购票者服务结束;A4:电话到达;Ast通话开始;A6i通话结束。
上面的6个活动例程分属3个实体,幻是购票者的活动例程,如是电话问询者的活动例程,缶、43、45、4。均为售票员的活动例程。相应的逻辑流程图如下:总控程序调用购票者逬入队列产生下次到达时间安排下次到达事件-返回总控程序A/活动例程(购票者到达)总控程序调用E1事件例程(购票者到达)总控程序调用总控程序调用4343活动例程(购票者服务结束)总控程序调用总控程序调用4343活动例程(购票者服务结束)购票者离去闲置售票员返回总控程序总控程序调用总控程序调用--19・总控程序调用总控程序调用--19・E2事件例程(购票者服务结束)总控程序调用总控程序调用如活动例程(电话到达)如活动例程(电话到达)总控程序调用总控程序调用如活动例程(电话到达)如活动例程(电话到达)逬入电话队列产生下次电话到达时间安排下次电话到达事件返回总控程序总控程序调用总控程序调用--19・总控程序调用总控程序调用--19・E3事件例程(电话到达事件)总控程序调用总控程序调用AoAo活动例程(通话结束)总控程序调用总控程序调用AoAo活动例程(通话结束)问询者离去闲置售票员返回总控程序总控程序调用总控程序调用总控程序调用总控程序调用--19・E”事件例程(通话结束)占用售票员将购票者移出队列产生售票服务时间安排服务结束事件返回总控程序A2活动例程(开始为购票者服务)Nc人5活动例程(通话开始)--19・--19・⑶三段扫描法一一改进的活动扫描仿真策略。由于活动扫描法将确定事件和条件事件的活动例程同等对待,都要通过反复扫描来执行,因此效率较低。1963年,Tocher借鉴事件调度法的某些思想,对活动扫描法进行了改进,提出了三段扫描法。三段扫描法兼有活动扫描法简单和事件调度法高效的优点,因此被广泛釆用,并逐步取代了最初的活动扫描法。同活动扫描法一样,三段扫描法的基本模型单元也是活动例程。但是在三段扫描法中,活动例程被分为两类:B类活动例程一一描述确定事件的活动例程,在某一排定时刻必然会被执行。也称确定活动例程。C类活动例程一一描述条件事件的活动例程,在协同活动开始(满足状态条件)或满足其它特定条件时被执行。也称条件活动例程或合作活动例程。显然,B类活动例程像事件扫描法中的事件例程一样可以在排定时刻直接执行,只有C类活动例程才需扫描执行。
基于这种思想,给出三段扫描法的仿真策略如下:(1)初始化置仿真的开始时间巾和结束时间圳I实体的初始状态;置初始B类活动例程及其调用时间仏(2)111置仿真的开始时间巾和结束时间圳I实体的初始状态;置初始B类活动例程及其调用时间仏(2)111[仿真时钟TIME%(3)确定当前时钟"ME下调用的B类活动例程儿,T2,•…/2。(4) B类例程调用如果"ME®,按优先序执行{caseA/ofAl:执行活动例程Al;An:执行活动例程An。endcase}否则,转(7);(5)C类例程扫描forj=l,m(优先序从高到低)if(令的测试条件D[j]=True)then执行活动例程A八{退出当前循环,重新开始扫描};endifendfor推进仿真时钟"ME到下一最早B类例程调用时刻;转(3);(7)仿真结束。B类例程的调用时刻在B类和C类活动例程中均可安排。具体实现时,将活动扫描法中的确定事件(B类活动)的活动例程中的探测头去掉,其余不变。执行机制见下图:(开始)时间扫描执行当前B类活动例程、扫描C类活动例程NoNoB段((开始)时间扫描执行当前B类活动例程、扫描C类活动例程NoNoB段(B类活动例程调用):/执行A阶段确定的当前发生的B类活动例程。有动作执行仿真结束YesC段(C类活动例程扫描): ]/反复测试各个C类活动的探测头;完成通过测试的活动序列。 .厂(时间扫描): '“确定下一事件发生时刻及在该时刻执行的B类活动例程;/将仿真钟推进到下一事件发生时刻。三段扫描法仿真执行机制--19・--19・实体记录格式:时间元time-cell下一次B类活动例程(C类活动带有标志)上一次活动例程(C类活动带有标志)时间扫描时:◊先检査实体记录格式中的第二项内容是否是B类,若是则比较其时间元的值,从中找到一个最小值作为仿真时钟的未来值;◊然后产生一个时间元值等于仿真时钟未来值的实体名表,表中的实体在下一事件发生时必定要改变状态;◊在将仿真时钟推进到其未来值时,总控程序将实体名表与实体记录相匹配,调用当前时刻执行的B类活动例程;◊B段调用完成后,再对C类活动例程进行扫描。4.4离散事件系统仿真结果分析根据仿真运行试验的基本方法和统计分析方法的不同,离散事件系统仿真运行方式可以分为两种:终态仿真(终止型仿真、暂态仿真):是指仿真试验在某个持续时间段上运行,在终态仿真中,系统的初始状态必须加以明确指定,同时必须指定仿真结束时刻或给出仿真停止条件。终态仿真结果对初始状态有明显的依赖性。仿真运行时间长度是事先确定的。稳态仿真:是通过系统仿真试验,希望得到系统性能指标在系统达到稳态时的估计值,因而常常需要很长一段时间的运行,结束条件一般是充分长的仿真试验时间(针对仿真钟而言),或充分多的观测样本,或系统的稳态判据为真。稳态仿真试验结果一般应与初始状态无关。4.4.1终态仿真结果的分析4・4丄1重复运行法(复演法)一般情况下,终态仿真采用的是重复运行法(复演法)。所谓重复运行法,是指选用不同的独立随机数序列,采用相同的参数、初始条件以及相同的采样次数n对系统重复仿真运行。利用重复运行仿真方法,可以得到独立的仿真结果。对一个终态仿真系统,由于每次运行是相互独立的,因此可以认为每次运行的结果Xg,2,…,n)是独立同分布的随机变量,从而可以釆用经典的统计方法对结果进行分析。由于每次仿真运行的初始条件和参数是相同的,每次仿真运行的结果也必然是相近的,相互之间的偏差不会很大,因此可以假设仿间的偏差不会很大,因此可以假设仿真结果X"X2,…,X"是服从正态分布的随机变量。随机变量X的期望值E(X)的估计值“为y]s2(n)/n其中:S\n)=fj[X(n)-Xj]2/(n-l)j=iJa为置a为置I信度水平。根据中心极限定理,产生的样本点&越多,即重复运行的次数越多,&则越接近于正态分布,此重复运行的次数不能太小。举例:机床加工零件仿真系统,仿真目的是分析机床的利用率P和一个工作日内机床每加工一个零件的平均时间⑵。在相同的初始条件下经过4次独立的仿真运行,得出结果如下表:运行序号机床利用率。零件加工时间Q10.8083.74min20.8754.53min30.7983.84min40.8423.98min计算机床利用率。的95%置信区间和零件加工平均时间的95%的置信区间。计算机床利用率的点估计值"=0.83075戸的方差为:S2(n)=(0.035)2E表得『3,0.025=3.18,故:p=p±Go()254s\n)7n=0.83075±3.18x0.035故。的95%置信区间为:
0.716</?<0.945类似地计算零件平均加工时间的点估计值:=4.02min@的方差为:S2(/i)=(0.35)2故cd-co±4()()25Js'(n)/比=4.02±3.18x0.1760的95%置信区间为:3.46 4.584.4.1.2序贯程序法在上面的重复分析法中,通过规定次数的仿真运行可以得到随机变量取值的置信区间,置信区间的长度与仿真次数〃的平方根成反比。显然,若要缩小置信区间的长度就必然增加仿真次数这样就产生了另一个方面的问】显然,若要缩小置信区间的长度就必然增加仿真次数这样就产生了另一个方面的问】即在一定的精度要求下,规定仿真结果的置信区间,设法确定能够达到精度要求的仿真次数。这样做可以对置信区间的长度进行控制,避免做出不适用的结论。如上例中的机床利用率的置信区间为0.716<p<0.945,可能就太大了。由上面的公式可知,样本X的100(1-⑵%置信区间的半长为:式中:S为样本的标准差,〃为重复运行次数。设给定以准确度的临界值G即限定置信区间的长度为[乂-£,乂+刃,并给定置信度(1-⑵,为达到此要求,需要取足够大的仿真运行次数巾,使之满足假设仿真已运行了%)次(山》2),为了满足置信区间半长的临界值,必须选择重复运行次数〃,使得初始仿真次数他至少大于2,最好取4或5。可推出:n的解就是满足上式的最小整数。注:这里假定斤次独立重复运行结果总体方差b?的估计值52(n)随着增加斤次运行没有显著变化,因此可用f的总体方差代替。在上例中,如果希望计算出的机床利用率以0.95的概率落入半长为0.04的区间,可按上述方法计算得出运行次数为8。
实际上,利用斤。次仿真运行的方差S"%)来代替斤次仿真运行的方差,会使计算得出的斤值偏大。为了消除这种影响,一般釆用序贯程序法,步骤为:(1)预定独立仿真运行的初始次数%>2,置H=/20独立运行,7次;(1)(2)计算该料次运行的样本X|,X2,・・・,X”以及相应的52(h);若卩"则得到置信度为若卩"则得到置信度为(1-Q)的满足精度要求的置信区间[乂何-0,乂何+0],从而确定了相应的仿真次数卅;(4)否责令刃=,7+1,进行仿真得到样本值X曲;(4)(5) 返回步骤(2)o(6)采用序贯程序法,对上例进行计算,得到的仿真次数为6,比用解析法得到的次数要少。(原(6)因?)4.4.2稳态仿真结果的分析除了终态仿真研究之外,还需要研究一次仿真运行时间很长的仿真,研究系统的稳态性能。在仿真运行过程中,每相隔一段时间即可获得一个观测值X,从而可以得到一组自相关时间随机序列的采样值厶岭,…,打,其稳态平均值定义为1nv=lim—Vy;—n如果v的极值存在,则"与仿真的初始条件无关。稳态仿真结果分析的主要目的仍是对系统状态变量的估计及使估计值达到给定精度要求时停止。4・4・2・1批均值法一般来说,对于稳态仿真若采用类似重复运行法那样利用全部观测值进行估计,得到的估计值产与实际的稳态值Y之间会有偏差b=Y-Y这里b称为在点估计9中的偏移。这个偏移是由人为的或任意的初始条件所引起,我们希望得到一个无偏估计,至少也希望偏移值b相对于Y值尽可能地小。如果在点估计中有明显的偏移,采用大量的重复运行来减少点估计的变化范围,可能会导致错误的置信区间。这是因为偏移不受重复次数的影响,增加重复运行次数只会使置信区间围绕错误的估计点Y+b变短,而不会围绕Y变短。为了降低偏移的影响,一般采用批均值法,基本思想是:仿真运行时间足够长,可以得到足够多的观测值冷约,…,诊,将Z
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026-2027学年郑州市金水区一年级上册语文期末质量检测卷含答案
- 胸腔镜下肺癌手术术中高发风险因素分析及护理对策
- 轧光(轧花)机挡车工改进考核试卷含答案
- 船舶特大型起重机驾驶工岗前认知考核试卷含答案
- 玻纤拉丝工诚信道德模拟考核试卷含答案
- 孤残儿童护理员岗前安全知识宣贯考核试卷含答案
- 手工火焰切割工安全检查知识考核试卷含答案
- 高频等离子工记录能力考核试卷含答案
- 手工织毯工岗后模拟考核试卷含答案
- 糖尿病足的中医护理
- 《护理管理培训》课件
- 2026重庆国际物流枢纽园区建设有限责任公司及子公司招聘19人笔试模拟试题及答案解析
- 《纪检监察机关派驻机构工作规则》 测试竞赛考试练习题库(附答案)
- 检察官遴选考试真题及答案解析
- 江苏省无锡市梅村高级中学2025-2026学年高一上学期10月阶段检测物理试卷(含答案)
- 2026秋新北师大版数学六年级上册教学课件:数学好玩 五子棋
- TCNAS 59-2026 《患者自控镇痛护理》全面解读
- 生物酶制剂生产流程技术指南
- 2026及未来5年中国全自动商用咖啡机市场数据分析及竞争策略研究报告
- 超声评估胆囊腺肌症
- TSG08-2026《特种设备使用管理规则》解析
评论
0/150
提交评论