离散事件仿真方法

针对生产系统的性能评估分析问题,排队论、Petri网等数学方法有明显的局限性,离散事件仿真方法则可以克服这些困难。一般来说,仿真方法的最大优点是可以较为全面精确的模拟实际对象,不需要太多的抽象和假设,即便是系统结构较为复杂时,分析效率也不会明显降低。本文介绍几种常见的离散事件系统仿真方法。

「 1. 事件调度法 」

事件是离散事件系统的基本概念,事件的发生引起系统状态的改变。事件调度法(event scheduling)以事件为分析系统的基本单位,通过定义事件、事件发生的时间顺序及其系统状态的变化,并以事件来驱动仿真模型的运行。仿真模型中的事件存放于“事件表”中,通过时间控制模块从事件表中选择最先发生的事件;重置仿真时钟,并调用与该事件对应的事件处理模块;更新系统状态,决定未来将要发生的事件;当前事件结束后,返回时间控制模块;重复事件的选择与处理,直到仿真结束。事件调度法的逻辑如图1所示。

「 2. 活动扫描法 」

活动扫描法(activity scanning)以“活动”作为分析系统的基本单元,这里的活动等同于对象的“操作”。该方法认为仿真系统的运行是由若干活动构成,每一活动对应一个活动处理模块,处理与活动相关的事件。一个活动可以由“开始(激发)”和“结束(终止)”两个事件表示,每一事件都有相应的活动处理模块。处理中的操作能否进行取决于时间及系统状态。一个对象可以有几个活动处理模块。每一个进入系统的临时对象都处于某种活动的状态。活动的激发与终止都会形成新的事件。活动扫描法不断扫描系统的每个对象,检验哪些活动可以激发,哪些活动继续保持,哪些活动可以终止。活动扫描法的基本思想:用各对象时间元的最小值推进仿真时钟;按优先级执行激活活动处理,使测试通过的事件得以发生;改变系统状态,确定相关事件的发生时间。事件调度法的逻辑如图2所示。

「 3. 进程交互法 」

事件调度法和活动扫描法的基本模型单元分别是事件处理和活动处理。它们都针对具体事件而建立,处理相对独立。进程交互法(process interaction)的基本模型单元是进程(process)。进程由和某类对象相关的事件及若干操作组成,一个进程描述了它所包括的事件及操作间的相互逻辑关系和时序关系。通过为每个临时对象建立一个进程,来反映它从产生开始到结束为止的全部活动。进程交互法试图把活动扫描法和事件调度法方法两者的优点结合起来。这种方法认为系统的行为可由一组进程来描述,一个进程是对一系列连续的事件和活动的描述。每个临时对象都有自己的一个进程,随着仿真的进行,相继通过这个进程的各个阶段。在任意一个时刻,系统中可能存在许多临时对象,这些对象都按照自己的进程流动,可能处在进程的不同阶段。各进程之间相互作用,引起临时对象的延迟和移动,从而构成了系统的动态变化过程。在仿真过程中,每个临时对象沿着自己的进程向前移动,直到由于某种原因移动被中止,从而产生一定的延迟;一旦满足某些条件,延迟被解除,则临时对象继续向前移动,而且尽可能移过多个阶段,引发延迟一般有两种情况:

(1)无条件延迟(如进入服务)。在这种情况下, 临时对象在产生延迟的这个阶段一直保持到预先确定的延迟时间结束,然后继续移动。

(2)条件延迟(如排队等待)。在这种情况下,延迟的持续时间依赖于其它进程的状态。因此,临时对象在这一阶段要一直保持到其它条件允许它移动为止。

进程交互法中,仿真时钟的控制程序采用两张事件表,其一是当前事件表(current events list, CEL)它包含了从当前时间点开始有资格执行的事件记录,但是该事件是否发生的条件尚未判断。其二是将来事件表(future events list, FEL),它包含了在将来某个仿真时刻发生事件的事件记录。每一个事件记录中包括事件的若干属性,其中必有一个属性说明该事件在进程中所处位置的指针。

进程交互法仿真过程主要分为3个阶段,如图3所示。

(1)未来事件表FEL扫描:扫描FEL中的记录,确定具有最早下次激活事件的对象,仿真时钟推进到这一时间。

(2)移动记录:把激活时间小于等于当前仿真时钟时间的所有记录从FEL移到CEL中。

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

「 4. 三阶段法 」

三阶段法(three-phase approach)是一种折中的方法,它认为系统中有些活动可以直接安排,而有些活动不能直接安排。执行程序跟踪可以直接安排的活动,然后扫描其它的活动,以寻找当前安排的活动执行的逻辑结果。在三阶段法中活动被分成两种类型:

B活动(book – keeping Activities)——表示可被预先安排的无条件事件(持续时间为0的活动),每当它们的预定发生时间到达时,就可直接执行;

C活动(conditional activities)——是条件活动或协同活动。它们的执行或依赖于不同的对象的协同作用或要满足仿真中某些特定的条件。

如图4所示,三阶段法的执行分成三个阶段,一般称为A、B、C三个阶段。当仿真运行时,执行程序不断循环执行A、B、C三个阶段。

(1)A阶段(时间扫描):预先知道B活动(无条件事件)的下次发生时间,可以确定紧迫事件的发生时间,推进仿真时钟到这一时间;

(2)B阶段(执行B活动):只执行在A阶段确定的已到达发生时间的B活动(无条件事件);

(3)C阶段(扫描C活动):依次检查每个C活动,并执行条件满足的活动。这一阶段,除了扫描的只是C活动以外,操作过程和活动扫描法是一样的。

三阶段法也是事件调度法和活动扫描法的综合改进,是离散事件仿真软件主要采用的方法。

引自:《生产系统建模与仿真》(作者:朱海平)

 

注:除标明原创外,均为网友或机构投稿分享,如有宣发需求请联系dongxizhiku@163.com。