"Bank Simulation"
DUE November 21, 1995
One of the most useful applications of queues is in simulation. A simulation program is one that attempts to model a real world situation in order to learn something about it. Each object and action in the real situation has its counterpart in the program. If the simulation is accurate, that is, if the program successfully mirrors the real world, then the result of the program should mirror the result of the actions being simulated. Thus it is possible to understand what occurs in the real world situation without actually observing its occurrence.
Consider a bank with four tellers. A customer enters the bank at a specific time tl, desiring to conduct a transaction with any teller. The transaction may be expected to take a certain period of time t2 before it is completed if a teller is free, the teller can process the customer's transaction immediately and the customer leaves the bank as soon as the transaction has been completed, at time tl+t2. The total time spent in the bank by the customer is exactly equal to the duration of the transaction, t2.
However, it is possible that none of the tellers are free; they are all servicing customers who arrived previously. In that case, there is a line waiting at each teller's window. The line for a particular teller may consist of a single personóthe one currently transacting his business with the teller, or it may be a very long line. The customer proceeds to the back; of the shortest line and waits until all the customers who precede him on the line have completed their transactions and have left the bank. At that time, he may transact his business. The customer leaves the bank at t2 time units after he has reached the front of his teller's line. In this case the time spent in the bank is t2 plus the time spent waiting on line.
Given such a system, we would like to compute the average time spent by a customer in the bank. One way of doing so is to stand in the bank doorway, ask; departing customers the time of their arrival and record the time of their departure, subtract the first from the second, and take the average over all customers. However, this would not be very practical. It would be difficult to ensure that no customer is overlooked leaving the bank. Furthermore, it is doubtful that most customers would remember the exact time of arrival.
Instead, we write a program to simulate the customer actions. Each part of the real world situation has its analog in the program. The real world action of a customer arriving is modeled by a random process. As each customer arrives, two facts are known: the time of his arrival and the duration of his transaction (since, at the time of arrival, the customer presumably knows that he wishes to do at the bank). Thus for each customer two random numbers are generated: the clock time (in hh:mm:ss format) of the customer's arrival and the amount of time (in seconds) necessary for his transaction. These input lines are ordered by increasing arrival time. We assume at least one customer.
The four lines in the bank are represented by four queues. Each node of the queues represents a customer waiting on a line, and the node at the front of a queue represents the customer currently being serviced by a teller.
Suppose that at a given instant of time the four lines each contain a specific number of customers. What can happen to alter the status of the lines? Either a new customer enters the bank, in which case one of the lines will have an additional customer, or the first customer on one of the four lines completes his transaction, in which case that line will have one less customer. Thus there are a total of five actions (a customer entering plus four cases of a customer leaving) that can change the status of the lines. Each of these five actions is called an event.
The simulation proceeds by finding the next event to occur and effecting the change in the queues that mirrors the change in the lines at the bank due to that event. To keep track of events, the program uses an event list. This list contains at most five nodes, each representing the next occurrence of one of the five types of event. Thus the event list contains one node representing the next customer arriving and four nodes representing each of the four customers at the head of a line completing his transaction and leaving the bank. Of course, it is possible that one or more of the lines in the bank are empty or that the doors of the bank have been closed for the day so that no more customers are arriving. In such cases, the event list contains fewer than five nodes.
An event node representing a customer's arrival is called an arrival node, and a node representing a departure is called a departure node. At each point in the simulation, it is necessary to know the next event to occur. For this reason, the event list is ordered by increasing time of event occurrence so that the first event node on the list represents the next event to occur.
The events are read from a text file where each line denotes arrival time (hh:mm:ss) and service Time(in sec). For Example :08:07:02 10708:07:03 6508:07:05 217...<EOF>
The first event to occur is the arrival of the first customer. The event list is therefore initialized by reading the first input line and placing an arrival node representing the first customer's arrival on the event list. Initially, of course, all four queues are empty. The simulation then proceeds as follows. The first node is removed from the event list and the changes which that event causes are made to the queues. As we shall soon see, these changes may also cause additional events to be placed on the event list. The process of removing the first node from the event list and effecting the changes that it causes is repeated until the event list is empty.
When an arrival node is removed from the event list, a node representing the arriving customer is placed on the shortest of the queues represent four lines. If that customer is the only one on his queue, a node representing his departure is also placed on the event list, since he is at the front of his queue. At the same time, the next input line is read and an arrival node representing the next customer to arrive is placed on the event list. Thus there will always be an arrival node on the event list (as long as the input is not exhausted, at which point no more customers arrive), because as soon as one arrival node is removed from the event list, another is added to it.
When a departure node is removed from the event list, the node representing the departing customer is removed from the front of one of the four queues. At that point, the amount of time that the departing customer has spent in the bank is computed and added to a total. At the end of the simulation, this total will be divided by the number of customers to yield the average time spent by a customer. After a customer node has been deleted from the front of its queue, the next customer on the queue (if any) becomes the one being serviced by that teller and a departure node for that next customer is added to the event list.
This process continues until the event list is empty, at which point the average time is computed and printed. Note that the event list itself does not mirror any part of the real world situation. It is used as part of the program to control the entire process. A simulation such as this one, which proceeds by changing the simulated situation in response to the occurrence of one of several events, is called an event driven simulation.
A typical program structure is shown below;
initialize;
while not
eof(evlist)
begin
read arrival time and service time generate events;
update queues;
update statistics;
if (stepmode = true) then read;
end;
print
results;
You should submit the following:
NOTE: A program with successful graphics will get up to 20 bonus points.