离散事件系统的仿真模型设计与优化

离散事件系统是指受事件驱动、系统状态跳跃式变化的动态系统,系统的迁移发生在一串离散事件点上。这种系统往往是随机的,具有复杂的变化关系,难以用常规的微分方程、差分方程等方程模型来描述,一般只能用流程图或网络图描述,应用理论分析方法难以得到解析解,甚至无法解决,仿真技术为解决这类问题提供了有效的手段。

离散事件动态系统(Discrete Event Dynamic System,DEDS)是美国哈佛大学何毓琦(Y.C.HO)教授于1980年前后提出的一个学科分支,其主要是用于描述和解决一系列人造系统的问题,例如,通信系统、交通系统、制造系统、计算机系统、服务系统以及军事指挥系统等。近年来的研究从各种角度以不同的模型和方法提出和解决了一些不同类型的问题,形成了多种方法体系,并出现了多种形式的DEDS模型设计方法。

(一)离散事件系统仿真的基本思想

离散事件系统是系统的状态仅在离散的时间点上发生变化的系统,而且这些离散时间点一般是不确定的。这类系统中引起状态变化的原因是事件,通常状态变化与事件的发生是一一对应的。事件的发生没有持续性,在一个时间点瞬间完成,事件发生的时间点是离散的,因而这类系统称为离散事件系统。混凝土运输设备与拌和楼之间的关系是离散事件系统的一个例子(见图6-3-1),因为状态变量(即混凝土运输设备状态)仅当顾客到达或顾客服务完成时才改变,且顾客到达的时间与服务的时间是随机的。在这类系统的分析、设计、管理与控制中,人们常常需要知道系统的行为以及影响这些行为的因素。对少数相对简单的系统,其行为可通过解析法来获得,但对复杂的大系统,目前只能求助于计算机仿真技术。针对离散事件系统的仿真,称为离散事件系统仿真。

图6-3-1　混凝土施工过程示意图

离散事件系统仿真与建立系统模型的方式密切相关。对于比较复杂的大型离散事件系统,若以整个系统为单位,直接建立其总体模型,往往比较困难,不易取得成功。但是如果把系统分成若干个相对独立又相互作用的实体,首先建立这些实体的局部模型,然后按实体间的相互联系,连接局部模型来组成总体模型,则容易取得成功,也容易形成通用的建模步骤与方法,方便建模者使用。这样做符合人们处理大而复杂问题的一般方式:分而治之。这种通过连接局部模型而获得的系统总体模型,称为结构模型。

虽然离散事件系统的类型众多,但可以抽象出一些公共的概念来描述其结构模型。目前成熟且通用的基本概念包括实体、属性、事件、活动和进程等。

1.实体(Entity)

构成系统的各种成分称为实体,用系统论的术语,它是系统边界内的对象。实体可分为临时实体与永久实体两大类。在系统中只存在一段时间的实体称为临时实体,这类实体由系统外部到达系统,通过系统,最后离开系统。永久驻留在系统中的实体称为永久实体,只要系统处于活动状态,这些实体就存在。临时实体常具有主动性,又称为主动成分,而永久实体往往是被动的,又称为被动成分。在混凝土浇筑系统中,运输设备是临时实体(主动成分),拌和楼是永久实体(被动成分)。临时实体按一定规律不断地到达,在永久实体作用下通过系统,最后离开系统,如此整个系统呈现动态变化的过程。

2.属性(Attribute)

实体由它的属性来描述,属性用来反映实体的某些性质。例如,运输设备是一个实体,型号、载重量、到达时间和服务时间等是它的属性。对一个客观实体,其属性很多,在仿真建模中,只需用到与研究目的有关的一部分,也只需对这一部分进行描述。

3.状态(State)

在某一确定时间,系统的状态是系统中所有实体的属性的集合。

4.事件(Event)

事件是引起系统状态发生变化的行为,它是在某一时间点上的瞬间行为。离散事件系统可以看作是由事件驱动的。在上述例子中,可以定义“设备到达”为一类事件。因为由于设备到达,系统的状态中,拌和楼的状态可能由闲变忙,或者队列状态即排队的设备数发生变化。一个设备接受的服务完毕后离开系统的行为也可以定义为一类事件—— “设备离开”,此事件使拌和楼的状态由忙变闲。

5.活动(Activity)

实体在两个事件之间保持某一状态的持续过程称为活动。活动的开始与结束都是由事件引起的。

6.进程(Process)

进程由和某类实体相关的事件及若干活动组成。一个进程描述了它所包括的事件及活动间的相互逻辑关系和时序关系。

事件、活动与进程三者之间的关系可用图6-3-2描述。

(二)离散事件系统仿真模型的描述

离散事件系统的结构模型着重于描述构成系统的实体及实体间的交互,侧重于面向用户的视角。而建立系统的仿真模型需要将结构模型映射到计算机上,并需要考虑仿真的需要,如程序事件、数据统计等,通常与计算机的特征相关。由于传统的计算机均是串行计算的,而系统结构模型中各实体的活动是并行的,因此基于串行计算机建立离散事件系统仿真模型的主要任务是将并行的结构模型串行化计算,这个过程主要要用到事件表与仿真钟两个概念。

图6-3-2　事件、活动与进程的关系

1.事件表(Event List)

事件表是为仿真服务的,它记录系统中每一个将要发生的事件类型、发生时间以及与该事件相关的参数。在一个系统中,往往有许多类事件,而事件的发生一般与某类实体相联系,某一事件的发生还可能引起另一事件的发生,或者成为另一事件发生的条件等。为了实现对系统中事件的管理以及按时间顺序处理事件,必须在仿真模型中建立事件表。仿真模型是依赖事件来驱动的,系统中除了有固有事件(又称为系统事件)外,还有程序事件,它用于控制仿真的进行。

2.仿真钟(Simulation Clock)

仿真钟用于表示仿真时间的变化,作为仿真过程的时序控制。它是系统运行时间在仿真过程中的表示,而不是计算机执行仿真程序的时间长度。在连续系统仿真中,将连续模型离散化为仿真模型时,仿真时间的变化由仿真步长确定,可以是定步长,也可以是变步长。离散事件动态系统的状态本来只在离散时间点上发生变化,因而不需要进行离散化处理,而按以下两种基本推进方式推进:

(1)事件单位推进(Event-Unit Advance)。因为离散事件系统中两个相邻事件之间系统状态不会发生变化,所以仿真钟可以跨过这些“不活动”的时间段,从一个事件发生时刻直接推进到下一个事件发生的时刻。即每次推进都从事件表中选择相对当前时刻最早发生的事件,将仿真钟推进到该事件发生时刻,这样仿真时钟的推进呈现跳跃性。由于事件的产生具有随机性,仿真时钟的推进速度也是随机的。

(2)时间单位推进(Time-Unit Advance)。这种方法选择适当的时间单位(必须足够小)作为固定的时间推进步长。每推进一步,都作如下处理:首先检查事件表内有无事件在该步内发生,若没有,则仿真钟再向前推进一个时间单位;若有,则处理事件,相应地改变系统的状态,然后再向前推进一个时间单位。如在该步内有几个事件发生,则用户必须规定处理各类事件的优先顺序。

事件单位推进方式效率较高,一般情况下可节省时间,目前被广泛采用,但其设计和实现比较复杂。

时间单位推进将每步内发生的所有事件都当作该步末端时刻发生的,使得一些时间间隔较小的事件表现为同步发生,这样会产生较大的偏差。为了克服这个缺点,需要将时间单位取得足够小,这又使计算量增大。基于时间单位推进方法的特点,它主要用于系统事件发生时间具有较强周期性的模型。

连续系统仿真的目的是要得到状态变量的动态变化过程,并由此分析系统的性能。离散事件系统的状态随着事件的不断产生呈现出动态变化过程,但仿真的主要目的不是要获得状态的变化情况。因为离散事件系统通常含有随机的因素,因而状态的变化具有随机性。一次仿真运行获得的状态变化过程只是随机过程的一次采样,系统的性能计算只有在统计意义下才有参考价值。

在单服务台系统中,由于设备到达的时间间隔具有随机性,拌和楼为每一个设备服务的时间长度也是随机的,因而在某一时刻,各次仿真运行时设备排队的队长或拌和楼的忙闲情况是不确定的。从分析系统的角度来看,感兴趣的可能是系统的平均队长,顾客的平均等待时间或服务员的利用率。为了获得这样的统计性信息,在仿真模型中,需要有一个统计计数部件,以便统计系统中的有关变量。

离散事件系统仿真的程序,从其功能结构的角度来看,通常包含以下几个部分:

(1)系统状态变量:用于记录系统在不同时刻的状态。

(2)时钟变量:用于记录当前时刻的仿真时间值。

(3)事件表:按时间顺序记录仿真过程中将要发生的事件,即当前时刻以后的事件。

(4)统计计数器:用于记录有关仿真过程中系统性能的统计信息。

(5)初始化子程序:在仿真运行开始前进行初始化的子程序。

(6)时钟推进子程序:由事件表确定下一事件,然后将仿真钟推进到该事件发生时间的子程序。

(7)事件子程序:每一类事件对应有一个事件子程序,相应的事件发生时,就转入该事件子程序进行处理,更新系统的状态,产生新的事件。

(8)统计报告子程序:根据统计计数器的值计算并输出系统性能的估计值。

(9)随机数发生器:产生给定分布的随机数的一组子程序。

(10)主程序:调用时钟推进子程序,然后将控制转移到相应的事件子程序,完成仿真程序的总体控制。

(三)离散事件系统的仿真策略

离散事件系统的模型只在一些离散点上由事件改变其状态,因此离散事件模型是由事件驱动的。驱动某一模型的所有事件按其发生的时间先后构成一个序列,通常要求按时间先后顺序处理事件,而不能颠倒。离散事件系统仿真的关键是按时间顺序确定这一序列。除了初始事件,事件序列中的事件不能在仿真前事先确定,而是在仿真进行中产生的。在离散事件系统仿真中一般采用事先策划事件的方式,即在仿真系统处理任何事件之前,该事件必须已被策划。策划的主要工作是确定事件的类型与发生时间。策划好的事件存放在事件表中,当仿真时钟到达事件的产生时间时,由仿真系统处理该事件。离散事件系统仿真程序流程如图6-3-3所示。确定事件发生时间的方式有三类:

(1)直接方式。直接给定事件发生的时间点。

(2)间接方式。给出事件发生的条件,这时事件发生的时间点是条件满足的那一时刻。

(3)混合方式。既给出时间点,又给出条件,事件发生在给定时间点后条件满足的瞬间。

图6-3-3　离散事件系统仿真程序流程图

一个事件的策划一般是在处理前面的某一事件时进行的,这一处理时刻也称为事件的策划时间。受因果关系的约束,事件的策划时间不得迟于其发生时间,即只能策划当前和未来的事件,不能策划过去的事件。这样在离散事件仿真中,处理事件发生时,一是要按事件对系统的影响改变模型的状态,二是要策划后续的事件。用直接方式策划的事件,其发生时间可以与策划时间相同,但更常见的是在策划时间之后。后续事件的策划通常与模型新的状态有关,策划好的后续事件插入到事件表中。

离散事件模型中的各类事件可在不同层次上来组织。从前面的分析可知,系统的离散事件仿真模型由实体及其间的关系组成。实体状态的变化即为事件,同一实体在两个相继事件间所处的过程,称为实体的活动。同一实体若干活动的延续构成一个进程。因此,活动、进程都是以事件为基础构成,其粒度大于事件。从事件、活动、进程三个层次来组织事件,即构成了处理离散事件模型的三种典型处理方法:事件调度法、活动扫描法和进程交互法。在复杂系统仿真中,按进程来组织事件可以使众多的事件条理清晰,因而成为最通用的方法。

1.事件调度法(Event Scheduling)

事件调度法以事件为分析系统的基本单元,通过定义事件以及每个事件发生后对系统状态的影响,按时间顺序执行每个事件并策划新的事件来驱动模型的运行。

事件调度法的模型主要由若干事件子模块构成。所有事件均放在事件表中,模型中设有一个时间控制程序。仿真的过程是:从事件表中选择发生时间最早的事件,将仿真时钟推进到该事件发生的时间,并调用该事件的子模块处理事件、修改模型状态和策划新的事件,然后返回时间控制程序,重复这一过程,直至满足仿真结束的条件。事件调度法的算法如下:

执行仿真初始化操作

置仿真开始时间和结束时间

初始化事件表,设置初始事件(www.xing528.com)

状态初始化

置仿真时钟为仿真初始时间

WHILE(仿真时钟=结束时间)THEN

操作事件表

取出发生时间最早的事件,设类型为i

将仿真时钟推进到上一事件的发生时间

Case事件类型i

i=1:执行第1类事件处理程序

︙

i=n:执行第n类事件处理程序

EndCase

ENDWHILE

2.活动扫描法(Activity Scanning)

活动扫描法以活动为分析系统的基本单元,认为模型在运行的每一时刻都由若干活动构成。每一活动对应一个活动子例程,处理与活动相关的事件。活动与实体有关,主动成分可以主动产生活动,如排队服务系统中的设备,它的到达产生排队活动或服务活动;被动成分本身不能产生活动,只有在主动成分的作用下才产生状态变化,如排队服务系统中的拌和楼。

活动的激发与终止都是由事件引起的,每一个进入系统的主动成分都处于某种活动的状态。活动扫描法在每个事件发生时,扫描系统,检查哪些活动可以激发,哪些活动继续保持,哪些活动可以终止。活动的激发与终止都会策划新的事件。

活动的发生必须满足一定的条件,其中活动发生的时间是优先级最高的条件,即首先应判断该活动的发生时间是否满足,然后再判断其他条件。活动扫描法的算法如下:

执行仿真初始化操作

置仿真的开始时间和结束时间

设置主动成分i的仿真时钟为T [i],T [i]表示成分i的下一事件发生时间

状态初始化

置仿真时钟为仿真开始时间

WHILE(仿真时间=结束时间)THEN

扫描

FOR j=最高优先数TO 最低优先数

将优先数为j的成分置为i

IF(T [i]=仿真时间AND 成分i的活动条件为真)THEN

执行相应活动子程序

退出当前循环,重新开始扫描

ENDIF

ENDFOR

置仿真时钟=min(T [i],i=1,2,…,主动成分个数)

ENDWHIHE

3.进程交互法(Process Interaction)

进程交互法采用进程描述系统,它将模型中的主动成分历经系统时所发生的事件及活动按时间顺序进行组合,从而形成进程表。一个成分一旦进入进程,它将完成该进程的全部活动。

软件实现时,系统仿真钟的控制程序采用两张事件表:①当前事件表(Current Events List,CEL)。包含从当前时间点开始有资格执行的事件记录,但是该事件是否发生的条件(如果有)尚未判断。②将来事件表(Future Events List,FEL)。包含在将来某个仿真时刻发生的事件的事件记录。每一个事件记录中包括该事件的若干属性,其中必有一个属性,说明该事件在进程中所处位置的指针。

当仿真钟推进时,发生时间不大于仿真时钟的所有事件记录从FEL移到CEL中,然后对CEL中的每个事件记录进行扫描。对于从CEL中取出的每一个事件记录,首先判断它属于哪一个进程以及它在该进程中的位置。该事件是否发生则决定于发生条件是否为真,若为真,则发生包含该事件的活动,只要条件允许,该进程要尽可能多地连续推进,直到结束;如果条件为假或仿真钟要求停止,则退出该进程,然后对CEL 的下一事件记录进行处理。当CEL中的所有记录处理完毕后,结束对CEL 的扫描,继续推进仿真钟,即把将来事件表中最早发生的事件记录移到CEL 中。如此直到仿真结束。这种策略可用以下算法来描述:

执行仿真初始化操作

设置仿真开始时间与结束时间

设置初始化事件,并置于FEL中

将FEL中有关事件记录置于CEL中

成分状态初始化

置系统仿真时钟为仿真开始时间

WHILE(仿真时间=结束时间)THEN

扫描CEL

WHILE(CEL中最后一个记录未处理完)

WHILE(事件发生条件成立AND 当前成分未处理完)

执行该成分的活动

确定该成分的下一事件

ENDWHILE

ENDWHl LE

推进仿真钟

仿真时钟置为FEL中安排的最早时间

IF(仿真时钟=结束时间)THEN

将FEL中所有在仿真时钟指示时间发生的事件记录移到CEL中

ENDIF

ENDWHILE

由上述讨论可以看到,进程交互法既可预定事件,又可对条件求值,因而它兼有事件调度法及活动扫描法的特点。

图6-3-4为一体化建模与仿真系统结构图。

图6-3-4　一体化建模与仿真系统结构图