Chapter 7

Useful Tools and Simulation Methods

This chapter discusses some tools that can simplify waiting line analyses and the basic simulation approaches for evaluating variances in waiting line behavior and analyzing situations for which no closed-form mathematical solution yet exists. Specific topics include the following:

• Little’s Law
• Waiting line data collection
• Probability distribution determination
• Simulation models
  • Excel tools
  • Single-channel models
    • M/M/1 model
    • M/G/1 model
    • G/M/1
    • G/G/1 model
  • Multiple-channel models
  • Single-channel, multiple-phase manufacturing model
• Random number approximations of probability distributions

Little’s Law,¹ L = λW or L_q = λW_q, is arguably the most useful concept that waiting line analysts have in their toolboxes. It holds true regardless of the probability distributions used to describe the arrival and service rates for a waiting line; it is also independent of the number of servers used. Its primary value is that data for determining L, L_q, and λ can be collected easily in most businesses, which allows easy calculations of W and W_q. Knowing all these values then allows an easy determination of the average service time for many of the waiting line models.

The following discussion on collecting waiting line data gives some examples of the versatility of Little’s Law.

Waiting Line Data Collection

Having actual operational data about your business is necessary for being able to use queuing analysis models effectively. In many situations, the classic exponential distributions for arrival and service rates do not represent your business as well as another standard probability distribution or a discrete distribution tailored to fit your typical business conditions. To assess the need for choosing an alternate probability distribution for either the arrival rate or the service rate, you need to collect enough data to guide you in that choice and provide some of the average performance values for the appropriate waiting line model.

One class exercise that I have asked my process management students to do is to collect data while observing the waiting line behavior at various campus coffee shops. They are expected to analyze that data and use it in a subsequent waiting line simulation exercise. A sample data sheet from that exercise is shown in Figure 7.1. While these student exercises are specific to coffee shops, the general data collection and simulation approach is applicable to a wide variety of waiting line scenarios. We will discuss their work in more detail in the examples presented in this chapter.

We will collect data only about line lengths and arrival rates. Observing actual waiting and service times is much more difficult and not needed because we can derive waiting times from the line length and arrival data. Service times are a bit trickier but can be estimated for most scenarios once we have the waiting time values. For good data, the following guidelines should be followed:

• Select a suitably short collection period for each pair of line length and arrival rate values. For low arrival rates, where there is typically enough time between arrivals to count the number of people in the facility being served and waiting for service, it is better to record the amount of time between each arrival to determine the arrival rate. If the arrival rate is too fast to count the number of customers in the facility between arrivals, then select a fixed time segment that is at least three or four times as long as it typically takes to count the number of customers in line. Record the number of arrivals during each period and the number of customers in the facility at the end or the beginning of each period. For the student’s coffee shop exercise, the fixed time period was 5 minutes.
• Hint: It is useful to have one person note the arrivals and another person count the customers. Trying to do both at the same time can be challenging for a single person, particularly if the business is busy. Mechanical counters and stopwatches are useful but unnecessary tools if you have a good watch and paper and pencil for making tally marks.
• If you want to determine average service times, note the number of servers on duty during each recording period. If not, you can ignore this information (more about this decision later).
• Unless you have good reason to believe that your arrival rate is relatively constant throughout the working day, record the starting time for each record period. This is not usually required for production lines, where the production schedule normally ensures a relatively steady arrival rate.
• If your business has different service classes (express lanes, commercial customers only, etc.), be sure to collect data separately for each class if you want to derive service time and arrival rates per class. In this case, for more accurate data, avoid having servers in one class serve customers from another class when those servers have an idle period.
• Pay close attention to the measurement units. In Figure 7.1, the average line length is independent of the length of the collection period. Not so for the average arrival rate shown; that average is dependent on the number of arrivals per period. The form also clearly states that the line values are for L, not L_q.

Discrete Probability Distributions

A valuable characteristic of simulation models is that they can work with either continuous distributions, like the ones we have discussed for various queuing models, or discrete distributions based on collections of actual data. The difference in the approach is that we use random numbers to calculate the values for the simulation from the mathematical functions that describe the continuous distributions, or we use those random numbers in a lookup table to select a discrete value from the histogram of the data collection. Examples 7.2 and 7.3 illustrate these two approaches using some more data collected from my coffee shop data collection assignments.

Simulation Models

Setting up simulation models for waiting lines is simpler than for some other types of simulations. Because waiting lines are time based with a defined sequence of steps or phases, all the simulation has to do is keep track of when each customer or item enters the queue and how much time a customer spends at each step in the waiting line sequence. The tricky part is that the movement of customers that enter the queue later can be affected by the movements of customers who entered the queue earlier. When the time between successive arrivals is short, the probability of this occurring obviously increases.

Figure 7.6 shows an example of the sequence of events for a simple M/M/1 model with one service operation. The vertical axis represents the number of customers who have entered the queue, and the horizontal axis represents the passage of time. A horizontal bar represents each customer; the length of the bar represents how long the customer spent in the service system, with the left end representing when he or she entered and the right end when he or she left. This bar is normally divided into two parts, one shaded gray to represent how long the customer waits in the queue for service and the other colored black to represent how long the service took. The entry times are determined by the arrival distribution associated with the type of queue being simulated, and their service times are determined by the service distribution appropriate for the service being simulated. Of interest in Figure 7.6 are the conditions when there are no customers in the system, indicated by the arrow labeled A, and when there are five customers in the system, indicated by the arrow labeled B.

If Figure 7.6 is compared to the look of a typical computer spreadsheet, you should be able to recognize the similarities where the rows and columns of the spreadsheet could be used to represent the activities taking place and determine some of the performance values. Figure 7.7 shows an example of how this can be done and provides a template for a basic simulation module for waiting line analysis.

Like the diagram in Figure 7.6, the simulation model template in Figure 7.7 addresses each customer or unit in an order going down the sheet and determines the various performance times in an order moving toward the right. The Arrival Time column is where the entry time for the customer is entered in the template. This time is determined by adding the interarrival time for customer n to the arrival time recorded for customer n – 1. The interarrival time is chosen at random from the arrival distribution chosen for the model using an appropriate method that determines an interarrival value based on a random number input generated by the spreadsheet program. A similar method is done to select a service time for a customer using a different random number. When using continuous probability distributions, the method uses the random number to calculate a corresponding value according to that distribution as described in appendix D. When using discrete probability distributions, the method uses the random number to select a corresponding value using a lookup table similar to that shown in Figure 7.5.

The Service Starts column determines when the service begins for customer n by comparing customer n’s arrival time with the Service Ends time for customer n – 1. If that time is greater than customer n’s arrival time, it becomes the start of service time for customer n; if not, the start of service time is the same as customer n’s arrival time. The Service Ends column is the randomly chosen service time for a customer added to that customer’s start of service time.

Hence the arrival times in the simulation are solely determined by the arrival distribution chosen for the simulation. But the service start and end times are affected by both the previous customer’s service end time and the service distribution chosen.

W_q is merely the difference between a customer’s arrival time and when service starts for that customer. W is merely the difference between the service end time and the arrival time. Slack time is any positive difference between the service end time for customer n – 1 and the start of service for customer n (occurs only when customer n arrives after the service for customer n – 1 is completed). This time is idle time and can be used to determine P₀ for the simulation.

Obtaining L is a bit tricky but not difficult. If you observe the situation indicated by arrow B in Figure 7.6, you can see that the number of people in the system after customer n arrives is the number of customers, including customer n, whose start of service times are greater than customer n’s arrival time. So all you have to do is count the number of service start times for customers n, n – 1, n – 2, n – 3 . . . 3, 2, and 1 that are greater than the arrival time for customer n. If you desire an L_q result that indicates what a potential customer would see when entering your business, delete customer n in your L_q calculations. The Excel COUNTIF function is very useful for the L determination. Count the range of cells containing the service completion times for all the previous customers using the following criteria statement in the COUNTIF expression:

There is an example in appendix D of using the COUNTIF function for the results shown in Figure 7.8.

You should see that this model works for all choices of arrival and service distributions. All you need to do is alter the algorithms for selecting arrival times and service times to fit your chosen distribution. Hence, M/D/1, M/G/1, G/M/1, G/G/1, D/M/1, and D/G/1 models can be accommodated.

The last two models with deterministic (D) arrival distributions can be used to simulate appointment-based arrival distributions, such as the health-care situation discussed in Example 6.5. Using an exponential or Erlang distribution to describe service time, you can then evaluate different appointment durations by using constant interarrival times equal to those durations. You can even accommodate potential late or early arrivals by adding a small variation value to each interarrival time. That value could be normally distributed, or it could be based on a discrete distribution created from actual early or late arrival data.

Random Number Approximations of Probability Distributions

Many arrival and service distributions are in a form that allows the use of random numbers to select a value from the distribution in accordance with its probability of occurring. Random numbers generated by many spreadsheet programs are in the form of a decimal value varying from one significant digit greater than 0 to one significant digit less than 1, for example, 0.00000001 to 0.99999999. These values have a uniform distribution; that is, the probability of any random number occurring is equally likely. This means that they can be used as probability values without introducing any bias to the selection.

Consider the probability density function for the exponential distribution is given by for t ≥ 0, where α can represent either λ or µ, and t is the time between arrivals or successive service starts (same as service times). The cumulative distribution function for this probability density function represents the cumulative area underneath the curve represented by the probability density function as a function of t. This function is described by the equation

For an exponential distribution, a plot of the cumulative distribution function is the vertical inverse of the plot for the probability density function. That is, the first plot increases from 0 to a maximum value of 1, and the other plot decreases from a maximum value of 1 to 0. Equation 7.2 gives us the probability that the time between intervals will be t or less. Now if we could substitute a random number (RN) for f(t), in effect using the random number to represent a given probability value, we should be able to solve Equation 7.2 for the t value correlating to that probability value. The result is that we can use that equation to give us intervals of time using random numbers as the inputs:

Rearranging Equation 7.3, we first obtain . Then taking the natural logarithms of both sides gives us the result: –αt = ln(1 − RN). Solving for t, we arrive at the equation we want to use in our simulation model for obtaining an interarrival time or service time described by an exponential distribution.

Recognizing that (1 − RN) is also a random number with the same range of values,

Equation 7.4 is used to provide the results shown in Figure 7.8 for a simulation that uses the values collected for Examples 7.2 and 7.3. A list of other equations that have been derived for different probability distributions is provided in appendix D.

Finally, considering the basic module shown in Figure 7.9 as a building block for simulations with a set of inputs (arrivals) and a set of outputs (departing customers or completed items), you can mix and match these to address more complicated waiting line situations by observing a few rules, as follows:

1. Like state diagrams, each module can be considered as a state with inputs equaling outputs. The state of the module can be described by its inventory (line length).
2. Like the probability distributions that describe arrival rates and service times, each module’s internal actions are essentially independent of each other, provided that there is no sharing of resources (servers, equipment) with other modules.
3. When the outputs of a module are divided among two or more subsequent modules or when the inputs to a module come from more than one source, separate types of simulation mod-ules must be developed to manage this traffic, as illustrated in Figure 7.10. This is not difficult if the various input or output components can be defined by fixed percentages or known probability distributions.
4. Single-line configurations for multiple servers are easier to model than parallel-line configurations, but both require a traffic module, as shown in Figure 7.11a and Figure 7.11b. One directs the next customer in a single line to the next available server; the other distributes incoming customers to the available parallel lines according to whatever rule is desired. For example, in typical bank or governmental office applications the rule is likely to be to the parallel line with the least number of customers waiting in line. Another example is directing incoming customers according to their class or priority.
5. An advantage of simulation is that modules can have different service distributions, which are useful when simulating multiple-phase lines or customizing a multiple-server situation where not every server can be assumed to have the same service capability. For example, one can simulate the effect of dedicating one server to standardized services in a two- or three-server situation as compared to all servers handling the full range of services.
6. When one module’s output is the input to a following module, the arrival distribution for the following model is the same as the output distribution for the preceding model, as shown for the production line simulation in Figure 7.12. Note that the output distribution of a previous module is not the same as that module’s service time distribution unless the server in that module is continually busy, as may be the case in a production line situation.

It can be seen that spreadsheet implementations of these modules for different simulations can be pretty straightforward. For example, a multiple step production process can use the first few columns of the spreadsheet as shown in Figure 7.7 for the first step, the next set of columns for the second step set up in the same way as for the first step with the Service Ends column values for the first step also acting as the Arrival Time values for the second step and so forth. Finally, some useful references for further study about spreadsheet simulation methods are Laguna and Marklund (2005), chapter 6; Winston (2004); and Weida et al. (2001).