离散事件模拟

Published: by Creative Commons Licence

离散事件系统

什么是离散事件系统

离散事件系统是指系统状态在某些随机时间点上发生离散变化的系统，因而离散事件系统一般都具有随机性，系统的状态变量往往是离散变化的。

离散事件系统的组成

离散事件系统一般由以下六个基本要素组成：

  1. 实体。实体一般指系统所研究的对象。用系统术语说，它是系统边界内的对象，系统中流动的或活动的元素都可以称为实体。
  2. 事件。事件就是引起系统状态发生变化的行为。从某种意义上说，离散系统是由事件来驱动的。
  3. 活动。活动在离散事件系统中，通常用来表示两个可以区分的事件之间的过程，标志着系统状态的转移。
  4. 进程。进程由若干个有序事件及若干个有序活动组成，一个进程描述了它所包括的事件及活动之间的逻辑关系及时序关系。
  5. 仿真时钟。它用来表示仿真时问的变化。仿真时钟与实际时钟的区别在于：前者是离散的，而后者是连续的。由于仿真实质上是对系统状态在一定时间序列下的动态描述，因此，仿真时钟一般是仿真的主要自变量。
  6. 统计计数器。离散事件动态系统的状态随着事件的不断发生呈现出动态变化，这种变化是随机的，某一次仿真运行得到的状态变化过程只不过是随机过程中的一次取样，只有经过多次统计得到的仿真输出统计结果才有意义。

银行业务的模拟程序

在日常生活中，我们经常会遇到许多为了维护社会正常秩序而需要排队的情景。这样一类活动的模拟程序通常需要用到队列和线性表之类的数据结构，因此是队列的典型应用例子之一。下面将介绍一个银行业务的模拟程序。

问题

假设某银行有4个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需要在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正空闲，则可上千办理业务；反之，若4个窗口均有客户所占，他便会排在人数最少的队伍后面。现在需要编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。

解决思路

为了计算平均时间，我们需要掌握每个客户到达银行和离开银行这两个时刻，后者减去前者即为每个客户在银行的逗留时间。

所有客户逗留时间的总和被一天内进入银行的客户数除便是所求的平均时间。

几个概念

事件：称客户到达银行和离开银行这两个时刻发生的事情为“事件”。

事件模拟驱动：如果整个模拟程序按事件发生的先后顺序进行处理，这样一种模拟程序称作“事件驱动模拟”。

算法

void Bank_Simulation(int CloseTime) {
	// 银行业务模拟，统计一天内客户在银行逗留的平均时间
	OpenForDay();									// 初始化
	while(MoreEvent) {
		EventDrived(OccurTime, EventType);			// 事件驱动
		switch(EventType) {
			case 'A': CustomerArrived(); break;		// 处理客户到达事件
			case 'D': CustomerDeparture(); break;	// 处理客户离开事件
			default: Invalid();
		}
	}
	CloseForDay();
}

模拟程序的实现

一、模拟程序中需要的数据结构及其操作

由于程序驱动是按事件发生时可的先后顺序进行，则事件表应是有序表，其主要操作是插入和删除操作。

另一种数据结构是表示客户排队的队列。

由于前面假设银行有4个窗口，因此程序中需要4个队列，队列中有关客户的主要信息是客户到达的时刻和客户办理事务所需的事件。 每个队列中的队头客户即为正在窗口办理事务的客户，他办完事务离开队列的时刻就是即将发生的客户离开事件的时刻。(对每个队头客户都存在一个将要驱动的客户离开事件)

因此，在任何时刻即将发生的事件只有下列5中可能：

  1. 新的客户到达
  2. 1号窗口客户离开
  3. 2号窗口客户离开
  4. 3号窗口客户离开
  5. 4号窗口客户离开

由以上分析，在这个模拟程序中，只需要两种数据结构：有序链表和队列。下面是他们的数据元素类型定义：

typedef struct {	// 事件发生时刻
	int OccurTime;	// 事件类型：0表示到达事件，1至4表示四个窗口的离开事件
	int NType;		// 事件类型：有序链表LinkList的数据元素类型
} Event, ElemType;

typedef LinkList EventList	// 事件链表类型，定义为有序链表

typedef struct {
	int ArrivalTime;	// 到达时刻
	int Duration;		// 办理事务所需事件
} QElemtype;			// 队列的数据元素类型
二、主要操作步骤的实现

操作步骤一：对新客户到达时间的处理

因为客户到达的时刻以及其办理事务所需时间都是随机的，在模拟程序中可用随机数来代替。

在客户到达事件发生时需先产生两个随机数：

  1. 此时刻到达的客户办理事务所需时间durtime
  2. 下一客户将到达的时刻为intertime

假设当前事件发生的时刻为occurtime，则下一个客户到达事件发生的时刻为occurtime + intertime.

由此应产生一个新的客户到达事件插入事件表；刚到达的客户插入到当前所含元素最少的队列中；若该队列在插入前为空，则还应产生一个客户离开事件插入事件表。

操作步骤二：客户离开事件的处理

  • 首先计算该客户在银行逗留的时间；
  • 然后从队列中删除该客户后查看队列是否为空，若不空则设定一个新的队头客户离开事件。