Queues

Car Wash Project

Problem Description

The car wash machine at Squeaky Clean Car Wash requires exactly 3 minutes to complete the regular car wash (including rinse, wax, and dry). A car arrives at the car wash approximately every four minutes (cars don't arrive exactly four minutes apart: that would be easy to program!). The owners of the car wash are proposing to add another car wash bay, because they are suspicious that the average wait time for the cars is long enough that they are losing business. Construct a simulation of the car wash to determine the average waiting time for a car at the car wash during a typical day (9 am to 7 pm). Since the arrival time is an average, there is often a waiting line. This can be simulated using a queue.

Think about how you might go about simulating this problem. How could you simulate the arrivals, waiting, and washing of the cars at the car wash?

Perhaps it would be useful to think of what can happen in a given minute in the car wash (we'll assume that at most one car can arrive in any given minute, although this is not necessary). In a car wash, you can have cars arriving, cars waiting, and cars being washed. You also have cars changing from one state to another. If a car arrives and there is a car being washed, the arriving car becomes a waiting car. If there is at least one car waiting and the car wash bay becomes available, a waiting car becomes a car being washed.

How will you determine whether a car should arrive in the current minute? (In any given minute, there is a 1 in 4 chance that a car will arrive.) How will you decide whether a car is currently being washed? How will you decide when the machine is empty? How will you represent the waiting time of a car? How will you represent the total waiting time of all the cars for the day? How will you represent the total time that the car wash is open?

You may wish to develop your own design for this program, or you may wish to use the design below.

One Possible Design

First, let's look at the things in the problem description that might turn into objects in the implementation. The "things" (nouns) are:

car wash machine	Squeaky Clean Car Wash	minutes
car	owners	car wash bay
average waiting time	lost business	simulation
day	arrival time	waiting line (queue)

Several of these refer to the business as a whole: Squeaky Clean Car Wash and owners. The word simulation covers these, and is more relevant for our program. The possibility of lost business is the reason for the simulation, but not part of it. We are left with car wash machine and car wash bay (which seem to refer to the same thing), car, waiting line (queue), and several objects related to time: minutes, day, arrival time, and average waiting time.

Let's reconsider the problem in more detail. Our primary task is to create a simulation of the car wash for one day that calculates the average waiting time of all the cars. To do that we need to know the total waiting time for all the cars and the number of cars. To calculate the total waiting time we need the individual waiting time for each car, which we calculate from its arrival time (the current time when the car arrives) and the current time when the car leaves the waiting line and enters the car wash bay. Since the time a car spends in the wash bay is measured in minutes, we might as well measure waiting times and the time that the car wash is open (the length of the day) in minutes as well. As mentioned above, if a car arrives every four minutes, on average, then in any given minute there is a one in four chance of a car arriving.

This analysis has introduced several new "things" that did not appear explicitly in the original problem description: the total waiting time for all the cars, the number of cars, the waiting time for each individual car, and the current time. Our new list is:

Integers:	length of day	current time	arrival time
	individual waiting time	total waiting time	average waiting time
	number of cars
Objects:	simulation	car	waiting line (queue)
	car wash bay

Since the only reason we care about individual waiting times is to determine the total waiting time, we can avoid keeping track of them by adding them to the total waiting time as we go.

What do we know about the responsibilities of the objects listed in our table? In each minute the simulation is responsible for determining whether a car arrives, whether it has to wait on line, whether a car can leave the line, and, if so, how long it waited. To determine this it needs to know the car's arrival time and the current time. This constitutes a single step of the simulation. The simulation must run for as many minutes as the car wash is open. (Actually, the simulation should usually run longer -- what happens if there are cars waiting in line or in the wash bay when the car wash officially closes?) When done, the simulation must calculate the average waiting time.

The waiting line is easy. It is a first-in/first-out (FIFO) data structure of cars and, as mentioned in the problem description, can be modeled as a queue.

What do we care about for cars? We care about their arrival times and their waiting times. We also care about how long a car spends being washed, but we could argue that that is really a function of the car wash bay rather than of the car since all cars entering the bay will take the same amount of time to be washed. The waiting time can be calculated by the simulation, so the only thing the car really needs to keep track of is its arrival time. In fact, we could eliminate cars altogether in this simulation, and just keep a queue of arrival times. Providing a car abstraction more closely models the problem domain, however, and might be useful in the future if the problem is extended.

Finally, what are the responsibilities of a car wash bay? It should be able to tell the simulation whether it is empty or not, and, if it is not empty, it should keep track of the time until it becomes empty.

Implementation

A wash lasts three minutes, but your simulation should re-evaluate the state of the Squeaky Clean Car Wash every minute.

To solve this problem, use the Queue class and the other built-in classes that you find useful. Becoming familiar with the more common classes provided will be helpful to you, as they will often shorten your workload. Many classes in Java can be easily extended to make them useful for similar tasks. You can read the specifications for the built-in Java classes online: http://java.sun.com/j2se/1.4/docs/api/index.html. Become accustomed to using this website as a reference.

Consider the pseudo-code below, which shows all of the things that happen in one minute at the car wash. You will use this pseudo-code to write your Car Wash Simulation.

   for each minute of the simulation
   
       if a car arrives
           note the arrival time of the car (store this with the car)
           add the car to the queue
   
       if the car wash bay is empty and there is a car waiting to be washed
           dequeue a car for washing
           determine how long that car was waiting and add to total wait time
           start washing the car (bay will be occupied for next 2 minutes)
   
       otherwise, if there is a car being washed
           decrease the amount of time left before the car is done (bay empty)

Question: is there a case missing here that requires any action?

Implement the Car Wash Simulation program. If you wish, you may start with the template classes provided for three classes, CarWashSimulation, Car, and Bay, and a very simple class, SimApplication, that contains the main function. The locations where you will need to add code have been starred. If you do not wish to use the code provided, you may wish to become familiar with it anyway as a useful supplement to the problem description. (These classes are licensed under the Creative Commons GNU General Public License. )
Design usually proceeds from a high level of abstraction ("the big picture") down to low levels of abstraction (the details). Implementation often (although certainly not always) proceeds "bottom-up." The following suggested ordering is "bottom-up" and allows you to test your modifications incrementally.
1. The Car class is so trivial that it has been provided for you. Complete the implementation of the Bay class.
2. Implement CarWashSimulation.reset based on the comments provided. You should be able to test your partially completed program at this point, although it won't do much.
3. Implement CarWashSimulation.step based on the pseudo-code above. (Note that the code already contains one statement.) Implement a simplified version of Simulation.run that runs until closing time. (Don't worry yet about cars still waiting to be washed when the car wash closes.) Have the main function run the simulation for a small number of times (for example, 5 or 10 minutes) to test your step function. You may wish to use the Debug class. (The Debug class comes from the AP^® Marine Biology Simulation case study and is available under the GNU General Public License.^†)
4. Once CarWashSimulation.step seems to be running correctly, update CarWashSimulation.run and main to meet the requirements of the problem description.
Run the simulation several times. What are the average waiting times over a ten hour day?
The owners of Squeaky Clean Car Wash don't want to make their customers wait more than ten minutes for a car wash. The car wash is open seven days a week. How often in those seven days is the average wait time over ten minutes?

Hint: Looking for the Random number generator? It's in java.util, and it's called Random.

Acknowledgements: The behavior of the car wash simulation in this lab is based on a project description by Todd Ollendyke (trollend@nb.net).

^†AP is a registered trademark of the College Entrance Examination Board. The Marine Biology Simulation case study was copyrighted in 2002 by the College Entrance Examination Board. It is available on the web from the College Board web site (www.collegeboard.com and apcentral.collegeboard.com).