INTRODUCTION Queueing theory deals with the study of queues (waiting lines). Queues abound in practical situations. The earliest use of queueing theory was in the design of a telephone system. Applications of queueing theory are found in fields as seemingly diverse as traffic control, hospital management, and time-shared computer system design. In this chapter, we present anelementary queueing theory. QUEUEING SYSTEMS
A. Description: A simple queueing system is shown in Fig. 16-1. Customers arrive randomly at an average rate of λ a . Upon arrival, they are served without delay if there are available servers; otherwise, they are made to wait in the queue until it is their turn to be served. Once served, they are assumed to leave the system. We will be interested indetermining such quantities as the average number of customers in the system, the average time a customer spends in the system, the average time spent waiting in the queue, etc. Arrivals
Fig.16-1 A simple queuing system The description of any queueing system requires the specification of three parts:
1. The arrival process 2. The service mechanism, such as thenumber of servers and service-time distribution 3. The queue discipline (for example, first-come, first-served)
B. Classification : The notation A/B/s/K is used to classify a queueing system, where A specifies the type of arrival process, B denotes the service-time distribution, s specifies the number of servers, and K denotes the capacity of the system, that is, the maximum number of customersthat can be accommodated. If K is not specified, it is assumed that the capacity of the system is unlimited. Examples: M/M/2 queueing system (M stands for Markov) is one with Poisson arrivals, exponential service-time distribution, and 2 servers. An M/G/l queueing system has Poisson arrivals, general service-time distribution, and a single server. A special case is the M/D/1 queueing system, where Dstands for constant (deterministic:) service time. Examples of queueing systems with limited capacity are telephone systems with limited trunks, hospital emergency rooms with limited beds, and airline terminals with limited space in which to park aircraft for loading and unloading. In each case, customers who arrive when the system is saturated are denied entrance and are lost.
Some basic quantities of queueing systems are L: the average number of customers in the system Lq: the average number of customers waiting in the queue Ls: the average number of customers in service W: the average amount of time that a customer spends in the system Wq: the average amount of time that a customer spends waiting in the queue Ws: the average amount of time that a customerspends in service
Many useful relationships between the above and other quantities of interest can be obtained by using the following basic cost identity: Assume that entering customers are required to pay an entrance fee (according to some rule) to the system. Then we have: Average rate at which the system earns = λ a x average amount an entering customer pays (16.1) where
λ a , is theaverage arrival rate of entering customers
λ a = lim
X (t ) t →∞ t
and X(t) denotes the number of customer arrivals by time t. If we assume that each customer pays $1 per unit time while in the system , then Eq. 16.1 yeilds: (16.2) L =λa x W Equation (16.2) is sometimes known as Little's formula. Similarly, if we assume that each customer pays $1 per unit time while in the queue,then Eq. 16.1yields Lq = Ls =
λ a x wq λ a x ws
If we assume that each customer pays $1 per unit time while in service, Eq. (16.1) yields Note that Eqs. (16.2) to (16.4) are valid for almost all queueing systems, regardless of the arrival process, the number of servers, or queueing discipline. BIRTH-DEATH PROCESS We say that the queueing system is in state Sn , if there are n customers in...