Bar Simulation

One of the most common applications of priority queues is in the creation of simulations.

A discrete event-driven simulation is one popular simulation technique.

• Objects in the simulation model represent objects in the real world and are programmed to react as much as possible as the real objects would react.

A priority queue is used to store a representation of events waiting to happen.

• This queue is ordered based on the time the event should occur, so the smallest element will be the next event to be modeled (Min Heap).
• As an event occurs, it can spawn other events.
• These subsequent events are placed into the queue as well.
• Execution continues until all events have occurred or until a preset time for simulation is exceeded.

Imagine that you are thinking of opening a bar in San Mateo!

• You need to decide how large the bar should be, how many seats you should have, and so on.
• If you plan too small, customers will be turned away when there is insufficient space, and you will lose potential profits.
• On the other hand, if you plan too large, most of the seats will be unused, and you will be paying useless rent on the space and hence losing profits.
• So you need to choose approximately the right number, but how do you decide?

To create a simulation, you first examine similar operations in comparable locations and form a model that includes, among other factors,

• an estimation of the number of customers you can expect to arrive in any period of time,
• the length of time they will take to decide on an order, and
• the length of time they will stay after having been served.

Based on this, you can design a simulation.

The Software Gurus Bar

To see how we might create a simulation of our Software Gurus Bar, consider a typical scenario:

A group of customers arrive at the bar.

From our measurements of similar bars, we derive a probability that indicates how frequently this occurs.

• For example, suppose that we assume that groups will consist of from one to five people, selected uniformly over that range. In actual simulation, the distribution would seldom be uniform. For example, groups of size two, three and four might predominate, with groups of one and five being less frequent. We will start with uniform distributions and later you will modify appropriately.
• These groups will arrive at time spaced 2 to 5 minutes apart, again selected uniformly. Once they arrive, a group will either be seated or, seeing that there are no seats available, leave. If seated, they will take from 2 to 10 minutes to order and then will remain from 30 to 60 minutes in the bar.
• We know that every customer will order from three kinds of beer:
  • local beer, import beer, or special beer.

The bar makes a profit of
$2 on each local beer,
$3 on each imported beer and
$4 on each special beer.

The primary object in the simulation is the bar itself. It might seem odd to provide behavior for this inanimate object, but we can think of the bar as a useful abstraction for the servers and managers who work in the bar.

The bar manages two data items:

• the number of available seats and
• the amount of profit generated.

The behavior of the bar can be described by the following list:

• When a customer group arrives, the size of the group is compared to the number of available seats. If insufficient seats are available, the group leaves. Otherwise, the group is seated and the number of seats is decreased.
• When a customer orders and is served, the amount of profit is updated.
• When a customer group leaves, the seats are released for another customer group.

A (partial) java class description for SoftwareGurusBar is given below:

public class SoftwareGurusBar {
private int freeChairs = 50;
private double profit = 0.0;
private SimulationFramework simulation = new SimulationFramework();
public static void main(String[] args) {
SoftwareGurusBar world = new SoftwareGurusBar();
}
SoftwareGurusBar() {
int t = 0;
while (t < 240) { // simulate 4 hours of bar operation

t += randBetween(2, 5); // new group every 2-5 minutes
simulation.scheduleEvent(new ArriveEvent(t, randBetween(1, 5)));
} // group size ranges from 1 to 5 simulation.run(); System.out.println("Total profits " + profit); }
private int randBetween(int low, int high) {
return low + (int)((high - low + 1) * Math.random());
}

public boolean canSeat(int numberOfPeople) {
System.out.println("Group of " + numberOfPeople + " customers arrives at time " + simulation.time());
if (numberOfPeople < freeChairs) {
System.out.println("Group is seated");
freeChairs -= numberOfPeople;
return true;
} else System.out.println("No Room, Group Leaves");
return false;
}


private void order(int beerType) {
System.out.println("Serviced order for beer type " + beerType + " at time " + simulation.time()); // update profit knowing beerType ( left for you ) }

private void leave(int numberOfPeople) {
System.out.println("Group of size " + numberOfPeople + " leaves at time " + simulation.time());
freeChairs += numberOfPeople;
}


private class ArriveEvent extends Event {
private int groupSize;
ArriveEvent(int time, int gs) {
super(time);
groupSize = gs;
}

public void processEvent() {
if (canSeat(groupSize)) { // place an order within 2 & 10 minutes
simulation.scheduleEvent(new OrderEvent(time + randBetween(2, 10), groupSize));
}
}
}

private class OrderEvent extends Event {
private int groupSize;
OrderEvent(int time, int gs) {
super(time);
groupSize = gs;
}

public void processEvent() { // each member of the group orders a beer (type 1,2,3) for (int i = 0; i < groupSize; i++) order(1 + randBetween(1, 3)); // schedule a leaveEvent for this group // all the group leaves together ( left for you ) } }

private class LeaveEvent extends Event {
LeaveEvent(int time, int gs) {
super(time);
groupSize = gs;
}
private int groupSize;

public void processEvent() {
leave(groupSize);
}
}
}

The method randBetween(low, high) returns a random integer between the two given endpoints low & high.

The methods canSeat, order, and leave manipulate the profits and the number of chairs.

The execution of the simulation is controled by the simulation framework and the inner classes ArriveEvent, OrderEvent, and LeaveEvent which are described next.

A framework is reusable software that implements a generic solution to a generalized problem.

Principle: Applications that do different, but related, things tend to have quite similar designs

A framework is intrinsically incomplete

• Certain classes or methods are used by the framework, but are missing (slots)
• Some functionality is optional
  • Allowance is made for developer to provide it (hooks)
• Developers use the services that the framework provides
  • Taken together the services are called the Application Program Interface (API)

In the object oriented paradigm, a framework is composed of a library of classes.

• The API is defined by the set of all public methods of these classes.
• Some of the classes will normally be abstract

A framework is like the skeleton of an application

• It provides the structure for a solution, but none of the applicationspecific behavior

Our framework for simulations describes the features common to all discrete event-driven simulations, namely:

• the concept of a priority queue of pending events, and
• a loop that repeatedly removes the next event from the queue and executes it.

But note that the framework has no knowledge of the specific simulation being constructed.

To create a working application, certain key classes provided by the framework are used to create subclasses. These subclasses can provide the application-specific behavior.

In our simulation framework, the key class is Event. Three new types of events are created, corresponding to groups of drinkers

• arriving at the bar,
• drinkers ordering for beer, and
• drinkers leaving the bar.

Other frameworks you have already seen are AWT & Swing.

• To create a new application, you use inheritance to subclass from Frame (or JFrame), adding application specific behavior.

Frameworks can be created for any task that is repeated with a wide range of variations but that has a core of common functionality.

Rather than simply code a simulation of this one problem, we will generalize the problem and first produce a generic framework for simulations. At the heart of a simulation is the concept of event.

An event will be represented by an instance of class Event. The only value held by the class will be the time the event is to occur. The method processEvent will be invoked to execute the event when the appropriate time is reached.

The simulation queue will need to maintain a collection of various types of events. Each form of event will be represented by different derived classes of class Event. Not all events will have the same type, although they will all be derived from class Event.

Because a heap is a container that orders the elements it holds, we provide a basis for comparisons by having the class Event implement the Comparable interface.

This interface consists of only one method, compareTo. This method returns an integer result, which is 1 if the current value is less than the argument; 0 if they are equal; and 1 if the current value is larger than the argument.

We are now ready to define the class SimulationFramework, which provides the basic structure for simulation activities.

• The class SimulationFramework provides three functions.
  • The first is used to insert a new event into the priority queue,
  • the second runs the simulation,
  • and the third returns the simulation time, which is being held in a private data field.

public class SimulationFramework {
public void scheduleEvent(Event newEvent) { // put or addElement “newEvent” to the “eventQueue” // MinHeap Priority Queue ( left for you ) }
public void run() {
while (!eventQueue.isEmpty()) { // remove min element from priority queue (Min Heap) Event nextEvent = (Event) eventQueue.removeMin(); currentTime = nextEvent.time; nextEvent.processEvent(); // what do you see here??? } }
public int time() {
return currentTime;
}
private int currentTime = 0;
private FindMin eventQueue = new Heap(new DefaultComparator());
}

public abstract class Event implements Comparable {
public final int time;
public Event(int t) {
time = t;
}
abstract void processEvent();

public int compareTo(Object o) {
Event right = (Event) o;
if (time < right.time) return -1;
if (time == right.time) return 0;
return 1;
}
}

public abstract interface FindMin extends Collection;

/*
* FindMin - find smallest element in collection (priority queue);
*
* Method Summary
*
* void addElement(java.lang.Object value)
* add a new value to the collection
*
* java.lang.Object getFirst()
* yields the smallest element in collection
*
* void removeFirst()
* removes the smallest element in collection
*/

public class DefaultComparator implements java.util.Comparator;
/*
* DefaultComparator - comparator object for values that satisfy
* comparable interface;
*
* Method Detail
*
* public int compare(java.lang.Object left, java.lang.Object right)
* determine order of two object; -1, 0 or 1
* Specified by:
* compare in interface java.util.Comparator
* Parameters:
* left - first object
* right - second object
* Returns:
* -1 if left less than right, 0 if equal, 1 otherwise equals * * public boolean equals(java.lang.Object obj)
* Specified by:
* equals in interface java.util.Comparator
* Overrides:
* equals in class java.lang.Object
*/

The following tasks are left for you to complete this project:

• Implement the Priority Queue ADT based on the MinHeap Data Structure
• Understand the given code and complete the tiny sections of code marked with (left for you)
• Get it to run
• Modify the simulation so it uses the weighted discrete random number-generated function described on the next slide.
  • Select reasonable numbers of weights for the type of beer ordered by the drinkers and for the sizes of the groups of drinkers
  • Compare a run of the resulting program to a run of the given program (based on uniform distribution)
• Add creative & relevant graphics and/or animations are for a bonus (not easy in this context is it ?!?!)

One alternative to the use of uniform distribution is the idea of a weighted discrete probability. Suppose that we observe a real bar and note that 15% of the time they will order local beer, 60% of the time they will order imported beer, and 25% of the time they will order special beer. This is certainly a far different distribution from the uniform distribution we used above (33% of each type of beer). In order to simulate this new behavior, we can add a new method to our class random.

• Add a method named weightedProbability to the class SimulationFramework. This method will take as argument a vector of unsigned integer values. For example, to generate the preceding distribution, you will pass to the weightedProbability method a vector of three elements containing 15, 60, and 25.
• The method first sums the values in the array, resulting in a maximum value. In this case, the value would be 100. A random number between 1 and this maximum value is then generated.
• The method then decides in which category the number belongs. This can be discovered by scanning through the values. In our example, if the number is less than 15, the method should return 0; if less than or equal to 75 (15 + 60), return 1; otherwise return 2.