CPT 244 – Queues: Customer Processing Problem When we are waiting in a fast food line, an airline service counter, a bank, etc. there is typically one of two different methods of managing customers: • Have a single line for people waiting for service. Every customer waits in a single line. When a teller becomes free, the customer at the head of the line moves to the teller. If there are multiple tellers free, one is picked randomly. • Have multiple lines – one for each teller. When customers come in the door they attempt to pick the line that has the shortest wait. This usually involves standing in the line with the fewest customers. If there are multiple choices, the appropriate line is selected randomly. So, which of these two methods of queuing customers is most efficient? In the single-line technique, tellers appear to be constantly busy and no customer is served before any customer that arrives later. In the multiple-line technique, however, customers can take the responsibility of evaluating the lines themselves. Procedure Attached to this assignment in the drop box are three files. One models a Customer, one models a customer generator (e.g. the front door of a bank) and the final models the bank itself (which contains the Main method). The Main method is really just a shell to demonstrate calling the customer generator. The generator accepts the following arguments: • minDuration – The minimum amount of time that it will take to process a customer's request. • maxDuration – The maximum amount of time that it will take to process a customer's request. • avgPerSlot – The average number of customers that will arrive per time slot. (e.g. .5 would mean one customer every two minutes; 3 would mean three customers per minute) • totalTime – Total number of time slots for which customers are to be generated. For example, 120 means a two hour timeslot. The time will actually be slightly longer to service the last few customers. • seed – If present, the this value is passed as the seed to the random number generator. If the seed is negative, no seed is passed. For the sake of this program, all time units represent one minute, though as long as the unit is consistent throughout the program, this could be any time (second, millisecond, day, etc.) The class has a single method, GetCustomers, which returns a Queue of customers now waiting to be served. You could think of it as the all the customers who arrived in the last minute. That method takes a single argument, timeslot, which is the number of seconds that have elapsed during the simulation. The precise working of the CustomerGenerator isn't important for the assignment, but if you are curious you have the code. For this assignment you will not need to create a Customer since the CustomerGenerator will do that, but you will need to access its properties. Two of these are set when the Customer is created and cannot be modified. You will want to set the service time when the Customer actually reaches teller. Begin your assignment using these three files. For a grade of 'C': We want to know how many tellers it takes so that no customer ever has to wait more than five minutes in line before being waited on. To get at this, and some other information our employer wants, we want to display the maximum minutes a teller was idle, the average minutes a teller was idle, the maximum minutes a customer had to wait and the average minutes a customer had to wait. (These last two need to be calculated on the fly, we aren't going to make all the customers wait in line until the day is over and ask them how long they waited.) You are going to need a Teller class. At a minimum, the Teller class should keep track of how much time it spends in the idle state, i.e. w/o having an active customer. It must also have some way to process a customer. To make things easier, I also suggest that the Teller have a reference to a Queue of customers so that it can pull the next customer off the queue. That will make moving to the work for a 'B' easier as well. I also encourage you to have a reference to the currentCustomer. You will also want a processNextCustomer method – see below. I'll leave most of the details up to you, but here is a very high level view of your process. • Create an empty Queue of customers • Create a CustomerGenerator. • Create a list of Tellers – start with some reasonable size, then modify the number until you have the fewest number of tellers but still have no wait time greater than five minutes. Note your code does not have to do figure this out; you can experiment until you find the right answer. Think carefully and you should be able to determine a good starting point based on the parameters passed to the CustomerGenerator constructor. • Set the currentMinute to zero. • Loop until the time duration expires AND the Queue is empty, performing the following o get the list of customers from the customer generator for that minute o add them to the Queue of customers o foreach teller in the list  have the teller process a customer (processNextCustomer) • the method should accept the current time as its argument • it should check to see whether it is still busy (Question: how does it know whether it is busy?) with an earlier customer; there are three possibilities o busy o return w/o doing anything o not busy: o it should pull a customer off the queue and assign a reference to an internal Customer object o it should set the time of the customers service time to the current time o not busy but the queue is empty o it should increment its idle time o Increment the current time End Loop • Print the parameters, appropriately labeled, that were passed to the CustomerGenerator...this defines the beginning state. • Print the values described above (highest wait time, average wait time, highest idle time, average idle time) • Print the number of customers serviced and the total time taken. For a grade of B: Add the multiple-line simulation, one line per Teller. You can do this in two completely different Banks if you prefer, but you may find that it is pretty simple to have a flag that you can flip to have your code process multiple queues. They are very similar. Rather than a single queue you will want one queue for each teller (think List>). The part of the code which gets the Queue from the customer generator will determine which queue has the fewest customers and add the customer to that queue. If there is a tie, it doesn't matter which one gets it. (To be fair, you should do round-robin scheduling but that is more trouble that it is worth; just hand it to the first teller in the list.) Thought Questions Consider the following questions as you complete the assignment: • Run several simulations of both types of queues. Which queue strategy seems to process all the customers fastest? Is the number of required tellers the same? If not, which algorithm requires the fewest tellers? • Is there a difference between the average wait-time for customers between the two techniques? • Is there a difference between the average/max idle-time for Tellers between the two techniques? For a grade of A: Wrap your Queue of customers (or if you are brave, extend the Queue class) into a class that can keep track of the total of the TransactionDurations of all the customers in the queue. Don't walk the queue, simply keep track by adding to the number when Enqueue is called and subtracting from the number when Dequeue is called. Change the algorithm so that when a new customer 'arrives' they are placed into the queue with the shortest total of TransactionDurations rather than the line with the fewest customers. Keep the number of tellers the same as you did for the 'B' portion. More Questions: • What do you notice? • What does this say about choosing a line based on length, say at a bank, vs. choosing a line at a grocery store where you can see the number of items in the customers' carts? Notes I strongly encourage you to get the work for a 'C' working well before attempting to move on to the 'B' and 'A' assignments. If you have thought through the original assignment well, and work out all the bugs at that stage, adding the extra features is actually quite simple. Think hard about how to represent your single queue so that it could be easily expanded to multiple queues.