Abstract

This paper shows how graphical representations of spreadsheet queueing simulations can be used to give students a richer understanding of queues, provide a deeper understanding of simulation, and to serve as a lead-in to teaching queueing theory results. This paper builds on previous work on spreadsheet queueing simulation (Grossman, 1999), with the relevant material summarized in sections 2-4. The contribution of this paper (sections 5-8) is the development and use of "live" simulation graphs to provide a rich visual means for understanding queues and simulation, and techniques for using these graphs to motivate students, enhance their learning, and stimulate their interest in simulation.

The queueing simulation and their graphical representations were implemented in Microsoft Excel 97, and any specific instructions below refer to this software package.

1. Introduction

Queuing theory has always been a staple in survey courses on management science. Queueing theory is a powerful tool for computing certain steady-state queue performance measures. However, queueing theory is a poor vehicle for teaching students about what transpires in queues. For example, queueing theory tells us that, other things being equal, a queue with higher service time variability has longer average queueing time than a queue with lower variability. (Note that we are using "queueing theory" to mean what it usually means to students taking a survey course in management science: a small collection of formulas, typically for single server Markovian queues.)  However, queueing theory yields no insight into why this occurs.

Spreadsheet queueing simulation can be used to give students insight into queue behavior -- why queues form, why they persist, the role of variability, and the non-linear effect of increasing utilization on queue performance. In this paper we extend previous work on spreadsheet queueing simulation to provide a graphical representation of queue behavior. This graphical representation, which is connected to a live simulation model, allows students to articulate for themselves powerful insights about queue behavior. This enhances their intuition about queues and stochastic phenomena in general, and gives them a solid foundation to utilize queueing theory formulas when appropriate.

2. Approaches to Teaching Queueing

There are three approaches to teaching about queueing: analytical queueing theory, dedicated simulation packages, and spreadsheet simulation.

Queueing theory is widely taught in business school OR/MS survey courses, and students can use it to quickly compute a handful of steady-state performance measures for simple queueing systems. As presented in textbooks for management science survey courses (for example, Camm and Evans 1996, Winston and Albright 1997, or Ragsdale 1998), queueing theory is limited because the models are simplified to make them analytically tractable, the results apply only to steady-state behavior, and the number of performance measures that can be computed is small. Because deriving results using queueing theory models requires mathematics beyond the scope of the survey course, they are presented as black box formulas, and students do not gain the insights that OR/MS professionals obtain by studying the underlying theory.

Steady state queueing theory results are not particularly useful for understanding what actually transpires in queues: their dynamics, the effect of variability, human behavior while waiting in line, and such important technical issues as the role of initial conditions and the distinction between transient and steady-state behavior.

Simulating queues using dedicated software packages is flexible, powerful and widely used. It is often the best technology for computing quantitative results. Many simulation packages are available, such as SLAM, GPSS, Extend+, and Arena. However, simulation packages hide the mechanics of queues, are expensive and time-consuming to learn, and are not widely used in survey courses on OR/MS, although Liberatore and Nydick (1999) argue that they should be.

3. Overview of Simulating Queues in Spreadsheets

Any spreadsheet model can be simulated using techniques that can be found in survey textbooks such as Ragsdale (1998) or Winston and Albright (1997). There are three classes of spreadsheet simulation models (Evans and Olson, 1998), activity-driven, event-driven, and process-driven, each of which can be used for queueing simulation.

An activity-driven simulation describes the activities that occur during fixed intervals of time (for example, an hour, day, or week), typically using one row of the spreadsheet for each time interval. The activity-driven approach (often used in textbook inventory models) seems to have first been used for queueing by Clauss (1996) for ship unloading. However, we think this approach oversimplifies most queueing systems, unless the simulation time intervals are made very small - which makes the spreadsheet model very large.

An event-driven simulation describes the changes in the system at the moment of each stochastic event, typically using one row of the spreadsheet for each event. This approach was apparently first used for queueing by Winston (1996) for a single-server queue. Evans and Olson (1998) describe a similar model . The event-driven approach has technical advantages of efficiency and flexibility, but it is not good for teaching because it obscures the customer experience of queues, and it is less intuitive than the process-driven approach.

A process-driven simulation (Figure 1) models the logical sequence of events for each customer, typically using one row of the spreadsheet for each customer. This approach was apparently first used for queueing by Chase and Aquilano (1992), who present a model of two serial single-server queues with zero queue size. Process-driven simulation was first described in a management science textbook by Plane (1994) for a model of a single-server queue. Grossman, Tran, and Ursu (1997) developed prototypes of multiserver process-driven models, including balking, reneging, and multi-server serial queues. Hesse (1997) extends Chase and Aquilano's model by allowing the second queue to hold one customer. Camm and Evans (1996) and Lawrence and Pasternack (1998) contain single-server process-driven models. Evans and Olson (1998) describe one- and two-server process-driven models. Grossman (1999) discusses in detail the use of process-driven spreadsheet queueing simulations. Evans (2000) uses a single-server process-oriented queueing model similar to Figure 1. He presents live graphs of average performance measures, including average number in queue, average percent idle time, and average waiting time per customer, and indicates that individual replications demonstrate different times to converge to the long-term average value.

Figure 1: A two-server queueing simulation template. The entries in bold are included on the template. Students use the bold entries to compute the italicized entries.

4. Process-Driven Spreadsheet Queueing Simulation

A process-driven spreadsheet queueing simulation (Grossman 1999) uses one row for each customer. We provide students with a paper template of the spreadsheet (Figure 1) with all cells except interarrival times and service times blank and work with them to fill out the template, computing for each customer the arrival time, service start time, end time, wait time, and so forth. This by-hand simulation insures that every student understands how the model functions.

In the spreadsheet model, the user enters the start time and end time of the simulation. The user programs probability distributions for interarrival time and service time. The spreadsheet model samples the distributions and computes the values shown in Figure 1. A screen shot of the spreadsheet is in Figure 2. Details of how these models are programmed and instructions for downloading spreadsheet queueing simulation template files can be found in Grossman (1999).

Figure 2: interactive version (opens new window; requires Internet Explorer 4.01 or later)

We now discuss the key idea of this paper, which is to represent graphically the results of a spreadsheet queueing simulation such as the one shown in Figure 2.

5. Graphical Representations of a Spreadsheet Queueing Simulation

We have integrated two graphical representations with the spreadsheet queueing simulation templates. These graphs are "live" in the sense that when the spreadsheet is recalculated (for example, by pressing the F9 key in Microsoft Excel) the graphs instantly change to reflect a new replication. We refer to the two representations as the customer graph and the server graph. For each graph, we discuss the form of the graph and how it can be programmed. In the Appendix we indicate how spreadsheet queueing simulations containing these graphs may be downloaded.

5.1 The Customer Graph

Figure 3 shows the "customer graph". The horizontal axis measures time. The vertical axis displays the customer number, with customer 1 the first to arrive, customer 2 the second to arrive, etc. (column A of Figure 2). A two-color horizontal bar represents the experience of each customer. The left hand portion of the bar represents the customer's waiting time (this is absent if the customer does not wait). The right hand portion represents the customer's service time. The left edge of the bar is placed at the customer's arrival time (column C of Figure 2) to the system. The separation between the colors is the start of the customer's service (columns E and G of Figure 2). The right edge of the bar is the time of end of the customer's service (columns F and H of Figure 2).

In contrast to animated simulation packages, the customer graph shows the entire evolution of the system on one graph.

Figure 3: The Customer Graph

When the simulation is replicated (that is, the spreadsheet is recalculated, by pressing the F9 key), the customer graph is updated instantly and automatically. The updated graph reflects new samples from the interarrival and service time distributions, and the corresponding customer arrival times, service start times, and service end times.

5.2 The Server Graph

Figures 4 shows the "server graph" (a Gantt chart) corresponding to the same replication as Figure 3. The horizontal axis measures time. The vertical axis shows the server index. The server graph represents each server by a horizontal bar whose length equals the duration of the simulation. Each server bar is divided into sections whose color indicates whether the server was busy (serving a customer) or idle during that time interval. The busy sections are broken up by vertical lines to show when the server finished serving one customer and immediately began serving the next customer.

Figure 4: The Server Graph

Like the customer graph, the server graph is updated instantaneously when the simulation is replicated (that is, the spreadsheet is recalculated). 

Figure 5 shows both the customer and server graphs for three replications.  When viewed in a web browser, the Figure cycles automatically through the three replications.

We use spreadsheet queueing simulation graphs to teach several advanced topics to business students. The graphs have proven useful for an intuitive proof of Little's Law, to teach the craft skill (Powell 1998) of cleaning flawed data, and for linking microscopic features of queues (for example, arrival times of individual customers) with macroscopic measures (for example l, the average arrival rate to the system), and for understanding non-linear changes in queue performance as utilization increases.

7.1 Little's Law

The idea for the customer graph originally came from a diagram that is sometimes used to derive Little's law - for example, see Figure 2.3 in Kleinrock (1975). Our informal derivation goes as follows. Define A(t) to be the cumulative number of arrivals up to time t, D(t) to be the cumulative number of departures up to time t and L(t) = A(t) - D(t) to be the number in system at time t, as shown in Figure 6.

Figure 6: Informal derivation of Little's law.

Then the average arrival rate of customers is

Now let

We now see that the average system time of a customer is

The average number of customers in the system is

Combining (1), (2), and (3) we see that

of us has used this informal derivation in a 4th year undergraduate business course for a few years. The better students usually notice, and point out, that equation (2) is only approximately true, unless t is chosen so that L(t) = 0, that is, the system is empty at time t. Otherwise, F(t) will not include all of the system time for the last few arriving customers. This, and the implicit assumption of first-in-first-out, is what makes the derivation informal.

7.2 Cleaning Data and Checking Assumptions

One very real problem that anyone who tries to apply queueing theory is often faced with is imperfect data. Figure 7 shows a particularly troublesome part of a real dataset that one of us has used as the basis for an assignment. The Figure shows the times at which customers arrived to a "water kiosk" in a third world country, entered service ("arrival at tap"), and departed after receiving service. Unfortunately, many of the numbers are missing. Some students might have seen examples of imperfect data sets in a prior statistics course. If the data set can be thought of as consisting of several independent draws from the same distribution, then one option is to simply remove the missing observations from the data set. Here, the situation is more complicated - one cannot simply remove a customer with one or more missing numbers from the dataset, because that customer may interact with other customers in important ways. The choice is really between modifying the data set intelligently or not using the data set at all. The option to use the data set after removing all missing observations is not realistic in this case.

Figure 7: Imperfect transactional data for a water kiosk.

Some of the missing data are easy to estimate, particularly the arrival times. For example, a reasonable estimate for the missing arrival time for customer 72 would be the average of the arrival times of customers 71 and 73. When several arrival times in a row are missing (such as for customers 74-76) one can estimate the missing times such they are equally spaced between the last known arrival time and the next known arrival time. In addition, one will have to make sure the arrival time of a customer is always less than or equal to the "arrival at tap" time for that customer, if it is known.

The missing departure times can also be estimated fairly easily. One can estimate the average service time, using customers for which both "arrival at tap" and "departure time" are available. Then one can estimate the missing departure times as "arrival at tap" plus the average service time (2 minutes and 34 seconds in this case).

The tricky part is estimating the missing "arrival at tap" times. These should be estimated in a way that is consistent with the queue discipline (first-come-first-serve) and the number of servers (two). This is where the customer graph can help.

Figure 8 shows a customer graph for the data shown in Figure 7, after the missing arrival times and departure times have been estimated as explained above. The "arrival at tap" times have been set equal to the arrival time of the respective customers, to provide initial estimates.

Figure 8: Customer graph for the water kiosk data, with initial estimates for missing data.

A close look at Figure 8 shows that the "arrival at tap" time for customer 72 must be adjusted from its current value of 8:26:30. A server does not become available until 8:27, when customer 70 departs. The next customer with missing "arrival at tap" data is customer 74. From the queueing graph, we see that this customer will not have access to a server until customer 72 departs, at 8:30. Continuing in this fashion we can replace all the missing "arrival at tap" times with estimates that are at least consistent with how the system operates.

It is even possible to do the estimation graphically in Excel, by grabbing the vertical line corresponding to an "arrival at tap" time and moving it.  When one does this, Excel brings up the goal seek dialog box, and asks what "changing cell" to use.  Enter the cell with the missing "arrival at tap" data and click OK, and Excel will adjust the data to correspond to the new position of the vertical line in the graph.  Some students enjoy applying this procedure because the can concentrate on the graphical representation rather than precise numbers on the time scale, but for other students the complexity of the procedure is an impediment. 

The customer graph can also be used to examine the validity of assumptions about how the system operates. For example, we notice that customer 74 departs from service before customer 73 enters service. So the queue does not operate in a truly first-come-first-serve manner at all times (and this is not an artifact of how we estimated the missing data - the "arrival at tap" for customer 73 and the departure time of customer 74 were both recorded). The customer graph also shows that customers 71, 73, and 76 are all receiving service simultaneously, despite the system having only two servers (again, this is based on numbers that were actually recorded, not our estimates of missing number). Apparently, customers "shared servers" at certain times.

It is easy to throw one's hands up in frustration and ask for better data, but in reality that might not be an option. Customer graphs can help pre-process the data in an intelligent way to allow the best analysis that is possible, given the quality of the data. Queueing graphs also help the analyst see whether assumptions about how the system operates are supported by the data.

7.3 Linking Transactional Data to Macroscopic Parameters

The customer graph displays almost all there is to know about a queueing system in one picture. To use a term coined by Edward R. Tufte [Tufte, 1983], the customer graph has a high data-ink ratio. The average arrival rate to the system (l) can be visualized as the (average) slope of the A(t) curve in Figure 7, and estimated numerically as A(t)/t as discussed above. The number in system at any time t can be visualized as the vertical distance between A(t) and D(t). The average number in system (L) can be visualized as the average vertical distance between A(t) and D(t). Hence, the customer graph can be used to illustrate both such macroscopic parameters as l and L, and microscopic transactional data (arrival time, waiting time, service time) for every customer -- all in one picture. This can help to explain the link between the detailed behavior of a queue over time (which students usually understand easily) and average measures of performance, such as L and W (which students usually have more difficulty interpreting).

7.4. The Effect of Increasing Utilization on Queues

As a first order approximation, many students believe intuitively that utilization less than 100% means that no queue should form. The customer graph allows them to see that a queue does form if there is variability in arrivals or service, and the size of the queue increases non-linearly as utilization gets close to 100%. They can articulate for themselves why this is so.

8. Benefits of Spreadsheet Queueing Simulation Graphs

The use of spreadsheet queueing simulation graphs can enhance student understanding of queues. By providing a rich visual representation of the complete evolution of a queue, complex queue behavior can be presented to students so that they can articulate the insights themselves, rather than relying on the instructor for wisdom. The ease with which replications can be made and instantly presented on the graph makes the basic concepts of simulation very clear to students. It also shows how simulation (in a spreadsheet or in dedicated simulation software) can be used to model complex business processes.

Graphical spreadsheet queueing simulation is a strong lead-in to traditional queueing theory results. Students develop intuition regarding queues in general. They easily grasp the distinctions among one arrival, one particular day's queue (or one replication), average performance in a single day, and average performance across many days. It is easier for students to understand the meaning of queueing theory results, and to appreciate the limitations of the average results that most queueing theory models yield. In turn, the hard work required to implement a spreadsheet queueing simulation makes them appreciate the speed with which queueing theory provides results.

Finally, spreadsheet queueing simulation increases student interest in learning simulation software (and taking elective courses in simulation). Business students find spreadsheet simulation of queues to be inherently interesting. This makes them excited about simulation in general. However, programming spreadsheet queueing simulations, even with the templates in Grossman (1999) can be cumbersome. When we demonstrate a simulation package such as Arena and indicate that a queue which requires hours of spreadsheet programming can be programmed in under 1 minute in Arena, students take note. Simulation elective enrolments have increased since we started using spreadsheet queueing simulation in the required course.

9. Conclusions

We discussed the use of spreadsheet queueing simulation graphs to enhance student understanding of queues and of simulation. Use of this technique seems to increase student interest in elective courses in simulation.

We look forward to using the server graph in research work with call center managers exploring the possibility of mixed inbound-outbound call centers where outbound calls are made during periods of idleness in a pure inbound call center. It is difficult to understand and communicate the size and stochastic nature of the time windows for outbound calls. The server graph provides a powerful stochastic representation of these time windows.

10. Appendix

10.1 Software Downloads

A family of spreadsheet queueing templates with customer and server graphs for queues with balking, reneging, and both balking and reneging can be downloaded from  http://www.bus.ualberta.ca/aingolfsson/simulation/ [local copy] .

10.2 VBA Code

The following VBA code scales the time axis on the customer and server graphs in a way that we find more pleasing than Excel's default scaling.  The code needs to be associated with the worksheet that contains the graph.  The name of the worksheet does not matter.  Copies of this same subroutine can be associated with several worksheets, if desired. 

Cells with the names start_time and close_time must exist somewhere in the workbook. The code scales the value axis of every chart in the worksheet it is associated with.

Private Sub Worksheet_Calculate()
Dim N As Long, I As Integer
Dim X As Double
N = ActiveSheet.ChartObjects.Count
' Find open time in minutes
X = ([close_time] - [start_time]) * 24 * 60
' Find how many 5 minute intervals in open time.
' Then divide by ten and take integer value.  The result,
' times 5 minutes, will be the interval length.  Therefore,
' there will be approximately ten intervals, and each interval
' will be a multiple of 5 minutes.
X = Int(X / 10 / 5 + 1)
For I = 1 To N
    With ActiveSheet.ChartObjects(I).Chart.Axes(xlValue)
        .MinimumScale = [start_time]
        .MaximumScale = [close_time]
        .MajorUnit = 1 / 24 / 60 * 5 * X
    End With
Next I
End Sub

11. References

Camm, J. D. and J. R. Evans (1996). Management Science: Modeling, Analysis and Interpretation, South-Western College Publishing, Cincinnatti, OH.

Chase, R. B. and N.J. Aquilano (1992), Production and Operations Management, sixth edition, Richard D. Irwin, Chicago, IL.

Clauss, F. J. (1996), Applied Management Science and Spreadsheet Modeling, Duxbury Press, Belmont, CA.

Evans, J. R. and D. L. Olson (1998), Introduction to Simulation and Risk Analysis, Prentice Hall, Upper Saddle River, NJ.

Evans, J.R. (2000), "Spreadsheets as a Tool for Teaching Simulation", INFORMS Transactions on Education, Vol. 1, No. 1, http://ite.informs.org/Vol1No1/Evans/index.php

Grossman, T. A., Tran, K. and Ursu, G.D. (1997), "Prospects and techniques for dynamic discrete event simulation in spreadsheets," Proceedings of the International Association of Science and Technology for Development International Conference on Applied Modelling and Simulation, Banff, Canada, July, available at http://www.ucalgary.ca/~grossman/simulation/history.htm.

Grossman, T. A. (1999), "Spreadsheet Modeling and Simulation Improves Understanding of Queues," Interfaces vol.29, no.3, pp.88-103.  Templates available from http://www.ucalgary.ca/~grossman/simulation/ .

Hesse, R. (1997), Managerial Spreadsheet Modeling and Analysis, Richard D. Irwin, Chicago, IL.

Kleinrock, L. (1975), Queueing Systems, Volume 1: Theory, John Wiley and Sons, New York, NY.

Lawrence, J. A. and B.A. Pasternack (1998), Applied Management Science, a Computer-Integrated Approach for Decision Making, John Wiley and Sons, New York, NY.

Liberatore, M. J. and R. L. Nydick (1999), "Breaking the mold: A new approach for teaching the first MBA management science course," Interfaces, vol.29, no.4, pp.99:116.

Plane, D. R. (1994), Management Science, a Spreadsheet Approach, Boyd and Fraser, Danvers, MA.

Powell, S. G. (1998), "The studio approach to teaching the craft of modeling," Annals of Operations Research, vol. 82, no. 1, pp.29-47.

Ragsdale, C. T. (1998), Spreadsheet Modeling and Decision Analysis, second edition, South-Western College Publishing, Cincinnati, OH.

Tufte, E. R. (1983), The Visual Display of Quantitative Information, Graphics Press, Cheshire, CT.

Winston, W. L. (1996), Simulation Modeling Using @RISK, Duxbury Press, Belmont, CA.

Winston, W. L. and S. C. Albright (1997), Practical Management Science, Spreadsheet Modeling and Applications, Duxbury Press, Belmont, CA.

^ã INFORMS