第四章 离散事件系统仿真方法1

d

第4章 离散事件系统仿真方法

4.1离散事件系统仿真一般概念

4.1.1 一般概念

离散事件系统：系统中的状态只在离散时间点上发生变化，而且这些离散时间点一般是不确定的。

系统状态是离散变化的，而引发状态变化的事件是随机发生的，因此这类系统的模型很难用数学方程来描述。

随着系统科学和管理科学的不断发展及其在军事、航空航天、CIMS和国民经济各领域中应用的不断深入，逐步形成一些与连续系统不同的建模方法：流程图和网络图。

离散事件系统建模与仿真的基本概念： ⑴ 实体：

是描述系统的三（四）要素之一，是系统中可单独辨识和刻画的构成要素。如：工厂中的机器，商店中的服务员，生产线上的工件，道路上的车辆等。从仿真角度看，实际系统就是由相互间存在一定关系的实体集合组成的，实体间的相互联系和作用产生系统特定的行为。

实体可分为两大类：临时实体和永久实体

临时实体——在系统中只存在一段时间的实体。一般是按一定规律有系统外部到达系统，在系统中接受永久实体的作用，按照一定的流程通过系统，最后离开系统。临时实体存在一段后即自行消失，消失有时是指实体从屋里意义上退出了系统的边界或自身不存在了；有时仅是逻辑意义上的取消，意味着不必再予以考虑。如：进入商店的顾客、路口的车辆、生产线上的工件、进入防空火力网的飞机、停车场的汽车等。

永久实体——永久驻留在系统中的实体。是系统产生功能的必要条件。系统要对临时实体产生作用，就必须有永久实体的活动，也就

d

必须有永久实体。可以说临时实体与永久实体共同完成了某项活动，永久实体作为活动的资源而被占用，如：理发店中的理发员、生产线上的加工装配机械、路口的信号灯等。

属性和行为相同或相近的实体可以用类来描述，这样可以简化系统的组成和关系。如：理发店服务系统可以看成是由“服务员”和“顾客”两类实体组成的，两类实体之间存在服务与被服务的关系。

⑵ 属性

是实体特征的描述，一般是系统所拥有的全部特征的一个子集，用特征参数或变量表示。选用那些参数作为实体的属性与建模目的有关，一般按以下原则：

便于实体分类：如按理发店顾客的性别； 便于实体行为的描述：如飞机的速度

便于排队规则的确定：如生产线上待处理工件的优先级水平。 ⑶ 活动

实体在一段时间内持续进行的操作或过程。活动所占用的时间段称为忙期，忙期可以是定时的或随机的。

建模中，一般要给出忙期的计算公式或概率分布函数，保证一个实体一进入某一活动，其忙期就可以计算或从概率分布函数中抽取得到，如“服务员”对“顾客”的服务，其忙期就可以从指数分布函数抽样得到（服务时间）。很多情况下的活动是由几个实体协同完成的。

⑷ 状态

对实体活动的特征状况划分，其表征量称为状态变量。在理发中，顾客有等待服务、接受服务等状态，服务员有忙、闲等状态。

活动总是与一个或几个实体的状态相对应。状态可作为动态属性进行描述。

⑸ 事件

导致系统状态产生变化的瞬间操作或行为。从某种意义上说，系

d

统是由事件来驱动的。

事件发生的时刻称为事件点。不关心事件所代表的操作和行为意义时，事件与事件点是同义语。

若事件发生是有前提的，则称为条件事件。

活动、状态和事件三者间关系：时间的发生导致状态的变化，实体的活动可以与一定的状态相对应，因此可以用事件来标识活动的开始和结束。见下图：

活动、状态、事件及进程

⑹ 进程

一组按发生时间排列的事件/活动序列称为一个进程（见上图）。 ⑺ 队列

处于等待状态的实体序列。一般按新到的实体排在队尾的次序组成。在建模中，队列可作为一种状态或特殊实体对待。

⑻ 仿真钟

用于表示仿真时间的变化。其推进方法与仿真策略有关。 ⑼ 统计计数器

离散事件系统的有些变化是随机的，一次仿真运行得到的状态变

d

化过程只不过是随机过程的一次取样。如果进行另一次独立的仿真运行所得到的状态变化过程可能完全是另一种情况。一般只在统计意义下有参考价值！一般在仿真中需要一个统计计数部件，以便统计系统中的有关变量。如：服务系统中的平均队长、顾客的平均等待时间、服务员的利用率等。

4.1.2 离散事件系统仿真的一般步骤

基本步骤与连续系统仿真类似，但有些特殊问题： ⑴ 系统建模

系统模型一般用流程图或网络图的方式来描述。反映了临时实体在系统内部历经的过程、永久实体对临时实体的作用以及它们之间的逻辑关系。

⑵ 确定仿真算法

包括两方面内容，一是如何产生所需求的随机变量；二是采用怎样的方法进行仿真，即仿真策略。

⑶ 建立仿真模型

根据已经确定的仿真算法，进行变量定义、流程图确定，完成仿真程序实现。

⑷ 仿真结果分析

离散事件系统固有的随机性，每次仿真计算结果仅仅是随机变量的一次取样，要运行多次，并采用适当的方法进行分析。

4.2离散事件系统建模方法

4.2.1 实体流图法

4.2.1.1 实体流程图

采用与计算机程序流程图相类似的图示符号和原理，建立表示临时实体产生、在系统中流动、接受永久实体“服务”以及消失等过程

d

的流程图。

借助实体流程图，可以表示事件、状态变化及实体间相互作用的逻辑关系。

计算机程序框图——思想和编制方法已广为接受，实体流程图的编制方法虽然简单，但对离散事件系统的描述却比较全面，应用比较普遍。

用实体流图方法建模没有特别的技巧和理论可言：

一是要对实际系统的工作过程有深刻的理解和认识；二是要将事件、状态变化、活动和队列等概念贯穿于建模过程中。

常用符号： 菱形框——判断;

矩形框——事件、状态、活动等中间过程; 圆端矩形框——开始和结束； 箭头线——逻辑关系。 具体建模思路：

（1） 确定组成系统的实体及属性，将队列作为一种特殊的实体来

考虑。

（2） 分析各种实体的状态和活动，及其相互间的影响。队列实体

的状态是队列的长度。

（3） 考虑有哪些事情（事件）导致了活动的开始或结束，或者可

以作为活动开始或结束的标志，以确定引起实体状态变化的事件，并合并条件事件。

（4） 分析各种事件发生时，实体状态的变化规律。

（5） 在一定的服务流程下，分析与队列实体有关的特殊操作（如

换队等）。

（6） 通过以上分析，以临时实体的流动为主线，用约定的图示符

d

号画出被仿真系统的实体流程图。

（7） 给出模型参数的取值、参变量的计算方法及属性描述变量的

取值方法。属性描述变量，如顾客到达时间、服务时间等，可以取一个固定值（由某一计算公式取值）；也可以是一个随机变量，要给出其分布函数。

（8） 给出队列的排队规则。由多个队列存在时，还应给出其服务

规则（包括队列的优先序、换队规则等）

4.2.1.2 举例

例4.1：理发店服务系统

小理发店，只有一个理发员。顾客来到理发店后，如果有人正在理发，就坐在一旁等候。理发员按先来先理的原则为每一个顾客服务，而且只要有顾客就不停歇。建模目的是研究在假定顾客到达间隔和理发所花的时间服从一定概率分布时，考察理发员的忙闲情况。

分析：

错误!

d

理发店服务系统实体流图

本问题只有一个队列，顾客不会因排队人数太多而离去，因此队列规则很简单，没有特殊的队列操作。

需给出的模型属性变量：

顾客的到达时间（随机变量），从分布函数中获取； 理发员为一个顾客理发所需的服务时间（随机变量），从分布函数中获取；

队列的排队规则：先到先服务（FIFO）,每到一位顾客就排在队尾，服务员先为排在队首的顾客服务。

d

例4.2：售票窗口服务系统

剧院雇佣一名售票员同时负责剧票的窗口销售和对电话问询者的咨询服务：

窗口服务比电话服务有更高的优先级。

问询者打来电话由电话系统存储后，按先来先服务的原则一一予以答复。

建模目的：研究售票员的忙闲率。

此例中有两类实体同时流动，可能出现资源冲突。 分析：

d

售票窗口服务系统实体流图

模型属性变量：

购票者到达时间，电话问询者到达时间，售票服务时间，电话服务时间。

排队规则：

窗口购票者和电话问询者分别排队；优先进行窗口服务。 注：实体流图是为描述实体流动和相互间逻辑关系而绘制的，与

d

计算机程序框图不同，与编程实现的要求还有较大距离。

4.2.1.3 模型的人工运行

模型人工运行——建立实体流图模型后，选取有代表性的例子将流图全部走一遍。

人工运行要求遍历流程图的各个分支和实体的各种可能状态，在时间逐步变化的动态条件下，分析事件的发生及状态的变化过程，以检查模型的组成和逻辑关系是否正确。

例4.1中，假定：

系统初始状态：包括永久实体“理发员”及特殊实体“队列”的状态。初始时刻是指仿真开始的时刻，可以对应为实际系统（理发店）开门营业的时间。此时理发员为“闲”，队列长度为“0”（空）。

模型参数及变量的取值：包括第i个顾客与第i-1个顾客到达的时间间隔Ai，以及理发员为第i个顾客的理发时间Si。一般来说，Ai。、Si均为随机变量，因根据其分布函数产生。为举例方便，取其样本值为：

A1=15，A2=32，A3=24，A4=40，A5=22，…… S1=43，S2=36，S3=34，S4=28，…… 模型的人工运行规则： 规则1——确定当前时间

运行开始时，取当前时间TIME=t0（为仿真初始时刻）。运行开始后，当前时间逐步向前推移，且递推至下一个最早发生事件的发生时刻。如果当前时间有顾客到达事件发生，转规则2；若有顾客离去事件发生，转规则3。

规则2——顾客到达事件处理

假定在时刻TIME有顾客i到达，根据实体流程图可知，如果此时理发员忙，则入队列等待，队列长度加1；否则置理发员为“忙”

d

状态，顾客开始理发，且在di=TIME+Si时刻理毕离去。

规则3——顾客离去事件处理

假定在时刻TIME有顾客i离去，根据实体流程图可知，如果此时队列长度为0，则置理发员为“闲”状态；否则，队列中排在队首的一名顾客开始理发，队列长度减1，并且该顾客在di=TIME+Si时刻理毕离去。

上述规则体现了“事件调度法”的基本思想。如果还存在其它事件或复杂的服务流程时，则需增加相应的规则。

理发店模型人工运行结果

A1=15，A2=32，A3=24，A4=40，A5=22，…… S1=43，S2=36，S3=34，S4=28，……

4.2.2 活动周期图法

4.2.2.1 活动周期图

实体流图法中：实体的行为模式在有限的几种情况之间周而复始地变化，表现出一定的生命周期形式。

理发员实体：状态在“忙”和“闲”之间不断变化，“忙”意味着理发员与顾客正在协同完成“理发”活动。

d

顾客实体：群体行为是在“到达”、“等待”、“理发”和“离去”之间周而复始变化。

活动周期图法正是基于这种思想逐步形成的一种离散事件系统建模方法。

以直观的方式显示了实体的状态变化历程和各实体之间的交互作用关系，便于理解分析。可以充分反映各类实体的行为模式，并将系统的状态变化以“个体”状态变化的集合方式表示出来，因此可以更好地表达众多实体的并发活动和实体之间的协同。但是，它只描述了系统的稳态，而没有表示系统的瞬态，即活动的开始和结束事件。

活动周期图：

实体状态：静寂（Dead）、激活（Active）

静寂状态

激活状态

活动周期法基本图符

状态之间：用箭头连接，不同的实体用不同的线型，表示各种实体的变化历程。

激活状态：通常是实体的活动，模型中活动的忙期可采用随机抽样的方法事先加以确定；

静寂状态：通常表示无活动发生，是实体等待参加某一活动的状态，其持续时间在模型中无法事先确定，取决于有关活动的发生时刻与忙期。

每一类实体的生命周期都有一系列状态组成。随着时间的推移和实体间的相互作用，各个实体从一个状态变化到另一个状态，形成一

d

个变化过程。

活动周期图建模过程如下：

（1） 确定组成系统的实体及属性：确定组成系统的永久实体和临

时实体，队列不作为实体考虑。

（2） 分别画出各实体的活动周期图：要以实际过程为依据，队列

作为排队等待状态来处理；实体流程图中作事件看待的某些操作或行为，要拓展为活动来处理。活动周期图服从两个原则：

交替原则：静寂状态和活动状态必须交替出现。如果实际系统中某一活动完成后其后续活动就立即开始，则后续活动为直联活动。为使直联活动与其前置活动的连接仍符合交替原则，规定这两个活动之间存在一个虚拟的队列。

闭合原则：每类实体的活动周期图都必须是闭合的，其中临时实体的活动周期图表示一个或单位实体从产生到消失的循环过程，而永久实体的活动周期图则表示一个或几个实体被占用和被释放的循环往复过程。

（3） 将实体的活动周期图联结成系统的活动周期图：以各实体之

间的协同活动为纽带，将各种实体的活动周期图合并在一起。 （4） 增添必需的虚拟实体：在活动周期图中，当一个活动的所有

前置静寂状态均取非零值（队列不空）时，该活动才有可能发生。利用这一特性，可以增添某些必要的虚拟实体，并假定它们与另外的实体协同完成某项活动。利用这种办法可以为实体活动的发生加上某种附加条件，从而实现“隔时发生”的建模效果。

（5） 标明活动发生的约束条件和占用资源的数量：

活动是否可以发生的判断条件，这些条件应是用活动周期图示符号无法或不便表达的。活动发生的条件一般为某种表达式，标在活动框的旁边。

d

永久实体在参加一次协同活动时被占用和活动完成时释放的数量。协同活动发生时占用/释放永久实体（资源）的数量标在相应箭头线的旁边（带有+/-符号），数量为一时不标。

（6） 给出模型参数的取值、参变量的计算方法及属性描述变量的

取值方法，并给出排队规则和服务规则。

4.2.2.2 举例

举例（例4.2）：售票窗口服务系统

剧院雇佣一名售票员同时负责剧票的窗口销售和对电话问询者的咨询服务：

窗口服务比电话服务有更高的优先级。

问询者打来电话由电话系统存储后按先来先服务的原则一一予以答复。

建模目的：研究售票员的忙闲率。

此例中有两类实体同时流动，可能出现资源冲突。

d

售票员活动周期图

d

电话 = 0 电话问询者的活动周期图

d

电话 = 0 售票窗口服务系统活动周期图

活动周期图在描述两类以上临时实体资源竞争问题时较简练、清晰。

模型属性变量：

购票者到达时间，电话问询者到达时间，售票服务时间，电话服务时间。

排队规则：

窗口购票者和电话问询者分别排队；优先进行窗口服务。

d

4.2.2.3 模型的人工运行

确定初始状态（符合被仿真系统运行前的实际情况）： 标记临时实体在初始状态下的位置。一般情况下，它们处于生命周期起始点所对应的静寂状态，如例题中的“外部”状态；有时部分实体可能处在“排队等待”等中间状态。

标记永久实体在初始状态下的位置。一般情况下，它们处于“等待”或“空闲”等静寂状态。

确定运行规则：

规则1——活动的发生与执行

按照服务优先级，依次检查临时实体每一项活动的前置状态（均为静寂状态）和标在活动上方的发生条件，判断活动是否可以开始。满足以下两个条件的活动可以开始：

（1） 活动的所有前置状态中均有实体停留，且各类永久实体的

数量超过或等于相应箭头线上所标明的占用量。 （2） 活动发生的约束条件已经满足。

如果某项活动可以开始，则在相应的活动框中标出正在进行该活动的临时实体标号；

对于哪些被确定可以开始的活动，需根据各项活动的忙期分别确定其终止时间（等于当前时间加上活动忙期），并将终止时间标在活动框外。 规则2——确定当前时间

检查所有活动的终止时间，从中选择最小者作为当前时间 规则3——活动的完成

从所有已发生的活动中，检出终止时间等于当前时间的临时实体，删掉其标在活动框外的终止时间。

运行过程中要注意标注：实体的状态、时间等。

d

在对从系统“外部”到达的临时实体标注时要注意：

“外部”状态中一般有无数个临时实体存在，因此无法一一标注，可采用特殊符号ω进行标注，代表有很多临时实体存在于系统 “外部”。

从前置活动进入到“外部”状态的临时实体不必再行标注。

4.3离散事件系统仿真方法

离散事件仿真要解决两个问题：随机变量的产生和仿真策略。

4.3.1 随机变量的产生

离散事件系统仿真过程中要用到许多服从不同分布类型及参数的随机变量。

产生随机变量的基础是产生[0，1]区间上均匀分布的随机变量——也称为伪随机数发生器。其他各类分布，如正态分布、γ分布、β分布、泊松分布等，都可以用某种方法通过对均匀分布进行某种变换来实现。

4.3.1.1 随机数发生器

严格地说，计算机中的随机数发生器不是概率意义下的真正随机数，只能称为伪随机数，原因是无论哪一种随机数发生器都采用递推算法。

但如果算法选择合适，得到的数据通过统计检验后能具有较好的统计特性（如均匀性、独立性等）。这种伪随机数可以用于仿真。

随机数发生器（线性同余发生器）： 应用较广泛，递推公式为：

本文来源：https://www.bwwdw.com/article/qpki.html