Queuing Theory

Each of us has spent a great deal of time waiting in lines. In this chapter, we develop mathe- matical models for waiting lines, or queues. In Section 20.1, we begin by discussing some ter- minology that is often used to describe queues. In Section 20.2, we look at some distributions (the exponential and the Erlang distributions) that are needed to describe queuing models. In Section 20.3, we introduce the idea of a birth–death process, which is basic to many queu- ing models involving the exponential distribution. The remainder of the chapter examines sev- eral models of queuing systems that can be used to answer questions like the following: 1 What fraction of the time is each server idle? 2 What is the expected number of customers present in the queue? 3 What is the expected time that a customer spends in the queue? 4 What is the probability distribution of the number of customers present in the queue? 5 What is the probability distribution of a customer’s waiting time? 6 If a bank manager wants to ensure that only 1% of all customers will have to wait more than 5 minutes for a teller, how many tellers should be employed? 20.1 Some Queuing Terminology To describe a queuing system, an input process and an output process must be specified. Some examples of input and output processes are given in Table 1. The Input or Arrival Process The input process is usually called the arrival process. Arrivals are called customers. In all models that we will discuss, we assume that no more than one arrival can occur at a given instant. For a case like a restaurant, this is a very unrealistic assumption. If more than one arrival can occur at a given instant, we say that bulk arrivals are allowed. Usually, we assume that the arrival process is unaffected by the number of customers present in the system. In the context of a bank, this would imply that whether there are 500 or 5 people at the bank, the process governing arrivals remains unchanged. There are two common situations in which the arrival process may depend on the num- ber of customers present. The first occurs when arrivals are drawn from a small popula- tion. Suppose that there are only four ships in a naval shipyard. If all four ships are be- ing repaired, then no ship can break down in the near future. On the other hand, if all four ships are at sea, a breakdown has a relatively high probability of occurring in the near 1052 CHAPTER 20 Queuing Theory future. Models in which arrivals are drawn from a small population are called finite source models. Another situation in which the arrival process depends on the number of customers present occurs when the rate at which customers arrive at the facility decreases when the facility becomes too crowded. For example, if you see that the bank parking lot is full, you might pass by and come another day. If a customer arrives but fails to enter the system, we say that the customer has balked. The phenomenon of balking was de- scribed by Yogi Berra when he said, “Nobody goes to that restaurant anymore; it’s too crowded.” If the arrival process is unaffected by the number of customers present, we usually de- scribe it by specifying a probability distribution that governs the time between successive arrivals. The Output or Service Process To describe the output process (often called the service process) of a queuing system, we usually specify a probability distribution—the service time distribution —which governs a customer’s service time. In most cases, we assume that the service time distribution is independent of the number of customers present. This implies, for example, that the server does not work faster when more customers are present. In this chapter, we study two arrangements of servers: servers in parallel and servers in series. Servers are in parallel if all servers provide the same type of service and a cus- tomer need only pass through one server to complete service. For example, the tellers in a bank are usually arranged in parallel; any customer need only be serviced by one teller, and any teller can perform the desired service. Servers are in series if a customer must pass through several servers before completing service. An assembly line is an example of a series queuing system. Queue Discipline To describe a queuing system completely, we must also describe the queue discipline and the manner in which customers join lines. The queue discipline describes the method used to determine the order in which cus- tomers are served. The most common queue discipline is the FCFS discipline (first come, first served), in which customers are served in the order of their arrival. Under the LCFS discipline (last come, first served), the most recent arrivals are the first to enter service. If we consider exiting from an elevator to be service, then a crowded elevator illustrates an LCFS discipline. Sometimes the order in which customers arrive has no effect on the or- TABLE 1 Examples of Queuing Systems Situation Input Process Output Process Bank Customers arrive at bank Tellers serve the customers Pizza parlor Requests for pizza delivery Pizza parlor sends out are received truck to deliver pizzas Hospital blood bank Pints of blood arrive Patients use up pints of blood Naval shipyard Ships at sea break down Ships are repaired and and are sent to shipyard return to sea for repairs