Implementation

This section presents the simulation of a system comprised of a single queue and server as shown in Figure . Program  declares the class Event which represents the events. There are two parts to an event, a Type (either arrival or departure), and a Time (a double).

  
Program: Event Class Definition

Since events will be put into a priority queue, the Event class is derived from the Association class which is defined in Section . An association is an ordered pair comprised of a key and a value. In the case of the Event class, the key is the time of the event and the value is the type of the event. Therefore, the events in a priority queue are prioritized by their times.

Program  defines the function which implements the discrete event simulation. This function takes two arguments. The first, eventList, is a reference to a priority queue. This priority queue is used to hold the events during the course of the simulation. The second parameter, timeLimit, specifies the total amount of time to be simulated.

  
Program: Application of Priority Queues--Discrete Event Simulation

The state of the system being simulated is represented by the two variables serverBusy and numberInQueue. The first is a Boolean value which indicates whether the server is busy. The second keeps track of the number of customers in the queue.

In addition to the state variables, there are two instances of the class ExponentialRV. The class ExponentialRV is a random number generator defined in Section . This class provides a member function called Sample which is used to sample the random number generator. I.e., every time Sample is called, a different (random) result is returned. The random values are exponentially distributed around a mean value which is specified in the constructor. For example, in this case both serviceTime and interArrivalTime produce random distributions with the mean value of 100 (lines 5-6).

It is assumed that the eventList priority queue is initially empty. The simulation begins by enqueuing a customer arrival at time zero (line 8). The while loop (lines 9-46) constitutes the main simulation loop. This loop continues as long as the eventList is not empty, i.e., as long as there is an event to be simulated

Each iteration of the simulation loop begins by dequeuing the next event in the event list (lines 11-12). If the time of that event exceeds timeLimit, the event is discarded, the eventList is purged, and the simulation is terminated. Otherwise, the simulation proceeds.

The simulation of an event depends on the type of that event. The switch statement (line 20) invokes the appropriate code for the given event. If the event is a customer arrival and the server is not busy, serverBusy is set to true and the serviceTime random number generator is sampled to determine the amount of time required to service the customer. A customer departure is scheduled at the appropriate time in the future (lines 25-27). On the other hand, if the server is already busy when the customer arrives, we add one to the numberInQueue variable (line 30).

Another customer arrival is scheduled after every customer arrival. The interArrivalTime random number generator is sampled, and the arrival is scheduled at the appropriate time in the future (lines 31-32).

If the event is a customer departure and the queue is empty, the server becomes idle (lines 35-36). When a customer departs and there are still customers in the queue, the next customer in the queue is served. Therefore, numberInQueue is decreased by one and the serviceTime random number generator is sampled to determine the amount of time required to service the next customer. A customer departure is scheduled at the appropriate time in the future (lines 39-41).

Clearly the execution of the Simulation routine given in Program  mimics the modeled system. Of course, the program given produces no output. For it to be of any practical value, the simulation program should be instrumented to allow the user to study its behavior. For example, the user may be interested in knowing statistics such as the average queue length and the average waiting time that a customer waits for service. And such instrumentation can be easily incorporated into the given framework.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.