CSCI 151 Lab 11: Ice Cream Store

Overview

In this lab, we will use a heap-based priority queue to implement a discrete event simulation. This lab will:

Give you practice using the priority queue API, and show you a (somewhat) real-world application of priority queues.
Give you practice working with a program constructed from many interacting classes.

Description

You are the manager of a new ice cream store, and you are trying to decide how many seats to put in your store so as to maximize your profit. In order to help you decide, you want to write a simulation that will test the outcome for different possibilities. Based on your observations of other ice cream stores, you have decided on the following scenario for your simulation.

Every so often, one or more groups of 1–6 people enter your store. You may assume that the number of groups entering at each time step follows a Poisson distribution with average 0.2 (that is, on average, one group of people enters your store every five time steps; you do not need to know what a Poisson distribution is). However, if there are not enough empty seats for everyone in a group, the group will leave. Also, if there are too many empty seats, they may assume that your store isn’t cool and leave to go to a different ice cream store. In particular, if the ratio of empty seats to the total number of seats is \(e\), then they will leave with probability \(C e\), where \(C\) is the “coolness parameter”. We will use a value of \(C = 3/4\). For example, if your store has 10 seats and 4 of them are occupied, then \(e = 6/10 = 3/5\), and a new group entering your store will leave with probability \(3/4 \cdot 3/5 = 9/20\).

If there are enough seats and the group thinks your store is cool, they will sit down. After a few minutes (a random number from 1–5) they will order some ice cream. Each person in the group will order a random number of scoops from 1–4 (you can decide how much to charge per scoop). Then they will stay while they eat their ice cream; you may assume that the amount of time a group stays follows a Poisson distribution with an average of 10 time steps. After they finish their ice cream, they will leave, vacating their seats.

Setup

Create a new Java project in Eclipse.
Download DiscreteEventSimulation.java, Event.java, and PoissonGenerator.java, and import them into your project.
ExponentialGenerator.java is also provided, but its use is optional. See below for an explanation of what it is and how to use it.

Notes

To generate random numbers from a uniform distribution, you can use System.Random. First, add import java.util.Random to the top of your file. Then, create a Random object, and use it to generate random numbers:
```
Random r = new Random();
int dieRoll = r.nextInt(6) + 1;

double prob = r.nextDouble();  // uniform on [0,1)
```
Note that nextInt(n) generates a random integer between 0 and 5. Adding 1 means the result will be a random integer between 1 and 6.

Important note: don’t create a new Random object every time you want to generate a random number! If you need to generate a bunch of random numbers, make one Random object and call nextInt() on it repeatedly.
Be sure to compute the coolness parameter using floating-point arithmetic. For example, writing (3/4)*(emptySeats/numSeats) will not work since 3/4 == 0 due to integer division, and probably emptySeats/numSeats == 0 as well, assuming both variables have type int.
To use PoissonGenerator, create a PoissonGenerator object with the desired average as a parameter. Then you can call nextInt() repeatedly to generate e.g. for each time step, call nextInt() to find out how many groups will arrive at that time step.
If the objects of a class will all need to generate random numbers, you should make a random generator object (either Random or PoissonGenerator) which is a static field. This means there will be only a single copy of the field shared by all objects of the class. For example:
```
public class Foozle {
    private static PoissonGenerator pois = new PoissonGenerator(10);

    ...
}
```
In this example, all Foozle objects will have access to single, shared, poisson generator called pois.

What to implement

You have three main tasks to complete; there is no particular order in which you must complete them, since each ends up depending on one of the others in some way.

Fill in the missing methods in DiscreteEventSimulation (namely, run and scheduleEvent).
Fill in the implementation of Event.compareTo, so Events can be stored in a priority queue.
Create an IceCreamStore class which extends DiscreteEventSimulation.
- IceCreamStore should have whatever additional fields you need to keep track of the store (e.g. number of seats available, current profits, etc.), as well as appropriate methods for manipulating these fields. It does not matter what fields and methods you use, but some choices are better than others—good abstractions here will make your life easier when implementing the different Events.
- The constructor should take a maxTime along with whatever other parameters you need to initialize your fields. Note the constructor does not need to take a Queue as a parameter; you will create the initial queue as part of the constructor.
- The first thing the constructor needs to do is call super to run the constructor for DiscreteEventSimulation. Your constructor should look something like this:
```
public IceCreamStore(int maxTime, ...) {
    super(initialEventQueue(maxTime), maxTime);

    ...
```
- Now write an initialEventQueue method to create the initial queue of events:
```
private static PriorityQueue<Event> initialEventQueue(int maxTime) { ...  }
```
  initialEventQueue should create an empty priority queue, and then add some initial events to it as follows:
  - For each time step t from 1 to the max number of time steps, generate an integer using a PoissonGenerator with parameter 0.2. This will be the number of groups that arrive at time t.
  - For each group, pick a random number of people from 1–6 and create an EnterEvent for that group at time t, and add it to the event queue.
  Note, however, that this is slow: it takes time \(O(T)\) where \(T\) is the total number of time steps for the simulation. Alternatively, you can use the provided ExponentialGenerator which generates values from an exponential distribution. The exponential distribution corresponds to the time interval between events of a Poisson process. To generate events this way:
  - Create an ExponentialGenerator with parameter 0.2.
  - Initialize a variable double time with the output of the nextDouble method of the exponential generator.
  - As long as time is less than or equal to the total number of time steps:
    - Create an EnterEvent at time Math.floor(time).
    - Increment time by the exponential generator’s nextDouble.
  This creates one event per loop iteration, so it is \(O(E)\), where \(E\) is the total number of events. Since in our case there is on average one enter event for every five time steps, this will be faster than the previous method.
Create three classes called EnterEvent, OrderEvent, and LeaveEvent. Each should extend Event, which means you will have to override the processEvent method.
- Note the implementation of processEvent is given a DiscreteEventSimulation, but it will always in fact be an IceCreamStore. You should just cast it, like so:
```
IceCreamStore store = (IceCreamStore)sim;
```
Finally, you should implement an IceCreamMain class with a main method which sets up and runs a simulation.

Here is some sample output from my solution, when an ice cream store with 10 seats is simulated for 20 time steps. Yours does not have to look exactly like this, but should contain similar information.

-- Time 3 -------------------
A group of size 1 enters.
  They sit down.
  There are now 9 available seats.
  They will order in 4 minutes.

-- Time 7 -------------------
A group of 1 people is ready to order.
  #1 orders 1 scoops.
  They will leave in 9 minutes.

-- Time 9 -------------------
A group of size 2 enters.
  They decide your store is not cool.

-- Time 11 -------------------
A group of size 5 enters.
  They sit down.
  There are now 4 available seats.
  They will order in 4 minutes.

-- Time 13 -------------------
A group of size 6 enters.
  There are not enough seats.  They leave.

-- Time 15 -------------------
A group of 5 people is ready to order.
  #1 orders 3 scoops.
  #2 orders 1 scoops.
  #3 orders 4 scoops.
  #4 orders 3 scoops.
  #5 orders 4 scoops.
  They will leave in 13 minutes.

-- Time 16 -------------------
A group of size 1 leaves.
  There are now 5 available seats.

The store made a total profit of $5.

Evaluation

Simulate the ice cream store with every possible number of seats from 1 to 100. For each number of seats, run ten simulations of 5000 steps each, and average the results.

Make a graph of your results. What is the optimal number of seats? How do you think this depends on the “coolness parameter” \(C\)? What else might affect the optimal number of seats? Write up your answers in an evaluation document.