Introduction

Simulation techniques are frequently applied to evaluate the performance of almost any kind of system. Highways, computer networks, CPU's, grocery stores, and car washes can all be modeled and analyzed using simulation. What they all have in common is, they offer some resource or service for which customers compete.

In this project you will develop a generic software framework for simulating the performance of such systems. The technique your software will support is discrete event-oriented simulation of queuing systems.

There is a concise Wikipedia entry on discrete event simulation that describes its various components and operation. Most of what is written there is also independently written here. It may however serve as a valuable alternative explanation.

Event-oriented systems feature at least two kinds of events: arrivals and departures. Using the car wash example, an arrival event occurs when a vehicle pulls off the street into the car wash facility and a departure event occurs when a vehicle leaves the facility after being cleaned. Events are considered to be instantaneous; that is, they do not consume any time. That simplifies the simulation.

For simplicity, let's consider a single-bay car wash. What happens when you enter a car wash facility? If the bay is in use (busy) you join the line (queue) - or form one if there is no one already in line. If the bay is not in use (idle), you pull into the bay and begin using it. When a vehicle departs and there is a line, the first vehicle in line pulls into the bay and it remains busy. Otherwise, the bay becomes idle. Pretty straightforward.

When evaluating the performance of such a system, one considers several statistics, such as:

• Utilization of the bay - percentage of time it is busy
• Time that vehicles spend in the bay
• Time that vehicles spend in line
• Length of the line
• and so on...

The Simulation Mechanism

Event-oriented simulation models require software components to model not only the entities of the system - vehicles and bays - but also components to manage the events that control the simulation. Here is a typical mechanism.

Any simulation model requires a clock to record the passage of time. A simple numeric variable will do. For simplicity, we will use an int variable initialized to time 0 (zero).

From the perspective of the clock, events occur instantaneously at some known point in the future. Again for simplicity, we will assume that events occur one at a time at a predetermined future time. Such events can be managed using a data structure called a Future Events Queue (FEQ). This is a queue-based list of events ordered by their scheduled time. The first event on the list will be the next to occur.

In general there are two kinds of events in the FEQ: arrivals and departures.

There must be an algorithm to carry out the actions of the mechanism at simulation time. This is called the Events Loop because of its repeated operations. Here is a pseudo-code description.

Initialize clock to zero
Create SimulationEnd event and place in FEQ
Create Arrival event and place in FEQ
While (the FEQ is not empty)  {
	remove the first event from the FEQ
	update the clock to that event's time
	process the event
}

Notice that when the FEQ becomes empty, the event loop terminates and the simulation is over. How are events generated and placed into the FEQ? Great question!

Before entering the Event Loop, the mechanism must create the first Arrival event and place it into the FEQ. This is called "priming the pump." Once in the loop, the "process the event" step includes creating another event and adding it to the FEQ. You will see details later, but in essence when an Arrival event is processed it creates the next Arrival and when a Departure event is processed it creates the next Departure (assuming the waiting line is not empty).

Event Processing

This section focuses on the Event Loop step "process the event." Arrival and departure algorithms are given as pseudo-code.

Create the next Arrival Event and place it in the FEQ
Customer requests use of the Server

Release the customer from the Server

Sounds pretty simple, right? It is, at that level. But requesting and releasing the server are not trivial operations. Here is pseudo-code for each:

Add the Customer to the Server's waiting line
If (the Server is idle)  {
	remove the Customer from the waiting line
	assign the Customer to the Server
	set the Server status to busy
	create a Departure Event and place it in the FEQ
}

If (the Server's waiting line is empty)  {
	set the Server status to idle
} else {
	remove the first Customer from the Server's waiting line
	assign that Customer to the Server
	create a Departure Event and place it in the FEQ
}

Ordering Events in the FEQ

Random Events

Another feature of many discrete event simulation models is they are non-deterministic. That is, the model has elements of random behavior. The most common of these are random inter-arrival times and random service times. That is, customer arrivals occur at random intervals, and service times vary randomly from one customer to the next.

In the event processing algorithms above, the action of creating a new Arrival Event includes determining at what future time the event will occur. This is done by generating a random value and adding it to the current clock value. Since this is done at the time of an arrival, the random value represents the inter-arrival time. Similarly, when an Arrival Event or a Departure Event creates a new Departure Event, the time at which that departure will occur is determined by adding a random value to the current clock value. Since the random value is generated at the start of service, it represents the service time required.

Although we can generate random values using the Math.random() method, for simulations it is better to create an object of the Random class (package java.util) for each random variable. In this case, create one Random object for inter-arrival times and a second one for service times.

Creating a different Random object for each random variable gives us much greater control over simulation behavior. In particular, it allows us to control the sequence of random values. We have the option of giving a Random object an initial or seed value. If we do so, we can guarantee that it will produce the same sequence (stream) of values every time we run the program. This is important for reproducibilty, which allows us to determine the effect of changing one factor (such as average inter-arrival time) while keeping all other factors the same.

Software-based random number generators (RNG) are more accurately called pseudo-random number generators. The values are not truly random. In fact, each value in a sequence produced by such a generator is a function of the value that preceded it in the sequence. For instance, if an RNG generates the value 23 followed by the value 678, and later on it produces 23 again then a cycle has been established and it must be followed by 678 again! Therefore, giving the RNG a fixed seed value guarantees the same sequence every time we run the program.

Random variables such as inter-arrival times follow different probabilty distributions. The default behavior of an RNG is to produce values that vary according to a uniform distribution. This means that given a range of possible integer values, every value in the range has an equal probability of being produced. The Random method nextInt() generates uniformly-distributed random values. This is a good starting point, but is not particulary realistic.

The Random method nextInt() produces values from the entire integer range. That's a pretty wide range. Fortunately, it is overloaded with nextInt(int n) to produce values in the range from 0 (inclusive) to n (exclusive). If the low end of the desired range is greater than zero, we need to add the low end to the random value. For example: We have a Random object called randu and we want values from the range 10 (inclusive) to 25(exclusive). We get these from the expression 10 + randu.nextInt(15).

Statistics

The Statistic class you created for Project 1 and the WeightedStatistic class you created for Exercise 2 will used in this project! You can use yours, but I will provide these when they are needed.

Classes for this project

This project will require a number of Java classes and interfaces.

• Simulation -- A class to control the simulation.
• Event -- An interface to represent any simulation event. It will extend Comparable
• AbstractEvent -- An abstract class to define many of the methods for events.
• ArrivalEvent -- A class to represent a customer arrival event. It will extend AbstractEvent and implement Comparable
• DepartureEvent -- A class to represent a customer departure event. It will extend AbstractEvent and implement Comparable
• SimulationReportEvent -- A class for the event that triggers generation of a simulation report. It will extend AbstractEvent and implement Comparable
• SimulationEndEvent -- A class for the event that signals the completion of the simulation. It will extend AbstractEvent and implement Comparable
• Customer -- A class to represent customers in the system. In a snapshot of a single server system, zero or more customers are waiting in line and at most one customer is being served.
• Server -- A class to represent servers in the system. A server is either busy or idle.
• WaitingLine -- A class to represent the server's waiting line (queue) in the system.
• Statistic -- A class to gather and report statistics such as waiting time. See Project 1.
• WeightedStatistic -- A class to gather and report weighted statistics such as queue length. See Exercise 2.

Phases

A complex project like this needs to be developed in phases. I am constructing this project to permit you to develop it incrementally. Not all phases are initially linked here because I will tweak the project as it progresses. Due dates for unlinked phases are tentative.