Assigned: October 5
Due: Friday, Nov. 2, 11:59pm
|
Read the entire assignment before you begin to implement it. You will almost certainly want to read it at least twice, and you will need to come back to it while writing your program. This assignment will take time to write. Do not wait to start on it. Start right away, and try to finish early so that you have time if things do not go according to plan. You will encounter difficulties. If you do not understand something, ask about it. When you read the assignment, you will probably imagine that it is huge, and you might become discouraged in your ability to solve it. It is not as large or difficult as it initially appears. The methods are short and simple, and most are fairly obvious. In fact, that is the reason that the simulation is broken down the way it is. The architecture makes implementing the simulation easy. |
The assignment is to simulate a bank, with customers arriving and tellers serving them. The simulation should report the following events, along with the times at which they occur.
Report a customer arrival. (When a customer arrives, the customer enters the customer queue.)
Report when a customer steps up to be served by a teller.
Report when a customer is finished being served.
With each event, report the length of the customer queue and the number of idle tellers. For example, a sample run might print the following results. You are not required to use this format, but provide the required information in some readable format. Numbers in brackets are times.
[ 0.00] Simulation starts [ 0.00] 0 waiting customers [ 0.00] 3 idle tellers [ 5.19] Customer 1 arrives [ 5.19] Teller 1: Start serving customer 1 [ 5.19] 0 waiting customers [ 5.19] 2 idle tellers [ 6.01] Customer 2 arrives [ 6.01] Teller 2: Start serving customer 2 [ 6.01] 0 waiting customers [ 6.01] 1 idle tellers [ 6.36] Customer 3 arrives [ 6.36] Teller 3: Start serving customer 3 [ 6.36] 0 waiting customers [ 6.36] 0 idle tellers [ 6.93] Teller 1: Finished serving customer 1 [ 6.93] 0 waiting customers [ 6.93] 1 idle tellers [ 7.24] Customer 4 arrives [ 7.24] Teller 1: Start serving customer 4 [ 7.24] 0 waiting customers [ 7.24] 0 idle tellers [ 7.64] Teller 3: Finished serving customer 3 [ 7.64] 0 waiting customers [ 7.64] 1 idle tellers [ 8.28] Customer 5 arrives [ 8.28] Teller 3: Start serving customer 5 [ 8.28] 0 waiting customers [ 8.28] 0 idle tellers [ 9.22] Customer 6 arrives [ 9.22] 1 waiting customers [ 9.22] 0 idle tellers [ 10.04] Teller 2: Finished serving customer 2 [ 10.04] Teller 2: Start serving customer 6 [ 10.04] 0 waiting customers [ 10.04] 0 idle tellers [ 10.42] Teller 2: Finished serving customer 6 [ 10.42] 0 waiting customers [ 10.42] 1 idle tellers [ 13.08] Teller 3: Finished serving customer 5 [ 13.08] 0 waiting customers [ 13.08] 2 idle tellers [ 17.22] Teller 1: Finished serving customer 4 [ 17.22] 0 waiting customers [ 17.22] 3 idle tellers [ 17.93] Customer 7 arrives [ 17.93] Teller 2: Start serving customer 7 [ 17.93] 0 waiting customers [ 17.93] 2 idle tellers [ 18.77] Teller 2: Finished serving customer 7 [ 18.77] 0 waiting customers [ 18.77] 3 idle tellers [ 19.86] Customer 8 arrives [ 19.86] Teller 3: Start serving customer 8 [ 19.86] 0 waiting customers [ 19.86] 2 idle tellers [ 22.10] Teller 3: Finished serving customer 8 [ 22.10] 0 waiting customers [ 22.10] 3 idle tellers [ 22.57] Customer 9 arrives [ 22.57] Teller 1: Start serving customer 9 [ 22.57] 0 waiting customers [ 22.57] 2 idle tellers [ 23.97] Customer 10 arrives [ 23.97] Teller 2: Start serving customer 10 [ 23.97] 0 waiting customers [ 23.97] 1 idle tellers [ 24.36] Customer 11 arrives [ 24.36] Teller 3: Start serving customer 11 [ 24.36] 0 waiting customers [ 24.36] 0 idle tellers [ 25.47] Customer 12 arrives [ 25.47] 1 waiting customers [ 25.47] 0 idle tellers [ 26.12] Teller 3: Finished serving customer 11 [ 26.12] Teller 3: Start serving customer 12 [ 26.12] 0 waiting customers [ 26.12] 0 idle tellers [ 26.80] Teller 1: Finished serving customer 9 [ 26.80] 0 waiting customers [ 26.80] 1 idle tellers [ 27.37] Customer 13 arrives [ 27.37] Teller 1: Start serving customer 13 [ 27.37] 0 waiting customers [ 27.37] 0 idle tellers [ 27.40] Customer 14 arrives [ 27.40] 1 waiting customers [ 27.40] 0 idle tellers [ 28.30] Teller 3: Finished serving customer 12 [ 28.30] Teller 3: Start serving customer 14 [ 28.30] 0 waiting customers [ 28.30] 0 idle tellers [ 30.47] Teller 3: Finished serving customer 14 [ 30.47] 0 waiting customers [ 30.47] 1 idle tellers [ 35.46] Customer 15 arrives [ 35.46] Teller 3: Start serving customer 15 [ 35.46] 0 waiting customers [ 35.46] 0 idle tellers [ 36.84] Customer 16 arrives [ 36.84] 1 waiting customers [ 36.84] 0 idle tellers [ 37.16] Teller 3: Finished serving customer 15 [ 37.16] Teller 3: Start serving customer 16 [ 37.16] 0 waiting customers [ 37.16] 0 idle tellers [ 39.40] Teller 3: Finished serving customer 16 [ 39.40] 0 waiting customers [ 39.40] 1 idle tellers [ 39.83] Teller 1: Finished serving customer 13 [ 39.83] 0 waiting customers [ 39.83] 2 idle tellers [ 40.07] Customer 17 arrives [ 40.07] Teller 3: Start serving customer 17 [ 40.07] 0 waiting customers [ 40.07] 1 idle tellers [ 40.27] Customer 18 arrives [ 40.27] Teller 1: Start serving customer 18 [ 40.27] 0 waiting customers [ 40.27] 0 idle tellers [ 42.34] Customer 19 arrives [ 42.34] 1 waiting customers [ 42.34] 0 idle tellers [ 43.62] Teller 2: Finished serving customer 10 [ 43.62] Teller 2: Start serving customer 19 [ 43.62] 0 waiting customers [ 43.62] 0 idle tellers [ 43.78] Customer 20 arrives [ 43.78] 1 waiting customers [ 43.78] 0 idle tellers [ 45.23] Customer 21 arrives [ 45.23] 2 waiting customers [ 45.23] 0 idle tellers [ 45.63] Customer 22 arrives [ 45.63] 3 waiting customers [ 45.63] 0 idle tellers [ 46.07] Customer 23 arrives [ 46.07] 4 waiting customers [ 46.07] 0 idle tellers [ 46.09] Customer 24 arrives [ 46.09] 5 waiting customers [ 46.09] 0 idle tellers [ 48.95] Customer 25 arrives [ 48.95] 6 waiting customers [ 48.95] 0 idle tellers [ 49.38] Customer 26 arrives [ 49.38] 7 waiting customers [ 49.38] 0 idle tellers [ 51.01] Teller 1: Finished serving customer 18 [ 51.01] Teller 1: Start serving customer 20 [ 51.01] 6 waiting customers [ 51.01] 0 idle tellers [ 52.79] Customer 27 arrives [ 52.79] 7 waiting customers [ 52.79] 0 idle tellers [ 54.36] Teller 3: Finished serving customer 17 [ 54.36] Teller 3: Start serving customer 21 [ 54.36] 6 waiting customers [ 54.36] 0 idle tellers [ 54.65] Teller 1: Finished serving customer 20 [ 54.65] Teller 1: Start serving customer 22 [ 54.65] 5 waiting customers [ 54.65] 0 idle tellers [ 54.66] Teller 3: Finished serving customer 21 [ 54.66] Teller 3: Start serving customer 23 [ 54.66] 4 waiting customers [ 54.66] 0 idle tellers [ 56.14] Customer 28 arrives [ 56.14] 5 waiting customers [ 56.14] 0 idle tellers [ 58.87] Teller 3: Finished serving customer 23 [ 58.87] Teller 3: Start serving customer 24 [ 58.87] 4 waiting customers [ 58.87] 0 idle tellers [ 61.22] Customer 29 arrives [ 61.22] 5 waiting customers [ 61.22] 0 idle tellers [ 63.39] Teller 2: Finished serving customer 19 [ 63.39] Teller 2: Start serving customer 25 [ 63.39] 4 waiting customers [ 63.39] 0 idle tellers [ 63.49] Customer 30 arrives [ 63.49] 5 waiting customers [ 63.49] 0 idle tellers [ 63.79] Customer 31 arrives [ 63.79] 6 waiting customers [ 63.79] 0 idle tellers [ 67.13] Customer 32 arrives [ 67.13] 7 waiting customers [ 67.13] 0 idle tellers [ 67.15] Customer 33 arrives [ 67.15] 8 waiting customers [ 67.15] 0 idle tellers [ 67.68] Teller 1: Finished serving customer 22 [ 67.68] Teller 1: Start serving customer 26 [ 67.68] 7 waiting customers [ 67.68] 0 idle tellers [ 68.48] Teller 3: Finished serving customer 24 [ 68.48] Teller 3: Start serving customer 27 [ 68.48] 6 waiting customers [ 68.48] 0 idle tellers [ 71.80] Customer 34 arrives [ 71.80] 7 waiting customers [ 71.80] 0 idle tellers [ 71.99] Teller 1: Finished serving customer 26 [ 71.99] Teller 1: Start serving customer 28 [ 71.99] 6 waiting customers [ 71.99] 0 idle tellers [ 72.71] Customer 35 arrives [ 72.71] 7 waiting customers [ 72.71] 0 idle tellers [ 75.14] Customer 36 arrives [ 75.14] 8 waiting customers [ 75.14] 0 idle tellers [ 75.86] Customer 37 arrives [ 75.86] 9 waiting customers [ 75.86] 0 idle tellers [ 76.84] Customer 38 arrives [ 76.84] 10 waiting customers [ 76.84] 0 idle tellers [ 77.77] Teller 1: Finished serving customer 28 [ 77.77] Teller 1: Start serving customer 29 [ 77.77] 9 waiting customers [ 77.77] 0 idle tellers [ 79.13] Customer 39 arrives [ 79.13] 10 waiting customers [ 79.13] 0 idle tellers [ 80.28] Teller 2: Finished serving customer 25 [ 80.28] Teller 2: Start serving customer 30 [ 80.28] 9 waiting customers [ 80.28] 0 idle tellers [ 80.29] Customer 40 arrives [ 80.29] 10 waiting customers [ 80.29] 0 idle tellers [ 81.17] Teller 1: Finished serving customer 29 [ 81.17] Teller 1: Start serving customer 31 [ 81.17] 9 waiting customers [ 81.17] 0 idle tellers [ 85.06] Customer 41 arrives [ 85.06] 10 waiting customers [ 85.06] 0 idle tellers [ 85.18] Teller 3: Finished serving customer 27 [ 85.18] Teller 3: Start serving customer 32 [ 85.18] 9 waiting customers [ 85.18] 0 idle tellers [ 86.01] Customer 42 arrives [ 86.01] 10 waiting customers [ 86.01] 0 idle tellers [ 86.35] Teller 3: Finished serving customer 32 [ 86.35] Teller 3: Start serving customer 33 [ 86.35] 9 waiting customers [ 86.35] 0 idle tellers [ 86.59] Customer 43 arrives [ 86.59] 10 waiting customers [ 86.59] 0 idle tellers [ 86.94] Customer 44 arrives [ 86.94] 11 waiting customers [ 86.94] 0 idle tellers [ 86.98] Customer 45 arrives [ 86.98] 12 waiting customers [ 86.98] 0 idle tellers [ 87.14] Customer 46 arrives [ 87.14] 13 waiting customers [ 87.14] 0 idle tellers [ 87.17] Customer 47 arrives [ 87.17] 14 waiting customers [ 87.17] 0 idle tellers [ 87.38] Customer 48 arrives [ 87.38] 15 waiting customers [ 87.38] 0 idle tellers [ 90.58] Customer 49 arrives [ 90.58] 16 waiting customers [ 90.58] 0 idle tellers [ 90.83] Teller 2: Finished serving customer 30 [ 90.83] Teller 2: Start serving customer 34 [ 90.83] 15 waiting customers [ 90.83] 0 idle tellers [ 92.85] Customer 50 arrives [ 92.85] 16 waiting customers [ 92.85] 0 idle tellers [ 93.94] Customer 51 arrives [ 93.94] 17 waiting customers [ 93.94] 0 idle tellers [ 94.03] Customer 52 arrives [ 94.03] 18 waiting customers [ 94.03] 0 idle tellers [ 94.65] Customer 53 arrives [ 94.65] 19 waiting customers [ 94.65] 0 idle tellers [ 95.15] Customer 54 arrives [ 95.15] 20 waiting customers [ 95.15] 0 idle tellers [ 95.19] Teller 1: Finished serving customer 31 [ 95.19] Teller 1: Start serving customer 35 [ 95.19] 19 waiting customers [ 95.19] 0 idle tellers [ 98.62] Customer 55 arrives [ 98.62] 20 waiting customers [ 98.62] 0 idle tellers [ 99.62] Customer 56 arrives [ 99.62] 21 waiting customers [ 99.62] 0 idle tellers [ 100.31] Customer 57 arrives [ 100.31] Simulation done
The input format is described below. The input comes from the standard input and all output should go to the standard output.
Use an object-oriented approach. There should be objects in your program that correspond to objects in the simulation. For example, each customer should be an object and each teller should be an object. Use the following classes. (You can choose different names for them, but keep the general intent.)
Class Customer. An object of class Customer represents a customer. Its holds a customer number and a transaction duration, indicating how long this customer needs to talk to a teller.
Class Teller. An object of class Teller represents a teller. It holds a teller number and reports when it starts and ends a transaction.
Class Event. An object of class Event represents an event that can happen in the simulation. It is an abstract class. Subclasses of Event are particular events. Each event object holds a time at which it is scheduled to occur.
Class CustomerArrivalEvent. This is a subclass of Event. An object of class CustomerArrivalEvent represents an event in which a customer arrives at the bank and enters the customer queue.
Class CustomerServiceEvent. This is a subclass of Event. An object of class CustomerServiceEvent represents an event in which a customer leaves the customer queue and begins talking to a teller.
Class ServiceEndEvent. This is a subclass of Event. An object of class ServiceEndEvent represents an event in which a customer finishes talking to a teller and leaves the bank.
Class Bank. There will be just one object of class Bank. Its job is to hold: a customer queue; a teller queue (holding idle tellers); an event queue (holding pending events); and a current time of day. It has a method that performs the simulation, and a method to schedule an event into its event queue.
Class Simulate. This just holds a main method that starts the simulation.
A customer holds a customer number (type int); a transaction duration (type double), telling how long this customer needs to talk to a teller; and the bank, so that the customer has access to the bank object.
There should be one constructor that takes two parameters: a bank and an average transaction duration. The constructor should choose an actual transaction duration at random, with the given average, using the pseudo-random number generator; and should assign itself the next available customer number.
You can use a class variable in the customer class holding the next available customer number. Add 1 to it every time a customer is created. Be sure to initialize it. To initialize a class variable, include a class constructor. It has no name or heading. Just put a part in {...} inside the class. It will run when the class is loaded.
Provide a method to get the customer's transaction duration and a method to get the customer number. Also provide a method that causes the customer to enter the bank's customer queue.
A teller holds a teller number (type int); and the bank in which the teller is working.
There should be one constructor that takes one parameter: the bank. The constructor should get the next available teller number.
Provide: a method to get the teller number; and a method to cause the teller to enter the bank's teller queue. Also provide two methods for printing events: one that prints that the teller is beginning to serve a customer, and one that prints that the teller is done serving a customer. Each will need to take the customer as a parameter.
You will need to use first-in-first-out queues for the customer and teller queues. Use the Java class LinkedList<Customer> for a queue of customers and LinkedList<Teller> for a queue of tellers. Use the add method to add an object to the end of the queue; poll to remove the first thing; and isEmpty to check whether the queue is empty. To create a new (empty) queue of customers, use
LinkedList<Customer> customerQueue; ... customerQueue = new LinkedList<Customer>();
An event holds a bank and a time. It implements the Comparable<Event> interface, meaning that it contains a compareTo method. (The priority queue class will order events according to what the compareTo method says.) The heading for this class should be
abstract class Event implements Comparable<Event>
There should be one constructor that takes two parameters: a bank and a time (a real number). It should just remember the bank and the time.
Abstract method happen( ) should cause the event to happen. What it does depends on the subclass.
Abstract method debugPrint( ) should print a brief description of the event. (It is only useful for debugging.)
Concrete method getTime() should return the time of this event.
Concrete method compareTo should take another Event object as a parameter, and return an int telling how the time of this event relates to the time of another event. Expression a.compareTo(b) returns
CustomerArrivalEvent is a subclass of Event.
A customer arrival event object only holds the inherited bank and the time at which the event occurs.
There should be one constructor that takes a bank and a time as parameters. It should install the bank and time, using the constructor in class Event.
Method happen( ) should: create a customer; print that the customer has arrived; tell the customer to put itself into the bank's customer queue; create a new CustomerArrivalEvent event; and schedule the new CustomerArrivalEvent to occur a randomly selected time in the future. Each print should be preceded by the time.
To determine when the next customer arrives, get the average customer arrival interval from the bank. (See class Bank.) Get an exponentially distributed pseudo-random number from the pseudo-random number generator.
Method debugPrint( ) should print a brief description of the event. For example, it might print "Customer arrival event".
CustomerServiceEvent is a subclass of Event.
A customer service event object holds the customer who is to be served and the teller who is serving the customer. Since it is a subclass of Event, it also contains the bank and a time.
There should be one constructor that takes four parameters: a customer; a teller; the bank; and a time. It should run the Event constructor to install the the bank and time, and should remember the customer and the teller.
Method happen( ) should: ask the teller to print that the customer is being served; and schedule a ServiceEndEvent in the future. The time of the ServiceEnd event depends on the duration of the customer's transaction. The print should be preceded by the time.
Method debugPrint( ) should print a brief description of the event, including numbers of the teller and customer that it holds.
ServiceEndEvent is a subclass of Event.
A service end event object holds the customer who has been served and the teller who is finished serving the customer. Since it is a subclass of Event, it also contains the bank and a time.
There should be one constructor that takes four parameters: a customer; a teller; the bank; and a time. It should run the Event constructor to install the the bank and the time, and should remember the customer and the teller.
Method happen( ) should: ask the teller to print that the customer service is done; and add the teller to the bank's teller queue. The print should be preceded by the time.
Method debugPrint( ) should print a brief description of the event, including numbers of the teller and customer that it holds.
The event queue is a priority queue. Use the Java class PriorityQueue<Event> for it. Use add to add an event to the priority queue, poll to remove the next event, and isEmpty to test whether the queue is empty.
A bank object should hold
There should be one constructor that takes three parameters: the number of tellers, the average customer arrival interval, and the average customer transaction time. It should create the queues and the pseudo-random number generator and remember the information from the parameters. It should create the tellers, and insert them into the teller queue.
Method simulate(startTime, endTime) should perform the simulation, starting at time startTime, and ending at time endTime. It should start by creating a new customer arrival event, and inserting the customer arrival event into the event queue. Then it should enter a loop where it does the following.
Provide a method to schedule an event. It should take the event as a parameter.
Provide methods to return: the average customer arrival time; the average transaction time; and the current time of day.
Provide a method to print the time of day, in some standard form, such as "[ t ]", where t is the time.
Provide a method to get an exponentially distributed pseudo-random number with a given mean.
You will probably want other methods to help. Make them sensible, with the goal of making all of the methods clear and fairly short.
A pseudo-random number generator does not really produce random numbers at all. It returns a sequence of numbers that appear to be random. Use the Java Random class. Method nextDouble gets a real number that is uniformly distributed between 0 and 1. What you want is an exponentially distributed (memoryless) random number. If you have generated uniformly distributed random number u, then use the following formula to yield an exponentially distributed random number e with mean m.
e = -m ln(u)where ln is the natural logarithm, called java.lang.Math.log in Java.
When you create a pseudo-random number generator, give it a seed, a long integer. The seed determines the sequence of numbers produced, and if you run the simulation twice with the same seed, you will get exactly the same results both times. Expression new Random(seed) creates a new pseudo-random number generator with the given seed.
A uniform distribution gives the same probability to every number in a given range.
There is a different distribution, however, that tends to model real situations in simulations more accurately. To understand that other distribution, imagine choosing a small interval of time, such as one second, and asking whether a customer arrives during that interval. Suppose that the probability that a customer arrives during a given second is small.
If the customer arrival time were uniformly distributed, then, the more seconds without a customer that you see, the more likely it becomes that a customer will arrive in the next second. For example, imagine that you choose the arrival time to be uniformly distributed between 0 and 120 seconds. In the first second, the probability of an arrival is 1/120. But if you have waited for 110 seconds, and no customer has arrived, then the likelihood of an arrival in the next second is 1/10. The longer you wait without an arrival, the more likely an arrival in the next second becomes.
A memoryless distribution, on the other time, keeps the probability of an arrival occurring during a given second the same, regardless of what has happened in the past. This is similar to radioactive decay of an unstable atomic nucleus. The nucleus does not remember how long it has existed, and the probability of it decaying in a given interval does not depend on how old the nucleus is.
Customer arrivals at a bank are eratic, not regular. There is nothing that indicates the probability of a customer arrival in the next second should be higher just because there was not one in the previous few seconds. Sometimes, two customers arrive at almost the same moment. Sometimes, there is a longer gap between customers. So we use a memoryless distribution for customer arrivals. It also makes sense to use that distribution for the distribution of transaction times.
The main program should read information from the standard input about the simulation, then create a bank and ask the bank to perform the simulation. The input format should be as follows.
| Number of tellers |
| Average customer arrival interval |
| Average transaction time |
| Start time |
| End time |
| Seed |
For example, input
2 5.0 10.0 0.0 100.0 7547104requests a simulation with 2 tellers, starting at time 0.0 and ending at time 100.0. The customers arrive, on the average, one every 5.0 minutes. The average transation takes 10.0 minutes. The random number generator is initialized by setting its seed to 7547104.
You can use a separate file for each class or put all of the classes in one file. Put all of your files in a directory for this assignment. Before submitting, move any extraneous .java files to a different directory. Log into one of the Unix computers in the lab, and change your directory to the directory that contains your assignment. For example, use command
cd Assignment2Now use the following command to submit the assignment.
~karl/3310/bin/submit L2 *.java