Simulating a Grocery Store Line Queue using Java

Question

So I have a problem I've been wracking my brain over for about a week now. The situation is:

Consider a checkout line at the grocery store. During any given second, the probability that a new customer joins the line is 0.02 (no more than one customer joins the line during any given second). The checkout clerk takes a random amount of time between 20 seconds to 75 seconds to serve each customer. Write a program to simulate this scenario for about ten million seconds and print out the average number of seconds that a customer spends waiting in line before the clerk begins to serve the customer. Note that since you do not know the maximum number of customers that may be in line at any given time, you should use an ArrayList and not an array.

The expected average wait time is supposed to be between 500 and 600 seconds. However, I have not gotten an answer anywhere close to this range. Given that the probability of a new customer in the line is only 2%, I would expect the line to never have more than 1 person in it, so the average wait time would be about 45-50 secs. I have asked a friend (who is a math major) what his view on this problem, and he agreed that 45 seconds is a reasonable average given the 2% probability. My code so far is:

package grocerystore;

import java.util.ArrayList;
import java.util.Random;

public class GroceryStore {

private static ArrayList<Integer> line = new ArrayList();    
private static Random r = new Random();

public static void addCustomer() {        
    int timeToServe = r.nextInt(56) + 20;
    line.add(timeToServe);        
}    

public static void removeCustomer() {
    line.remove(0);
}

public static int sum(ArrayList<Integer> a) {
    int sum = 0;
    for (int i = 0; i < a.size(); i++) {
        sum += a.get(i);
    }
    return sum;
}

public static void main(String[] args) {
      int waitTime = 0;
      int duration = 10000;
      for (int i = 0; i < duration; i++) {              
          double newCust = r.nextDouble();

          if (newCust < .02) {
              addCustomer();
          }

          try {
              for (int j = 0; j < line.get(0); j++) {                                          
                  waitTime = waitTime + sum(line);                      
              }
          } catch (IndexOutOfBoundsException e) {}                

          if (line.isEmpty()) {}
          else {
              removeCustomer();
          }
      }
      System.out.println(waitTime/duration);
}

}

Any advice about this would be appreciated.

Answer 1

There's actually a very easy implementation of single server queueing systems where you don't need an ArrayList or Queue to stash customers who are in line. It's based on a simple recurrence relation described below.

You need to know the inter-arrival times' distribution, i.e., the distribution of times between one arrival and the next. Yours was described in time-stepped fashion as a probability of 0.02 of having a new arrival in a given tick of the clock. That equates to a Geometric distribution with p = 0.02. You already know the service time distribution - Uniform(20,75).

With those two pieces of info, and a bit of thought, you can deduce that for any given customer the arrival time is the previous customer's arrival-time plus a (generated) interarrival time; this customer can begin being served at either their arrival-time or the departure-time of the prior customer, whichever comes later; and they finish up with the server and depart at their begin-service time plus a (generated) service-time. You'll need to initialize the arrival-time and departure time of an imaginary zeroth customer to kick-start the whole thing, but then it's a simple loop to calculate the recurrence.

Since this looks like homework I'm giving you an implementation in Ruby. If you don't know Ruby, think of this as pseudo-code. It should be very straightforward for you to translate to Java. I've left out details such as how to generate the distributions, but I have actually run the complete implementation of this, replacing the commented lines with statistical tallies, and it gives average wait times around 500.

interarrival_time = Geometric.new(p_value)
service_time = Uniform.new(service_min, service_max)
arrival_time = depart_time = 0.0        # initialize zeroth customer
loop do
   arrival_time += interarrival_time.generate
   break if arrival_time > 10_000_000
   start_time = [arrival_time, depart_time].max
   depart_time = start_time + service_time.generate
   delay_in_queue = start_time - arrival_time
   # do anything you want with the delay_in_queue value:
   #   print it, tally it for averaging, whatever...
end

Note that this approach skips over the large swathes of time where nothing is happening, so it's a quite efficient little program compared to time-stepping through every tick of the simulated clock and storing things in dynamically sized containers.

One final note - you may want to ignore the first few hundred or thousand observations due to initialization bias. Simulation models usually need a "warm-up" period to remove the effect of the programmatically necessary initialization of variables to arbitrary values.

Answer 2

Instead of using an ArrayList, a Queue might be better suited for managing the customers. Also, remove the try/catch clause and a throws IndexOutOfBoundsException to the main function definition.

Answer 3

Here's some pseudocode to help you plan it out

for each second that goes by:
    generate probability

    if probability <= 0.02
        add customer

    if wait time is 0
        if line is not empty
            remove customer
            generate a new wait time
    else
        decrement wait time