基于优先级队列的事件驱动模拟(Event-Driven Simulation)

1. 引言：

    利用模拟来研究一个不少于两个(n>=2)出纳窗口的银行中每个客户到达(Arrival)银行和离开(Departue)银行的情况。
一般每个出纳窗口在某一时刻值能接待一位客户，在客户很多时需在每个窗口顺序排队。如果客户到达银行时某个窗口
正空闲，客户就可以立刻到该窗口办理业务；如果所有窗口都不空闲，则客户要排在最短的队列后面。我们需要通过计算
每位客户的平均等待时间和每位出纳员的繁忙度(时间百分比)的出服务的效率。

2. 设计过程：

(1) 模拟设计
      
1> 在运行过程中，模拟将跟踪各个客户的到达和离去。

       设客户到达时间为time(Arrival), 离去时间为time(Depature),窗口的服务时间ServiceTime，则有：

       time(Depature) = time(Arrival) + ServiceTime

       考虑另一种情况，设两个出纳窗口都不空闲。客户必须排在某一个队列中等待服务。模拟可以让客户选择出纳窗口
，并在窗口更新"下次空闲时间"标牌。银行模拟的关键部分是两个客户事件：到达事件Arrival和离开事件Depature。假设
客户的等待时间为WaitTime,则有：

       time(Depature) = time(Arrival) + WaitTime + ServiceTime

       当一位客户到达银行时，就会产生一个到达事件Arrival。
       当一位客户检查并选定出纳窗口后，就将定义一个离开事件来描述该客户什么时候离开。

事件类代码如下：

package boke.eventdriven;

/**
 * TODO 事件类型
 * 
 * @author 毛正吉
 * 
 */
public enum EventType {
	// 到达和离开事件
	Arrival, Departure

}

--------------------------------

package boke.eventdriven;

/**
 * TODO 事件类
 * 
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.05.24
 * 
 */
public class Event {
	private int time; // 客户到达 | 离开时间
	EventType eType; // 事件类型
	private int customerID; // 客户编号，编号为1,2,3...
	private int tellerID; // 出纳窗口编号，编号为1,2,3，...
	private int waitTime; // 客户等待时间
	private int serviceTime; // 客户服务时间

	/**
	 * 构造方法
	 * 
	 * @param _time
	 * @param _eType
	 * @param _customerID
	 * @param _tellerID
	 * @param _waitTime
	 * @param _serviceTime
	 */
	public Event(int _time, EventType _eType, int _customerID, int _tellerID,
			int _waitTime, int _serviceTime) {
		time = _time;
		eType = _eType;
		customerID = _customerID;
		tellerID = _tellerID;
		waitTime = _waitTime;
		serviceTime = _serviceTime;
	}

	/** ************ getter和setter方法 ************* */
	public int getTime() {
		return time;
	}

	public void setTime(int time) {
		this.time = time;
	}

	public EventType getEType() {
		return eType;
	}

	public void setEType(EventType type) {
		eType = type;
	}

	public int getCustomerID() {
		return customerID;
	}

	public void setCustomerID(int customerID) {
		this.customerID = customerID;
	}

	public int getTellerID() {
		return tellerID;
	}

	public void setTellerID(int tellerID) {
		this.tellerID = tellerID;
	}

	public int getWaitTime() {
		return waitTime;
	}

	public void setWaitTime(int waitTime) {
		this.waitTime = waitTime;
	}

	public int getServiceTime() {
		return serviceTime;
	}

	public void setServiceTime(int serviceTime) {
		this.serviceTime = serviceTime;
	}

}

2> 在模拟中，还要统计每一出纳窗口信息：
   处理过的客户总数；
   客户的总等待时间；
   总的服务时间；
   什么时候出纳窗口空闲
------------------------------

package boke.eventdriven;

/**
 * TODO 出纳窗口类
 * 
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.05.24
 * 
 */
public class TellerStatus {
	public int finishService; // 什么时候出纳窗口空闲
	public int totalCustomerCount; // 服务过的客户总数
	public int totalCustomerWait; // 客户总的等待时间
	public int totalService; // 总的服务时间
}

3> 模拟为每一位客户生成一个到达事件和离开事件。所有的事件都以时间为标记，并放入一个优先级队列中。
在优先级队列中优先权最高的事件是时间标记最早的事件。这样一种表结构使得我们能够以一个事件递增的顺序
从队列中移去客户的到达和离开事件。
----------------------------------------

package boke.eventdriven;

/**
 * TODO 优先级队列
 * 
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.05.24
 * 
 */
public class PQueue {
	/**
	 * 
	 * @param args
	 * @throws PQueueException
	 */
	public static void main(String[] args) throws PQueueException {
		PQueue pq = new PQueue();
		for (int i = 0; i <= 10; i++) {
			Event e = new Event(i, EventType.Arrival, i, i, i, i);
			pq.enPQueue(e);
		}

		System.out.println(pq.length());

		while (!pq.isEmpty()) {
			Event e = pq.delPQueue();
			System.out.println(e.getEType() + " " + e.getTime());
		}

		System.out.println(pq.length());
	}

	private static final int MAX_EVENT_SIZE = 1000; // 队列最大长度
	private Event[] events; // 队列元素
	private int count; // 队列长度

	public PQueue() {
		events = new Event[MAX_EVENT_SIZE];
		count = 0;
	}

	/**
	 * 入队
	 * 
	 * @param evt
	 * @throws PQueueException
	 */
	public void enPQueue(Event evt) throws PQueueException {
		if (!isFull()) {
			events[count] = evt;
			count++;
		} else {
			throw new PQueueException("PQueue is full!");
		}
	}

	/**
	 * 出队:标记时间最短的事件有最大的优先权
	 * 
	 * @return
	 * @throws PQueueException
	 */
	public Event delPQueue() throws PQueueException {
		if (!isEmpty()) {
			int min = events[0].getTime();
			int minindex = 0;

			for (int i = 1; i < count; i++) {
				if (events[i].getTime() < min) {
					min = events[i].getTime();
					minindex = i;
				}
			}

			Event et = events[minindex];
			events[minindex] = events[count - 1];
			count--;
			return et;
		} else {
			throw new PQueueException("PQueue is empty!");
		}
	}

	/**
	 * 队列置空
	 */
	public void makeEmpey() {
		count = 0;
	}

	/**
	 * 队列是否为空
	 */
	public boolean isEmpty() {
		return count == 0;
	}

	/**
	 * 队列是否为满
	 */
	public boolean isFull() {
		return count == MAX_EVENT_SIZE;
	}

	/**
	 * 队列的长度
	 */
	public int length() {
		return count;
	}
}

-------------------------------
package boke.eventdriven;

/**
 * TODO 优先级队列异常类
 * 
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.05.24
 * 
 */
public class PQueueException extends Exception {
	public PQueueException() {
		super("PQueueException");
	}

	public PQueueException(String msg) {
		super(msg);
	}
}

---------------------------------

2. 模拟建立、运行

1> 下一次客户何时到达？当前客户的服务时间有多长？

    银行模拟将使用一个随机数发生器来生成。该发生器假定在一定的取值范围内取任何值的概率都是相等的。
如果当前的到达时间发生在T分钟，下一次到达时间将随机地发生在T+arriveLow 到 T+arriveHigh的范围内，客户
需要的服务时间则在serviceLow到serviceHigh的范围内。
 
    看函数nextArrivalTime() 和 getServiceTime()

2> 在模拟过程中，客户要得到空闲时间最小的出纳窗口?

    看函数nextAvailableTeller()

3> 模拟运行

    看函数runSimulation()

-----------------------------

package boke.eventdriven;

import java.util.Random;

/**
 * TODO 模拟 类
 * 
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.05.24
 * 
 */
public class Simulation {
	private int simulationLength; // 模拟的时间长度
	private int numTellers; // 出纳窗口个数
	private int nextCustomer; // 下一位客户的编号
	private int arrivalLow, arrivalHigh; // 下一次到达的时间范围
	private int serviceLow, serviceHigh; // 服务的时间范围
	private TellerStatus[] tstat = new TellerStatus[11]; // 最多10个出纳窗口
	private PQueue pq = new PQueue(); // 优先级队列
	private Random rnd = new Random(); // 用于到达和服务的时间

	/**
	 * 构造方法
	 * 
	 * @param simulationLength
	 * @param numTellers
	 * @param arrivalLow
	 * @param arrivalHigh
	 * @param serviceLow
	 * @param serviceHigh
	 * @throws PQueueException
	 */
	public Simulation(int simulationLength, int numTellers, int arrivalLow,
			int arrivalHigh, int serviceLow, int serviceHigh)
			throws PQueueException {
		Event firstEvent = new Event(0, EventType.Arrival, 1, 0, 0, 0); // 第一个到达事件
		for (int i = 0; i <= 10; i++) { // 初始化出纳窗口信息
			tstat[i] = new TellerStatus();
			tstat[i].finishService = 0;
			tstat[i].totalService = 0;
			tstat[i].totalCustomerWait = 0;
			tstat[i].totalCustomerCount = 0;
		}
		this.nextCustomer = 1; // 下一位客户的编号从1开始

		this.simulationLength = simulationLength; // 输入的模拟时间长度(以分钟计算)
		this.numTellers = numTellers; // 输入的出纳窗口个数
		this.arrivalLow = arrivalLow; // 输入下一次到达的时间范围
		this.arrivalHigh = arrivalHigh;
		this.serviceLow = serviceLow; // 输入服务的时间范围
		this.serviceHigh = serviceHigh;
		pq.enPQueue(firstEvent);
	}

	/**
	 * 确定一下次到达的随机时间
	 * 
	 * @return
	 */
	private int nextArrivalTime() {
		return arrivalLow + rnd.nextInt((arrivalHigh - arrivalLow + 1));
	}

	/**
	 * 确定客户服务的随机时间
	 * 
	 * @return
	 */
	private int getServiceTime() {
		return serviceLow + rnd.nextInt((serviceHigh - serviceLow + 1));
	}

	/**
	 * 产生一个可用的出纳窗口
	 * 
	 * @return
	 */
	private int nextAvailableTeller() {
		int minfinish = simulationLength; // 初始时假定所有的出纳窗口在下班时关闭
		int minfinishindex = rnd.nextInt(numTellers) + 1; // 给下班前到达但在下班后得到服务的客户提供一个随机的出纳窗口编号

		for (int i = 1; i <= numTellers; i++) { // 找一个可用的窗口
			if (tstat[i].finishService < minfinish) { // 寻找窗口空闲时间最小者
				minfinish = tstat[i].finishService;
				minfinishindex = i;
			}
		}
		return minfinishindex; // 返回窗口空闲时间最小者的窗口号码
	}

	/**
	 * 模拟的主函数
	 * 
	 * @throws PQueueException
	 */
	public void runSimulation() throws PQueueException {
		while (!pq.isEmpty()) {
			// 出队
			Event e = pq.delPQueue();

			/* ###################################### */
			System.out.println("客户" + e.getCustomerID() + "在时间" + e.getTime()
					+ "分" + e.getEType());
			/* ###################################### */
			System.out.println("######################################");
			System.out.println("CustomerID = " + e.getCustomerID());
			System.out.println("TellerID = " + e.getTellerID());
			System.out.println("WaitTime = " + e.getWaitTime());
			System.out.println("ServiceTime = " + e.getServiceTime());
			System.out.println("######################################");

			// 整个模拟的时间长度
			simulationLength = (e.getTime() <= simulationLength) ? simulationLength
					: e.getTime();

			// 1.到达 (Arrival)
			// (1)当前到达的客户负责生成下一个到达事件
			int nextTime = e.getTime() + nextArrivalTime();// 计算下次到达时间

			if (nextTime > simulationLength) { // 超出模拟时间长度，什么也不做
				continue;
			} else { // 产生下一个客户到达事件，并放入优先级队列
				nextCustomer++;
				Event newEvent = new Event(nextTime, EventType.Arrival,
						nextCustomer, 0, 0, 0);
				pq.enPQueue(newEvent);

				/* ###################################### */
				System.out.print("客户" + e.getCustomerID() + "为" + "客户"
						+ newEvent.getCustomerID() + "在第" + newEvent.getTime()
						+ "分钟到达产生一个到达事件,");
			}

			int serviceTime = getServiceTime(); // 客户所需服务时间
			int tellerID = nextAvailableTeller(); // 可为客户服务的出纳窗口
			int waitTime = 0; // 客户等待时间

			if (tstat[tellerID].finishService == 0) {
				tstat[tellerID].finishService = e.getTime();
			} else {
				waitTime = tstat[tellerID].finishService - e.getTime();
			}

			// (2)更新出纳窗口的各项信息
			tstat[tellerID].finishService += serviceTime;
			tstat[tellerID].totalCustomerCount++;
			tstat[tellerID].totalCustomerWait += waitTime;
			tstat[tellerID].totalService += serviceTime;

			// (3) 定义离开事件，并把它放入优先级队列中
			Event newEvent = new Event(tstat[tellerID].finishService,
					EventType.Departure, e.getCustomerID(), tellerID, waitTime,
					serviceTime);
			pq.enPQueue(newEvent);

			// 2.离开
			tellerID = e.getTellerID();
			if (e.getTime() == tstat[tellerID].finishService) {
				tstat[tellerID].finishService = 0;
			}

			/* ###################################### */
			System.out.println("并为自己在第" + newEvent.getTime() + "分钟"
					+ newEvent.getEType() + "产生一个离开事件");

			/* ###################################### */
			System.out.println("######################################");
			System.out.println("CustomerID = " + newEvent.getCustomerID());
			System.out.println("TellerID = " + newEvent.getTellerID());
			System.out.println("WaitTime = " + newEvent.getWaitTime());
			System.out.println("ServiceTime = " + newEvent.getServiceTime());
			System.out.println("######################################");
		}
	}

	/**
	 * 模拟输出函数
	 */
	public void printSimulationResults() {
		int cumCustomers = 0; // 客户总数
		int cumWait = 0; // 客户总的等待时间
		for (int i = 1; i <= numTellers; i++) {
			cumCustomers += tstat[i].totalCustomerCount;
			cumWait += tstat[i].totalCustomerWait;
		}

		System.out.println();
		System.out
				.println("**************************** Simulation Summary ******************************");
		System.out.println("模拟时间长度 : " + this.simulationLength + "分钟");
		System.out.println("客户总数 ：" + cumCustomers);

		// 计算平均等待时间
		float avgCustWait = (float) ((cumWait) / cumCustomers + 0.5);
		System.out.println("平均等待时间 : " + avgCustWait + "分钟");

		// 打印各个出纳窗口信息
		for (int i = 1; i <= numTellers; i++) {
			// 窗口平均服务时间
			float tellerWork = tstat[i].totalService / simulationLength;
			// 服务时间百分比
			float tellerWorkPercent = (float) (tellerWork * 100.0 + 0.5);
			System.out.println("出纳窗口" + i + ": 服务时间百分比 : " + tellerWorkPercent);
		}

	}
}

3. 模拟的输出：

package boke.eventdriven;

/**
 * TODO 模拟 类客户端应用
 * 
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.05.24
 * 
 */
public class SimulationApp {

	/**
	 * @param args
	 * @throws PQueueException
	 */
	public static void main(String[] args) throws PQueueException {
		// 模拟参数给出如下
		int simulationLength = 30; // 输入的模拟时间长度(以分钟计算)
		int numTellers = 2; // 输入的出纳窗口个数
		int arrivalLow = 6; // 输入下一次到达的时间范围
		int arrivalHigh = 10;
		int serviceLow = 18; // 输入服务的时间范围
		int serviceHigh = 20;
		Simulation s = new Simulation(simulationLength, numTellers, arrivalLow,
				arrivalHigh, serviceLow, serviceHigh);

		// 运行模拟程序
		s.runSimulation();

		// 输出结果
		s.printSimulationResults();
	}

}

-----------------------------------------
客户1在时间0分Arrival
######################################
CustomerID = 1
TellerID = 0
WaitTime = 0
ServiceTime = 0
######################################
客户1为客户2在第7分钟到达产生一个到达事件,并为自己在第18分钟Departure产生一个离开事件
######################################
CustomerID = 1
TellerID = 1
WaitTime = 0
ServiceTime = 18
######################################
客户2在时间7分Arrival
######################################
CustomerID = 2
TellerID = 0
WaitTime = 0
ServiceTime = 0
######################################
客户2为客户3在第14分钟到达产生一个到达事件,并为自己在第25分钟Departure产生一个离开事件
######################################
CustomerID = 2
TellerID = 2
WaitTime = 0
ServiceTime = 18
######################################
客户3在时间14分Arrival
######################################
CustomerID = 3
TellerID = 0
WaitTime = 0
ServiceTime = 0
######################################
客户3为客户4在第23分钟到达产生一个到达事件,并为自己在第38分钟Departure产生一个离开事件
######################################
CustomerID = 3
TellerID = 1
WaitTime = 4
ServiceTime = 20
######################################
客户1在时间18分Departure
######################################
CustomerID = 1
TellerID = 1
WaitTime = 0
ServiceTime = 18
######################################
客户4在时间23分Arrival
######################################
CustomerID = 4
TellerID = 0
WaitTime = 0
ServiceTime = 0
######################################
客户2在时间25分Departure
######################################
CustomerID = 2
TellerID = 2
WaitTime = 0
ServiceTime = 18
######################################
客户3在时间38分Departure
######################################
CustomerID = 3
TellerID = 1
WaitTime = 4
ServiceTime = 20
######################################
客户4在时间45分Departure
######################################
CustomerID = 4
TellerID = 2
WaitTime = 0
ServiceTime = 22
######################################

**************************** Simulation Summary ******************************
模拟时间长度 : 45分钟
客户总数 ：4
平均等待时间 : 2.5分钟
出纳窗口1: 服务时间百分比 : 0.5
出纳窗口2: 服务时间百分比 : 0.5