Chapter 69: Queuing Theory-The Mathematics of Waiting in Line


Overview

  • What factors affect the number of people and the time we spend waiting in line?

  • What conditions should be met before analyzing the average number of people present or the average time spent in a queuing system?

  • Why does variability degrade the performance of a queuing system?

  • Can I easily determine the average time a person spends at airport security or waiting in line at a bank?

We have all spent a lot of time waiting in lines, and you’ll soon see that a slight increase in service capacity can often greatly reduce the size of the lines we encounter. If you run a business, ensuring that your customers do not spend too much time waiting is important. Therefore, business people need to understand the mathematics of wait time, usually referred to as the queuing theory. In this chapter, I’ll show you how to determine the service capacity needed to provide adequate service.

  • What factors affect the number of people and the time we spend waiting in line?

  • In this chapter, we will consider queuing problems in which all arriving customers wait in one line for the first available service person. (To keep things simple, we’ll refer to service people as servers.) This model is a fairly accurate representation of the situations we face when we wait at a bank, at an airline ticket counter, or at the post office. By the way, the idea of having customers wait in one line started about 1970, when banks and Post Office branches realized that although waiting in one line does not reduce the average time spent waiting, it does reduce the variability of our time in line, thereby creating a “fairer” system.

  • Three main factors influence the time we spend in a queuing system:

    • The number of servers.  Clearly, the more servers, the less time on average we spend in line, and the fewer people on average will be present in the line.

    • The mean and the standard deviation of the time between arrivals.  (We call the time between arrivals interarrival time.) If the average interarrival time increases, the number of arrivals decreases, which results in shorter lines and less time spent in a queuing system. As you’ll soon see, an increase in standard deviation of interarrival times increases the average time a customer spends in a queuing system and the average number of customers present.

    • The mean and the standard deviation of the time needed to complete service.  If the average service time increases, we will see an increase in the average time a customer spends in the system and the number of customers present. As you’ll see, an increase in the standard deviation of service times increases the average time a customer spends in a queuing system and the average number of customers present.

  • What conditions should be met before analyzing the average number of people present or the average time spent in a queuing system?

  • When analyzing the time spent waiting in lines, mathematicians talk about steady state characteristics of a system. Essentially, steady state means that a system has operated for a long time. More specifically, we would like to know the value of the following quantities in the steady state:

    • W=Average time a customer spends in the system

    • Wq=Average time a customer spends waiting in line before the customer is served

    • L=Average number of customers present in the system

    • Lq=Average number of customers waiting in line

  • By the way, it is always true that L=(1/mean interarrival time)*W and Lq=(1/mean interarrival time)*Wq.

  • To discuss the steady state of a queuing system meaningfully, the following must be the case:

    • The mean and standard deviation of both the interarrival times and the service times changes little over time. The technical phrase is that the distribution of interarrival and service times is stationary over time.

    • (1/mean service time)*(number of servers)>(1/(mean interarrival time)). I’ll refer to this equation as Equation 1.

  • Essentially, if Equation 1 is true, we can serve more people per hour than are arriving. For example, if mean service time equals 2 minutes (or 1/30 of an hour), and mean interarrival time equals 1 minute (or 1/60 of an hour), Equation 1 tells us that 30*(number of servers)>60, or that the number of servers must be greater than or equal to 3 for a steady state to exist. If you cannot serve customers faster than they arrive, eventually you fall behind and never catch up, resulting in an infinite line.

  • Why does variability degrade the performance of a queuing system?

  • To see why variability degrades the performance of a queuing system, consider a one-server system in which customers arrive every 2 minutes and service times always equal 2 minutes. There will never be more than one customer in the system. Now suppose that customers arrive every 2 minutes, but half of all service times are 0.5 minutes and half are 3.5 minutes. Even though arrivals are totally predictable, the uncertainty in service times means that eventually we will fall behind and a line will form. For example, if the first four customers have 3.5 minute service times, after 12 minutes, we will have four customers waiting, which is illustrated in the following table.

    Open table as spreadsheet

    Time

    Event

    present after event

    0 minutes

    Arrival

    1 person

    2 minutes

    Arrival

    2 people

    3.5 minutes

    Service completed

    1 person

    4 minutes

    Arrival

    2 people

    6 minutes

    Arrival

    3 people

    7 minutes

    Service completed

    2 people

    8 minutes

    Arrival

    3 people

    10 minutes

    Arrival

    4 people

    10.5 minutes

    Service completed

    3 people

    12 minutes

    Arrival

    4 people

  • Can I easily determine the average time a person spends at airport security or waiting in line at a bank?

  • The Model worksheet of the file Queuingtemplate.xlsx contains a template that you can use to determine approximate values for L, W, Lq, and Wq (usually within 10 percent of their true value). The worksheet is shown in Figure 69-1.

    image from book
    Figure 69-1: Queuing template

  • After entering the following data, the template computes Wq, Lq, W, and L. The parameters in cells B6:B9 can easily be estimated by using past data:

    • Number of servers (cell B5)

    • Mean interarrival time (cell B6)

    • Mean service time (cell B7)

    • Standard deviation of interarrival times (cell B8)

    • Standard deviation of service times (cell B9)

  • Here’s an example of the template in action. We want to determine how the operating characteristics of an airline ticket counter during the 9:00 A.M. to 5:00 P.M. shift depend on the number of agents working. In the Queuing Data worksheet in the file Queuingtemplate.xlsx, shown in Figure 69-2, I’ve tabulated interarrival times and service times. (Some rows have been hidden.)

    image from book
    Figure 69-2: Airline interarrival and service times

  • By copying from cell B1 to C1 the formula AVERAGE(B4:B62), we find the mean interarrival time is 12.864 seconds and the mean service time is 77.102 seconds. Because mean service time is almost six times as large as mean interarrival time, we will need at least six agents to guarantee a steady state. Copying from cell B2 to C2 the formula STDEV(B4:B62) tells us that the standard deviation of the interarrival times is 4.439 seconds, and the standard deviation of the service times is 48.051 seconds.

  • Returning to the queuing template in the Model worksheet, if we enter these values in cells B6:B9 and enter 6 servers in cell B5, we find that disaster ensues. In the steady state, nearly 244 people will be in line (cell B19). You’ve probably been at the airport in this situation.

  • I used a one-way data table (shown in Figure 69-3) to determine how changing the number of agents affects the system’s performance. In cells F10:F14, I entered the number of agents we want to consider (6 through 10). In cell G9, I enter the formula to compute L(=B19) and in H9, I enter the formula to compute W(=B18). Next, I select the table range (F8:H14) and then click Data Table from the What-If portion of the Data tab. After choosing cell B5 (the number of servers) as the Row Input Cell, we obtain the data table shown in Figure 69-3. Notice that adding just one ticket agent to our original six agents reduces the expected number of customers present in line from 244 to fewer than 7. Adding the seventh agent reduces a customer’s average time in the system from 3137 seconds (53 minutes) to 90 seconds (1.5 minutes). This example shows that a small increase in service capacity can greatly improve the performance of a queuing system.

    image from book
    Figure 69-3: Sensitivity analysis for an airline ticket counter

  • In cells F16:K22, I used a two-way data table to examine the sensitivity of the average time in the system (W) to changes in the number of servers and standard deviation of service times. The Row Input Cell is B5, and the Column Input Cell is B9. When seven agents are working, an increase in the standard deviation of service times from 40 seconds to 90 seconds results in a 29 percent increase in the mean time in the system (from 86.2 seconds to 111.8 seconds).

    Note 

    Readers who are interested in a more extensive discussion of the queuing theory should refer to my book Operations Research: Applications and Algorithms (Duxbury Press, 2003).




Microsoft Press - Microsoft Office Excel 2007. Data Analysis and Business Modeling
MicrosoftВ® Office ExcelВ® 2007: Data Analysis and Business Modeling (Bpg -- Other)
ISBN: 0735623961
EAN: 2147483647
Year: 2007
Pages: 200

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net