Queues


Car Wash Simulation Project

Problem Description

The current car wash machine at Squeaky Clean Car Wash requires exactly 4 minutes to complete the regular car wash (including rinse, wax, and dry). The owners are considering upgrading their equipment, though, because they are suspicious that the average wait time for the cars is long enough that they are losing business. They are considering replacing the current machine with one that would take only 3 minutes. The upgrade will be expensive, so they would like to know in advance how much difference it will make.

Construct a simulation of the car wash to determine what the average waiting time would be during a typical day (9 am to 7 pm) using the new equipment. 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!). Since the arrival times are uneven, 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.

Some of the questions that are still open are: 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?

In addition to implementing the simulation, write a report for the owners of the Squeaky Clean Car Wash that presents an analysis of your results. (See the Analysis section below for full details.)

You may wish to develop your own design for this program, or you may use the design presented in the Car Wash Design Case Study.

Implementation

Implement the Car Wash Simulation program. A reasonable set of classes for the problem would be:
for each minute of the simulation

   if a car arrives
        increment the number of cars that have arrived
        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
        move the car from the queue to the car wash bay
        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 already being washed
        decrease the amount of time left before the bay is available
Question: is there a case missing here that requires any action?

Test-Driven, Iterative Development

Develop and test your program in small increments. For example, you might proceed through the following steps:

  1. Construct Car objects and use a queue:

    Create a Car class that keeps track of a car's arrival time. Have your main method loop a number of times (e.g., 20 times). In each step, print a timestamp and implement the random arrival of a car, putting cars in a queue. Test the queue by stepping through it at the end, printing the arrival time of each car. Your output at this point might look something like:

        time step 0:  A car arrived.
        time step 1:  No car arrived.
        time step 2:  No car arrived.
        time step 3:  A car arrived.
        time step 4:  A car arrived.
        ...
        Cars in queue:
        Car arrived at time step 0.
        Car arrived at time step 3.
        Car arrived at time step 4.
    (You may wish to use the Debug class for printing debugging information.)

  2. Develop and test the Bay class:

    Create a Bay class that tracks a car's progress through the bay, noting how many minutes of delay until the bay is available. When no car is in the bay, the delay is 0. (Tip: Pass the length of a car wash as a parameter so that you can experiment with times other than 3 minutes later.)

    You might want to modify your main method to loop through several time steps, but have a car arrive in only one pre-determined step. In each time step, report how long it will be before the car bay is available. For example, you might have

        time step 0:  No car arrived.  Bay available in 0 minutes.
        time step 1:  A car arrived.   Bay available in 3 minutes.
        time step 2:  No car arrived.  Bay available in 2 minutes.
        time step 3:  No car arrived.  Bay available in 1 minutes.
        time step 4:  No car arrived.  Bay available in 0 minutes.
  3. Develop and test the CarWashSimulation class:

    Implement the step method in the simulation class to handle a single minute when the car wash is open. Have the main function run the simulation for a small number of times (for example, 10 minutes) to test your code (especially the calculation of total wait time) on simple cases before trying to simulate an entire day. Update the main function to print the total number of cars serviced, the total wait time for all the cars, and the average wait time.

  4. Complete the Project:

    Once the simulation's step method seems to be running correctly, update it to handle cars that are still in the queue when the car wash closes and any other aspects of the original problem description that have not yet been implemented.

Analysis

Since providing the original problem specification, the owners of the Squeaky Clean Car Wash have asked for some additional information:

To answer these questions, simulate one week (7 days) of operation. Use your results to write a report that shows the average wait time and the number of cars that would have waited more than ten minutes for each type of machine (four-minute and three-minute wash) for each day in the 7-day period. For example, your output might include a table like the one below, along with a paragraph of explanation and conclusions. (Note that the numbers in the table below are completely made up, and should not be used to validate your results.)

4-Minute Bay3-Minute Bay
Avg Wait# Cars With
10 Min Wait
Avg Wait# Cars With
10 Min Wait
Monday18.3 min47.2 min1

Optional extension

Another alternative that the car wash owners are considering is to add a second bay similar to the one they have now. This would give them two bays, each of which takes four minutes to wash a car. Modify your program to handle multiple bays, and update your report to show what the results of having two bays would be. You might even go a step further, and tell then how many cars could they serve (what would the arrival frequency be) and still have the same results as a single four-minute or three-minute bay?


Author: Autumn C. Spaulding autumn@max.cs.kzoo.edu
with Alyce Brady abrady@kzoo.edu.

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