AiS Challenge 2003 STI :: Coffee Shop Service Simulation

1. Real Problem: To assess the impact (cost and benefits) on service of different staffing strategies at a high-volume coffee shop.

   • Area of Science: Probability/Queuing Theory

   • Background:Many of the modern, high-volume coffee shops (e.g. Starbucks) take great pains to ensure a consistent level of service. A key measure of this objective is the time required to take and fill a customer's order (i.e. the time between the moment a customer enters the waiting line, and the moment the customer leaves the counter with his/her order). Clearly, one of the surest ways to achieve very rapid turnaround is to have many employees on hand at all times, ready to take and fill orders; however, this would be prohibitively expensive - and, in any event, there are often other constraints on throughput (e.g. the number of espresso machines). At the other end of the spectrum, the shop could be staffed minimally, which would in turn minimize staffing costs; during peak times, however, the time spent waiting in line could grow to an unacceptable level, and a shop adopting such a strategy would risk losing customers (besides almost certainly exceeding the waiting and service time standards) at those peak times.

     In order to assess the impact of different strategies, and recommend rational staffing levels, we must take as much as possible of the following into account:

     • The average rate at which customers enter the shop - including, ideally, a breakdown of customer order types (e.g. regular coffee vs. espresso) - at different times of the day;
     • The time required for a coffee shop employee to serve each of the different order types, and the amount (and type) of variation in these times;
     • Shift staffing options (i.e. the limits - upper and lower - on the length of a shift);
     • The hourly cost of an employee (including the impact on cost of different shift lengths);
     • Other limiting factors (e.g. the number of espresso machines).

   • Why is this a Computational Science project? Although Queuing Theory (the study of waiting and processing times in service systems) has methods for examining such systems analytically, these methods quickly become extremely cumbersome (to the effective point of intractibility) as the systems become even moderately complex. An alternative to a pure analytical approach is to employ Monte Carlo simulation (simulation, usually with a computer, of a very large number of experimental trials) to examine the behavior of a simulated version of the system, and evaluate alternative configurations.

2. Working Problem: We will examine a simplified version of the problem, with the following characteristics:

   • A standard service policy: 95% of all customer orders will be filled within 3 minutes of the customer joining the line;
   • A single average arrival rate (20 customers/hour), based on a Poisson arrival process;
   • As a consequence of the previous point, no variation in staffing level over the course of the day - we will simply examine different, constant levels;
   • No distinction between different types of customer orders, and the time required to service each order distributed according to the Exponential distribution (with an average service time of 2 minutes);
   • Partly as a consequence of the previous point, we will not distinguish between types of employees; each employee costs the same, per hour, as any other employee.

   Using the above assumptions, we will simulate the effectiveness of different staffing levels in meeting the standard service policy.

3. Mathematical Model: When arrivals into a queuing system are independent (i.e. the fact that a person or party enters the shop during a given minute has no effect on whether another party enters the shop during any other minute), the arrival process is said to be a Poisson process, and the time between arrivals is a random variable which follows the Exponential distribution. This distribution is described by the following probability distribution function:

   f(t) = λe^-λt

   ¹/_λ = average interarrival time

   The same distribution will be used for the service time (the time from the moment the customer's order is taken to the moment the order is filled), but it is customary to employ μ (instead of λ) for the service rate:

   f(t) = μe^-μt

   ¹/_μ = average time to service an order

4. Computational Model: There are many ways to implement a Monte Carlo simulation of the working problem described above. Almost all general purpose programming languages (e.g. C/C++, Java, BASIC, FORTRAN), as well as a number of commonly-used scripting languages (e.g. Javascript, VBScript) and application-hosted languages (e.g. Excel with VBA) can be used successfully. (There are special-purposes languages as well, specifically designed for such simulations; we will not be using any of these.) The usual approach is to program the simulation as a "discrete event simulation", where a variable is used to keep track of the current simulation "clock", and a pseudo-random number generator is used to calculate the times of the upcoming simulation events (e.g. customer arrival, completion of an order for one of the customers currently being served). At each iteration of the simulation, the clock is advanced to the time of the earliest upcoming event, the simulated statistics (e.g. average waiting line length, average waiting time, etc.) are updated, and the simulation state is modified as necessary (e.g. length of the waiting line increased by one when a customer arrives).

   Most general-purpose programming languages provide variations on a very simple pseudo-random number generator, which generates numbers from the Uniform distribution, on the interval [0,1). Since our simulation will need to generate numbers from the Exponential distribution, we will need to transform the numbers returned from the Uniform distribution, as follows:

   t_arrival = -ln(1-u_arrival) / λ

   t_service = -ln(1-u_service) / μ

   u_arrival = number in interval [0,1), returned from uniform pseudo-random number generator, for arrival time

   u_service = number in interval [0,1), returned from uniform pseudo-random number generator, for service time

   An example of a similar Monte Carlo simulation, but based on a process with a number of servers in series, can be viewed here. This example is constructed entirely in Javascript; because it relies extensively on Dynamic HTML for displaying the results during the simulation, Internet Explorer v5.5 or higher is required.

5. Results/Conclusions: We will perform "what if" scenario analysis of different staffing levels, to find the minimal level which satisfies (based on the simulation results) the standard service policy. If time permits, we will also examine the impact of relaxing or tightening the tolerance included in the service policy (e.g. changing the "95% of all customers" portion of the rule to 90% or 99%).