Namespaces
Variants
Actions

Difference between revisions of "Queueing theory"

From Encyclopedia of Mathematics
Jump to: navigation, search
m
m (tex encoded by computer)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
 +
<!--
 +
q0768501.png
 +
$#A+1 = 56 n = 0
 +
$#C+1 = 56 : ~/encyclopedia/old_files/data/Q076/Q.0706850 Queueing theory
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
{| class="wikitable"
+
{{TEX|auto}}
!Copyright notice <!-- don't remove! -->
+
{{TEX|done}}
|-
 
| This article ''Queueing Theory'' was adapted from an original article by U. Narayan Bhat, which appeared in ''StatProb: The Encyclopedia Sponsored by Statistics and Probability Societies''. The original article ([<nowiki>http://statprob.com/encyclopedia/QueueingTheory.html</nowiki> StatProb Source], Local Files: [[Media:queueing_theory.pdf|pdf]] | [[Media:queueing_theory.tex|tex]]) is copyrighted by the author(s), the article has been donated to ''Encyclopedia of Mathematics'', and its further issues are under ''Creative Commons Attribution Share-Alike License'. All pages from StatProb are contained in the [[:Category:Statprob|Category StatProb]].
 
|-
 
|}
 
  
{{MSC|60}}
+
The branch of probability theory in which one studies mathematical models of various kinds of real queues (cf. [[Queue|Queue]]). These models are presented as random processes of a special form, sometimes called service processes. The definitions of these processes are most often descriptive, since their formal construction is very complicated and not always effective.
  
<!-- \documentclass[10pt]{article}
+
Queueing theory mainly uses the apparatus of probability theory. The fundamental problems of queueing theory usually are these: Based on  "local"  properties of the random processes under discussion, study their stationary characteristics (if they exist) or the behaviour of these characteristics over a long period of time. One of the main aims of research in this area is the choice of a preferable organization for a queueing system.
    \newtheorem{theorem}{Theorem}
 
    \newtheorem{corollary}{Corollary}
 
    \newtheorem{lemma}{Lemma}
 
    \newtheorem{proposition}{Proposition}
 
    \newtheorem{definition}{Definition}
 
    \newtheorem{notation}{Notation} -->
 
$ \def\mbit#1{ {\bf #1}} $
 
  
<!-- \begin{document} -->
+
For example, for a typical object of queueing theory such as an automatic telephone exchange (see [[Queue with refusals|Queue with refusals]]) one of the basic characteristics is the proportion of calls lost, that is, the limit  $  p $,
<center>'''\bf Queueing Theory'''</center>
+
as  $  t \rightarrow \infty $(
 +
if it exists), of the ratios  $  r ( t) / e ( t) $
 +
of the number  $  r ( t) $
 +
of calls lost up to time  $  t $
 +
to the number  $  e ( t) $
 +
of calls which arrived up to the same time. Here the distribution of the time intervals  $  \tau _ {1}  ^ {e} , \tau _ {2}  ^ {e} \dots $
 +
between the arrivals of calls and the distribution of the service times  $  \tau _ {1}  ^ {s} , \tau _ {2}  ^ {s} \dots $
 +
of these calls are assumed to be known. The assignment of the distribution of a random (control) sequence  $  \{ {\tau _ {j}  ^ {e} , \tau _ {j}  ^ {s} } : {j = 1, 2 ,\dots  } \} $
 +
together with the description of an algorithm of how the queue evolves form the initial data, characterizing the  "local"  properties of the service process.
  
<center> U. Narayan Bhat
+
Similarly, for multi-server queues (cf. [[Queue, multi-channel with waiting|Queue, multi-channel with waiting]]) one studies the limit as  $  n \rightarrow \infty $
 +
of the distributions of the probabilities  $  {\mathsf P} \{ w _ {n} < x \} $
 +
and  $  {\mathsf P} \{ q _ {n} < x \} $
 +
for the time  $  w _ {n} $
 +
which the  $  n $-
 +
th call arriving in the system has to wait before the beginning of its service and the queue length  $  q _ {n} $
 +
at the time of its arrival. The limit distribution  $  \lim\limits _ {t \rightarrow \infty }  {\mathsf P} \{ q ( t) < x \} $
 +
for the queue length at time  $  t $,
 +
etc., are also discussed. Here, again, the initial data are the assignment of the control sequences (the distribution of the intervals of service times) and the algorithm defining the operation of the queue.
  
Southern Methodist University, Dallas, TX, USA 75275 </center>
+
For relatively simple queues, and under certain assumptions on the control sequence, the required characteristics can be found by analytic methods. However, the number of such systems is not large. The nature of the conditions imposed on the control sequence can be demonstrated by the example of a queue with refusals (an automatic telephone exchange). Let 1) the random variables  $  \tau _ {j}  ^ {e} $
<!-- \maketitle
+
be exponentially distributed:
    \noindent -->
 
'''Keywords''': birth and death process; Markov chain; Markov process; matrix analytic method; queue length; steady state probability; stochastic process; transition probability; waiting line.
 
<!-- \vskip.25in
 
    \noindent -->
 
Queueing is essential to manage congestion in traffic of any type in the modern technological world. This does not mean it is a new phenomenon. More than one hundred years ago, recognizing its importance to telephone traffic, Danish mathematician A. K. Erlang (1909) showed for the first time how probability theory can be used to provide a mathematical model for telephone conversations. From then on, slowly in the first three decades, moderately in the next three decades, and tremendously in the last four decades, the probabilistic approach to modeling queueing phenomena has grown and contributed significantly to the technological progress. For a historical perspective of the growth of queueing theory see Chapter 1 of Bhat (2008).
 
  
<!-- \vspace{.15in}  
+
$$
    \noindent -->
+
{\mathsf P} \{ \tau _ {j}  ^ {e} > x \}  =  e ^ {- \alpha x } ,\  \alpha > 0,
Queueing theory describes probabilistically and mathematically the interaction between the arrival process of customers and the service provided to them in order to manage the system in an efficient manner. The term customer is used in a generic sense representing a unit, human or otherwise, demanding service. The unit providing service is known as the server. Some examples of a queueing system are: a communication system with voice and data traffic demanding transmission; a manufacturing system with several work stations; patients arriving at a doctor's office; vehicles requiring service; and so on.
+
$$
  
<!-- \vspace{.15in}  
+
that is, the input stream is Poisson; 2) the variables  $  \tau _ {j}  ^ {s} $
    \noindent -->
+
be independent and identically distributed and not dependent on  $  \{ \tau _ {j}  ^ {e} \} $.
Since the arrival process and service are random phenomena we start with a probabilistic model (also known as a stochastic model) of a queueing system. If we analyze such models using mathematical techniques we can derive its properties that can be used in understanding its behavior and managing it for its efficient use.
+
Then the probability of refusal  $  p $,
 +
defined above, exists and is equal to
  
<!-- \vspace{.15in}
+
$$
    \noindent -->
+
p  = \  
In order to build a probabilistic model, first we describe the arrival process (called the input process) using probability distributions. For example, the arrival of customers could be in a Poisson process; i.e. the number of customers arriving in a set period of time has a Poisson distribution. Its parameter, say $\lambda$, gives the mean number of customers arriving during a unit time. The known distribution now identifies the arrival process. The amount of service provided by the facility is represented by a random variable since it could be random. The distribution of the random variable identifies the service process. When we talk about service we have to take into consideration the mode of service such as service provided with several servers, service provided in a network of servers, etc. Also we must include factors such as queue discipline (e.g., first come, first served (FCFS), also known as first in, first out (FIFO); last come, first served (LCFS or LIFO); group service; priority service; etc). Another factor that complicates the model is the system capacity, which may be finite or infinite.
 
  
<!-- \vspace{.15in}  
+
\frac{\rho  ^ {n} }{n!}
    \noindent -->
 
Because of the multitude of factors involved in a queueing system, we use a three or four element symbolic representation in discussing various types of systems. The basic structure of the representation is to use symbols or numbers for the three elements: input/service/number of servers. When the system capacity is finite an additional element is added. The commonly used symbols for distributions are: $M$ for Poisson or exponential, $E_k$ for Erlangian with $k$ phases (gamma distribution with an integer scale parameter $k$), $D$ for deterministic, and $G$ for a general (also $GI$ for general independent) or an unspecified distribution. Thus M/G/1 represents a Poisson arrival, general service, and single server system, and M/G/1/N has the same description as above with a capacity restriction of $N$ customers in the system.
 
  
<!-- \vspace{.15in}  
+
\left (
    \noindent -->
+
\sum _ { k= } 0 ^ { n }
When the arrival process is represented by a random variable with an index parameter t, define $A(t)$ as the number of customers arriving and $D(t)$ the number of customers leaving the system during a time period $(0, t)$. Let the number of customers in the system at time $t$ be $Q(t)$. Then $Q(t) = A(t) - D(t)$. In order to manage the system efficiently one has to understand how the process $Q(t)$ behaves over time. Note that all $A(t), D(t)$, and $Q(t)$ are stochastic processes (which are sequences of random variables indexed by the time parameter $t$.) Since the total number of customers leaving the system at $t$ is dependent on the number customers arriving during that time, the mode of their arrival (e.g. there may be time periods with no customers in the system, commonly called idle periods), the service mechanism, queue discipline (when some customers get preferred treatment) and other factors that affect the operation of the system (e.g. service breakdowns), to analyze $Q(t)$, all these factors need to be taken into account in the model.
 
  
<!-- \vspace{.15in}
+
\frac{\rho  ^ {k} }{k!}
    \noindent -->
 
In the analysis of a queueing system the stochastic process $W(t)$ representing the waiting time of a customer to get served, and the random variable, say $B$, representing the busy period (the amount of time the system is continuously busy at a stretch) are also used. The objective of the analysis is to get the distributional properties of the stochastic processes $Q(t)$ and $W(t)$ and the random variable $B$ for use in decision making. Analyzing stochastic processes in finite time t often becomes very complex. When the constituent elements such as arrival and service are not time-dependent we can derive the distributions of the limit random variables $Q = \lim_{t \rightarrow \infty} Q(t)$ and $W = \lim_{t \rightarrow \infty} W(t)$ when they exist. The ratio arrival rate/service rate is commonly known as the traffic intensity of the queueing system (say $\rho$). The property $\rho < 1$ is generally the requirement for the existence of the limit distributions of the stochastic processes $Q(t)$ and $W(t)$, when they are time-independent. The behavioral performance measures of interest in a queueing system are transition probability distributions of $Q(t)$ and $W(t)$, probability distributions of $Q, W$, and $B$, and their means and variances.
 
  
<!-- \vspace{.15in}  
+
\right )  ^ {-} 1 ,
    \noindent -->
+
$$
In addition to the behavioral problems of underlying stochastic processes mentioned above, we are also interested in inference problems such as estimation and tests of hypotheses regarding basic parameters and performance measures, and optimization problems for assistance in decision making. An introduction to these topics and the necessary references may be found in Bhat (2008).
 
  
<!-- \vspace{.15in}
+
where  $  \rho $
    \noindent -->
+
is the ratio of the mathematical expectations:
In order to provide an illustration of the behavioral analysis of a queueing system we consider below a system with Poisson arrivals, exponential service, and single server, symbolically known as an M/M/1 queue. This is the simplest and the most used system in applications.
 
  
<!-- \vspace{.15in}
+
$$  
    \noindent -->
+
\rho  = \  
Let customers arrive in a Poisson process with rate $\lambda$. This means that the number $A(t)$ of the customers arriving in $(0, t)$ has a Poisson distribution
 
\[
 
P[A(t)=j] = e^{-\lambda t}\frac{(\lambda t)^j}{j!}, \hspace{.15in} j=0,1,2,...
 
\]
 
It also means that the interarrival times have an exponential distribution with probability density $a(x) = \lambda e^{-\lambda x} (x > 0)$. We assume the service times to have an exponential distribution with probability density $b(x)=\mu e^{-\mu x} (x > 0)$. With these assumptions we have E[inter-arrival time] $=(1/\lambda) = 1$/arrival rate and E[service time] $= (1/\mu) = 1$/service rate. The ratio of arrival rate to service rate is the traffic intensity. Note that we have assumed the processes to be time-independent.
 
<!-- \vspace{.15in}
 
    \noindent -->
 
Let $Q(t)$ be the number of customers in the system at time $t$ and its transition probability distribution be defined as
 
\[
 
P_{ij}=P[Q(t)=j|Q(0)=i]
 
\]
 
Because of the Poisson arrival process and the exponential service distribution, $Q(t)$ can be modeled as a birth and death process (a class of stochastic processes with major properties (a) probability of more than one state change during an infinitesimal interval of time is close to zero; (b) the rate of change in a unit time is constant and (c) changes occurring in non-overlapping intervals of time are independent of each other) governed by the following difference-differential equations.
 
\begin{eqnarray}
 
P_{i0}(t)&=& -\lambda P_{i0}(t)+ \mu P_{i1}(t) \nonumber \\
 
P_{in}(t)&=&-(\lambda + \mu)P_{in}(t)+\lambda P_{i,n-1}(t) \nonumber \\
 
& & + \mu P_{i,n+1}(t) \hspace{.30in} n=1,2,...
 
\end{eqnarray}
 
<!-- \noindent -->
 
with $P_{in}(0)=1$ when $n = i$ and $= 0$ otherwise. Solving these equations to obtain $P_{in}(t)$ is not very simple. Readers may refer to Gross et al (2008) and its earlier editions for their solutions.
 
  
<!-- \vspace{.15in}  
+
\frac{ {\mathsf E} \tau _ {j} ^ {s} }{ {\mathsf E} \tau _ {j} ^ {e} }
    \noindent -->
 
When $\rho < 1$, the limit $P_{ij}(t)=p_j$ exists and is independent of the initial state $i$. It is known as the steady state probability. It can be obtained easily from the following equations that result by letting $t \rightarrow \infty$ in the above set of difference-differential equations.
 
\begin{eqnarray}
 
\lambda p_0 &=& \mu p_1 \nonumber \\
 
(\lambda + \mu)p_n &=& \lambda p_{n-1} + \mu p_{n+1} \hspace{.3in} n=1,2,...
 
\end{eqnarray}
 
<!-- \noindent -->
 
along with $\sum^\infty_{n=0} p_n = 1$. We get $p_0 = 1 - \rho, p_n = (1-\rho)\rho^n(n=0,1,2,...,)$. The mean $E(Q)$ and variance $V(Q)$ of this distribution can be obtained as $E(Q) = \rho/(1-\rho)$ and $V(Q) = \rho/(1-\rho)^2$.
 
  
<!-- \vspace{.15in}
+
= \alpha {\mathsf E} \tau _ {j} ^ {s} .
    \noindent -->
+
$$
The waiting time of an arriving customer, when the queue discipline is FCFS, is the total amount of time required to serve the customers who are already in the system and this total time has an Erlangian distribution. Let us denote it as $T_q$ (we use $T$ as the random variable representing the total time the customer is in the system, also known as total workload.) Accordingly we get
 
\begin{eqnarray*}
 
P[T_q \leq t] &=& 1-\rho + \int^t_0 \sum^\infty_{n=1}p_n e^{-\mu t}\frac{\mu^n t^n}{(n-1)!} dt \\
 
&=& 1 - \rho e^{-\mu(1-\rho)t} \\
 
E[T_q] &=& \rho/\mu(1-\rho) \mbox{ and } E[T]=1/\mu(1-\rho).
 
\end{eqnarray*}
 
<!-- \noindent -->
 
Let $E(Q) = L$ and $E(T) = W$. Looking at the above results we can see that $L = \lambda W$ showing, how $L$ and $W$ are related in this system. This property is known as Little's Law and it holds in more complex systems under certain general conditions. Another property is the exponential nature of the limiting waiting time distribution shown above which holds in more general queueing systems as well.
 
  
<!-- \vspace{.15in}
+
For this system, if one of the conditions 1) or 2) fails, then the search of explicit formulas for  $  p $
    \noindent -->
+
becomes very complicated or even impossible.
The derivation of the distribution of the busy period B is more complicated even in this simple system. We may refer the reader to Gross et al (2008) for its derivation.
 
  
<!-- \vspace{.15in}
+
Underlying the analytic approach to the search for explicit expressions for the desired characteristics is a method connected with the construction of Markov processes describing the state of the system. These processes are very well studied and the solution of the problem in this case reduces to the formulation and solution of the corresponding equations for stationary distributions (invariant measures).
    \noindent -->
+
 
When systems include more complicated features, more advanced techniques are employed to analyze resulting stochastic models. For instance, generalizing the concepts introduced earlier, the birth and death process can be used to model a wide class of queueing systems. Using the terminology of birth for the arrival and death for the departure of customers, when there are $n$ customers in the system, let $\lambda_n$ be the rate of birth and $\mu_n$ be the rate of dealth. The birth and dealth process is governed by the three properties identified earlier. Writing $P_{in}(t) \equiv P_n(t)$ for ease of notation, the transition probabilities of the stochastic process $Q(t)$ can be shown to satisfy equations similar to (1), with $\lambda$ and $\mu$ replaced by $\lambda_n$ and $\mu_n$ respectively. Denoting the row vector $[P_0(t), P_1(t),...]$ as $\mbit{P(t)}$, the row vector of their derivatives as $\mbit{P}^\prime(\mbit{t})$, and the transition rate matrix (also called the generator matrix)
+
Such a process is often used in a modified form by forming semi-Markov processes or imbedded Markov processes (the Markov property is satisfied only at certain random times).
$$
 
\mbit{A} =
 
\left[ \matrix{& & & & \cr
 
& -\lambda_0 & \lambda_0 & & \cr
 
& \mu_1 & -(\lambda_1 + \mu_1) & \lambda_1 & \cr
 
& & \mu_2 & -(\lambda_2 + \mu_2) & \lambda_2 \cr
 
& & & \ddots & } \right]
 
\tag{1}$$
 
  
<!-- \noindent -->
+
For certain complicated queues exact analytic methods, as a rule, are not effective and one uses asymptotic methods or simulates the random processes by a [[Monte-Carlo method|Monte-Carlo method]]. Asymptotic methods are relevant in those cases when the system under consideration is close (in its local properties) to another system which is either well studied and allows the calculation of the necessary characteristics, or is in some sense critical. The direction of asymptotic investigation in the first case is described by stability (or continuity) theorems. In the second case stationary characteristics often do not exist, but one can establish  "collective"  limit theorems for them, that is, theorems in which the limit behaviour is determined not by individual properties of the control sequences but only by certain numerical parameters. Examples of the second type are theorems on the so-called single-server queues with heavy traffic. They have been established as follows. Let the inter-arrival intervals  $ \tau _ {j} ^ {e} $,
the generalized Eq. (1) can be written as
+
$  j = 1 , 2 \dots $
$$
+
and the inter-service times  $  \tau _ {j} ^ {s} $,
\mbit{P}^{'} \mbit{(t)} = \mbit{P(t)} \mbit{A}
+
$  j = 1 , 2 \dots $
\tag{2}$$
+
form mutually-independent sequences of independent identically-distributed variables and let the expectation
  
<!-- \noindent -->
+
$$
As $t \rightarrow \infty$ and when $P_n(t)$ exists, writing $P_n(t)_{\lim t \rightarrow \infty} = p_n$ and denoting the row vector of $\{p_n, n=0,1,2,...\}$ as $\mbit{p}$, Eq. (4) becomes
+
a  =  {\mathsf E} ( \tau _ {j}  ^ {s} - \tau _ {j} ^ {e} )
 
$$
 
$$
0 = \mbit{p A}
 
\tag{3}$$
 
  
[Eq. (2) in the M/M/1 case.]
+
of the difference between  $  \tau _ {j}  ^ {s} $
 +
and  $  \tau _ {j}  ^ {e} $
 +
be positive. Then there is a non-degenerate limit distribution
  
<!-- \noindent -->
+
$$
In queueing models of a wide variety of systems from computer, communication, manufacturing, and other areas of applications, birth and death process models can be used with generator matrix $\mbit{A}$ of appropriate structures, sometimes with submatrices taking the place of matrix elements. The problem now consists of solving equations of the type (4) and (5).
+
w ( x)  =  \lim\limits _ {n \rightarrow \infty } \  
 +
{\mathsf P} \{ w _ {n} \geq  x \}
 +
$$
  
<!-- \vspace{.15in}  
+
for the waiting time  $  w _ {n} $
    \noindent -->
+
of the  $  n $-
In two classical papers Kendall (1951, 1953) introduced the imbedded Markov chain technique for the analysis of queueing systems when their arrival processes are not Poisson and/or the service time distributions are not exponential. In an M/G/1 queue the queue length process $Q(t)$ is not a Markov process for all $t$. But if we observe the process only at departure points, say $t_0, t_1, t_2,..., \{Q(t_n) n=0,1,2,...,\}$ is an imbedded markov chain, the transition probablility matrix of which can be fully described when the arrival rate and the service time distribution are known. In a GI/M/1 queue, to get an imbedded Markov chain, we have to observe the system at arrival points. Then knowing the distribution of inter-arrival times and the rate of service we can specify the elements of the corresponding transition probability matrix. The analysis of the queueing systems then follow using standard techniques for the analysis of Markov chains.
+
th call. In addition, let the random variables  $  \tau _ {j}  ^ {e} $,
 +
\tau _ {j}  ^ {s} $
 +
vary so that  $  a \downarrow 0 $(
 +
$  a $
 +
tends to zero from the positive side), so that the variance  $ {\mathsf D} ( \tau _ {j}  ^ {s} , \tau _ {j}  ^ {e} ) $
 +
converges to a positive limit  $ \sigma  ^ {2} < \infty $
 +
and so that the expectation  $ {\mathsf E} [ \tau _ {j}  ^ {s} - \tau _ {j}  ^ {e} ] ^ {2 + \gamma } $
 +
is uniformly bounded for some  $  \gamma > 0 $.  
 +
Then for each fixed  $  z $,
  
<!-- \vspace{.15in}  
+
$$ \tag{* }
    \noindent -->
+
w \left (
Until the 1970s researchers analyzed stochastic processes underlying queueing system models using difference, differential and integral equations with the help of transforms; combinatorial relationships; and recursive solution techniques. As queueing models in applications such as computer-communication and manufacturing systems became more complex the available methods became inadequate. The need for analyzing such processes was answered with the development of the matrix analytic approach initiated by Neuts (1981) on generalized forms of matrix structures show in (3) and the transition probability matrices of the imbedded Markov chains of M/G/1 and GI/M/1, and advanced by many researchers since then. See Latouche and Ramaswami (1999).
+
\frac{z}{a}
 +
\right )  \rightarrow \  
 +
e ^ {- 2 z / \sigma  ^ {2} } .
 +
$$
  
<!-- \vspace{.15in}
+
This relation allows the approximate calculation of  $  w ( x) $
    \noindent -->
+
for small values of  $  a $.  
The literature on queueing theory is vast and it is impossible to cover all facets of the analysis of queueing systems using various modeling and sophisticated mathematical techniques in a short article in an encyclopedia. One such system is the queueing network in which customers are served in various types of networks of service nodes. It has spawned a major area of research and applications relevant to systems such as computer, communication, manufacturing and transportation. Retrial, polling and vacation models are some of the models used in the analysis of individual or networks of queues.
+
The limit system, corresponding to  $  a = 0 $,
 +
is critical in the sense that for it there is no non-degenerate limit distribution  $  w ( x) $,
 +
and  $  w ( x) = 1 $
 +
for each  $  x > 0 $(
 +
the waiting time of the $  n $-
 +
th client increases unboundedly as  $  n $
 +
increases). Relation (*) can be extended to a broad class of queues with waiting under very general assumptions on the control sequences.
  
<!-- \vspace{.15in}
+
The emergence of queueing theory has produced an interest in the novel mathematical problems which arise in the organization of telephone networks. The first publication in this connection is due to A. Erlang in 1907. The later development of queueing theory occurred in the 1940's and 1950's in papers by C. Palm, F. Pollaczek, A.Ya. Khinchin, and others. The last coined the term  "queue" . In the USSR, work on queueing theory was continued by B.V. Gnedenko, with a group of his students, and others.
    \noindent -->
 
As mentioned earlier, analysis of queueing systems involves the study of interaction between arrival and service processes under various queueing structures and queueing disciplines. These complexities generate a large number of problems in practice. For instance, if the arrival rate is larger than service rate, the system becomes unstable. Limit theorems on appropriate distributions provide the behavior of such congested systems. The properties of the tail probabilities of queue length and waiting time distributions describe the influence the basic distributions of arrival and service processes have on the system behavior. Also the complexities of the systems may require the use of mathematically more sophisticated stochastic processes such as diffusion processes.
 
 
 
<!-- \vspace{.15in}
 
    \noindent -->
 
The following references provide the basic understanding of the subject at two levels: Bhat (2008) for those who have a background only in probability and statistics at an introductory level and Gross and Harris (1998) or Gross et al. (2008) for those who have some background in stochastic processes. Bibliographies given in these books and specialized books such as Buzacott and Shanthikumar (1993) and Chen and Yao (2001) provide a good selection of references on the subject. The major source for articles in queueing theory is the journal ''Queueing Systems''. Other sources are major operations research journals such as ''European Journal of Operations Research'', ''Management Science'', ''Operations Research'', and ''Stochastic Models''; and other journals in application areas such as electrical and communications engineering, industrial engineering, and manufacturing.
 
  
 +
The development of queueing theory has been stimulated both by a variety of applications and by the mathematical content of the problems that arise. Although formally a part of the theory of random processes, queueing theory has evolved into an independent area of research with its own problems and methods of solution.
  
 
====References====
 
====References====
{|
+
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> A.Ya. Khinchin,   "Mathematical methods in the theory of queueing" , Griffin (1960)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> B.V. Gnedenko,   I.N. Kovalenko,   "Introduction to queueing theory" , Israel Program Sci. Transl. (1968(Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> A.A. Borovkov,   "Stochastic processes in queueing theory" , Springer  (1976) (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> A.A. Borovkov,   "Asymptotic methods in queueing theory" , Wiley (1984)  (Translated from Russian)</TD></TR></table>
|-
 
|valign="top"|{{Ref|rf:1}}||valign="top"| Bhat, U. N. (2008). ''An Introduction to Queueing Theory'', Birkhauser, Boston.
 
|-
 
|valign="top"|{{Ref|rf:2}}||valign="top"| Buzacott, J. A. and Shanthikumar, J. G. (1993),  ''Stochastic Models of Manufacturing Systems'', Prentice Hall, Upper Saddle River, NJ.
 
|-
 
|valign="top"|{{Ref|rf:3}}||valign="top"| Chen, H. and Yao, D. D. (2001),  ''Fundamentals of Queueing Networks'', Springer, New York.
 
|-
 
|valign="top"|{{Ref|rf:4}}||valign="top"|  Erlang, A. K. (1909), The theory of probabilities and telephone conversations ''Nyt Tidsskrift fur Matematik B'', '''20''', 33.  
 
|-
 
|valign="top"|{{Ref|rf:5}}||valign="top"|  Gross, D. and Harris, C. M. (1998),  ''Fundamentals of Queueing Theory'', 3rd Ed., Wiley, New York.
 
|-
 
|valign="top"|{{Ref|rf:6}}||valign="top"|  Gross, D., Shortle, J. F., Thompson, J. M. and Harris, C. M. (2008), ''Fundamentals of Queueing Theory'', 4th Ed., Wiley, New York.
 
|-
 
|valign="top"|{{Ref|rf:7}}||valign="top"| Kendall, D. G. (1951), "Some problems in the theory of queues''J. Royal Statist. Soc. B'', '''13''', 151-185.
 
|-
 
|valign="top"|{{Ref|rf:8}}||valign="top"| Kendall, D. G. (1953), "Stochastic processes occurring in the theory of queues and their analysis by the method of imbedded Markov chains",  ''Ann. Math. Statist.'', '''24''', 338-354.
 
|-
 
|valign="top"|{{Ref|rf:9}}||valign="top"|  Latouche, G. and Ramaswami, V. (1999),  ''Introduction to Matrix Analytic Methods in Stochastic Modeling'', ASA-SIAM Series on Statistics and Applied Probability, Philadelphia, PA.
 
|-
 
|valign="top"|{{Ref|rf:10}}||valign="top"| Neuts, M. F. (1981),  ''Matrix-Geometric Solutions in Stochastic Models. An Algorithmic Approach'', The Johns Hopkins University Press, Baltimore, MD.
 
|-
 
|}
 
  
 +
====Comments====
 +
A facility for collective use has usually a limited capacity and congestion (loss) arises when the momentary demands of the users surpass the capacity. Facilities for collective use are encountered in a large variety in present day society, e.g. ticket windows, road junctions, beds in a hospital, communication trunks in a telephone network, the central processor unit in a computer.
  
<!-- \vspace{.25in} -->
+
The need to evaluate the performance of a facility led to the development of queueing theory. The basic model concerns a single-server system and the description of the arrival process, of the service times required by the customers and the service discipline, which specifies the schedule of handling the customers.
  
Acknowledgement : Based on an article from Lovric, Miodrag (2011), International Encyclopedia of Statistical Science. Heidelberg: Springer Science + Business Media, LLC.
+
The irregularities in the arrival stream and also those in the demands of the service times require for their modelling a probabilistic approach; in fact, they are modelled as stochastic processes. Consequently, performance characteristics such as the waiting time of the  $  m $-
 +
th arriving customer, the queue length of the  $  n $-
 +
th arrival and the workload of the server as a function of time have to be analyzed as stochastic processes. Queueing theory studies the relations between these performance characteristics and the input processes (arrival and service times), and as such queueing theory is an important branch of applied probability theory.
  
<!-- \end{document} -->
+
The early developments of queueing theory took place in the first decade of the 20th century; congestion phenomena in telephone communication have been the direct impetus. Until 1940 queueing theory has been developed mainly for purposes in telecommunication engineering. The growing interest after 1940 in [[Operations research|operations research]] had a considerable influence on the developments of queueing theory. At present a huge variety of queueing models are studied: many-server models, batch arrivals instead of individual arrivals, group service, and sophisticated service disciplines like random service, priority service, processor sharing, and feedback of customers. Next to a single-service facility, networks of queues require analysis. In a network a customer or a message has to be transported via the nodes connected by links to a certain destination; at the switching nodes congestion may occur. The routing of the customers through the network is usually modelled as a stochastic protocol.
  
<references />
+
The mathematical analysis concerned with the relations between the performance and model characteristics is the analytical part of queueing theory; simulation techniques are used to study such relations experimentally.
  
[[Category:Statprob]]
+
====References====
 +
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> W. Feller, [[Feller, "An introduction to probability theory and its  applications"|"An introduction to probability theory and its  applications"]], '''1–2''', Wiley (1966)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> L. Kleinrock, "Queueing systems", '''1–2''', Wiley (1976)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> J.W. Cohen, "The single server queue", North-Holland (1982) pp. Chapt. II.1</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> R. Syski, "Congestion theory", North-Holland (1986)</TD></TR></table>

Latest revision as of 08:09, 6 June 2020


The branch of probability theory in which one studies mathematical models of various kinds of real queues (cf. Queue). These models are presented as random processes of a special form, sometimes called service processes. The definitions of these processes are most often descriptive, since their formal construction is very complicated and not always effective.

Queueing theory mainly uses the apparatus of probability theory. The fundamental problems of queueing theory usually are these: Based on "local" properties of the random processes under discussion, study their stationary characteristics (if they exist) or the behaviour of these characteristics over a long period of time. One of the main aims of research in this area is the choice of a preferable organization for a queueing system.

For example, for a typical object of queueing theory such as an automatic telephone exchange (see Queue with refusals) one of the basic characteristics is the proportion of calls lost, that is, the limit $ p $, as $ t \rightarrow \infty $( if it exists), of the ratios $ r ( t) / e ( t) $ of the number $ r ( t) $ of calls lost up to time $ t $ to the number $ e ( t) $ of calls which arrived up to the same time. Here the distribution of the time intervals $ \tau _ {1} ^ {e} , \tau _ {2} ^ {e} \dots $ between the arrivals of calls and the distribution of the service times $ \tau _ {1} ^ {s} , \tau _ {2} ^ {s} \dots $ of these calls are assumed to be known. The assignment of the distribution of a random (control) sequence $ \{ {\tau _ {j} ^ {e} , \tau _ {j} ^ {s} } : {j = 1, 2 ,\dots } \} $ together with the description of an algorithm of how the queue evolves form the initial data, characterizing the "local" properties of the service process.

Similarly, for multi-server queues (cf. Queue, multi-channel with waiting) one studies the limit as $ n \rightarrow \infty $ of the distributions of the probabilities $ {\mathsf P} \{ w _ {n} < x \} $ and $ {\mathsf P} \{ q _ {n} < x \} $ for the time $ w _ {n} $ which the $ n $- th call arriving in the system has to wait before the beginning of its service and the queue length $ q _ {n} $ at the time of its arrival. The limit distribution $ \lim\limits _ {t \rightarrow \infty } {\mathsf P} \{ q ( t) < x \} $ for the queue length at time $ t $, etc., are also discussed. Here, again, the initial data are the assignment of the control sequences (the distribution of the intervals of service times) and the algorithm defining the operation of the queue.

For relatively simple queues, and under certain assumptions on the control sequence, the required characteristics can be found by analytic methods. However, the number of such systems is not large. The nature of the conditions imposed on the control sequence can be demonstrated by the example of a queue with refusals (an automatic telephone exchange). Let 1) the random variables $ \tau _ {j} ^ {e} $ be exponentially distributed:

$$ {\mathsf P} \{ \tau _ {j} ^ {e} > x \} = e ^ {- \alpha x } ,\ \alpha > 0, $$

that is, the input stream is Poisson; 2) the variables $ \tau _ {j} ^ {s} $ be independent and identically distributed and not dependent on $ \{ \tau _ {j} ^ {e} \} $. Then the probability of refusal $ p $, defined above, exists and is equal to

$$ p = \ \frac{\rho ^ {n} }{n!} \left ( \sum _ { k= } 0 ^ { n } \frac{\rho ^ {k} }{k!} \right ) ^ {-} 1 , $$

where $ \rho $ is the ratio of the mathematical expectations:

$$ \rho = \ \frac{ {\mathsf E} \tau _ {j} ^ {s} }{ {\mathsf E} \tau _ {j} ^ {e} } = \alpha {\mathsf E} \tau _ {j} ^ {s} . $$

For this system, if one of the conditions 1) or 2) fails, then the search of explicit formulas for $ p $ becomes very complicated or even impossible.

Underlying the analytic approach to the search for explicit expressions for the desired characteristics is a method connected with the construction of Markov processes describing the state of the system. These processes are very well studied and the solution of the problem in this case reduces to the formulation and solution of the corresponding equations for stationary distributions (invariant measures).

Such a process is often used in a modified form by forming semi-Markov processes or imbedded Markov processes (the Markov property is satisfied only at certain random times).

For certain complicated queues exact analytic methods, as a rule, are not effective and one uses asymptotic methods or simulates the random processes by a Monte-Carlo method. Asymptotic methods are relevant in those cases when the system under consideration is close (in its local properties) to another system which is either well studied and allows the calculation of the necessary characteristics, or is in some sense critical. The direction of asymptotic investigation in the first case is described by stability (or continuity) theorems. In the second case stationary characteristics often do not exist, but one can establish "collective" limit theorems for them, that is, theorems in which the limit behaviour is determined not by individual properties of the control sequences but only by certain numerical parameters. Examples of the second type are theorems on the so-called single-server queues with heavy traffic. They have been established as follows. Let the inter-arrival intervals $ \tau _ {j} ^ {e} $, $ j = 1 , 2 \dots $ and the inter-service times $ \tau _ {j} ^ {s} $, $ j = 1 , 2 \dots $ form mutually-independent sequences of independent identically-distributed variables and let the expectation

$$ a = {\mathsf E} ( \tau _ {j} ^ {s} - \tau _ {j} ^ {e} ) $$

of the difference between $ \tau _ {j} ^ {s} $ and $ \tau _ {j} ^ {e} $ be positive. Then there is a non-degenerate limit distribution

$$ w ( x) = \lim\limits _ {n \rightarrow \infty } \ {\mathsf P} \{ w _ {n} \geq x \} $$

for the waiting time $ w _ {n} $ of the $ n $- th call. In addition, let the random variables $ \tau _ {j} ^ {e} $, $ \tau _ {j} ^ {s} $ vary so that $ a \downarrow 0 $( $ a $ tends to zero from the positive side), so that the variance $ {\mathsf D} ( \tau _ {j} ^ {s} , \tau _ {j} ^ {e} ) $ converges to a positive limit $ \sigma ^ {2} < \infty $ and so that the expectation $ {\mathsf E} [ \tau _ {j} ^ {s} - \tau _ {j} ^ {e} ] ^ {2 + \gamma } $ is uniformly bounded for some $ \gamma > 0 $. Then for each fixed $ z $,

$$ \tag{* } w \left ( \frac{z}{a} \right ) \rightarrow \ e ^ {- 2 z / \sigma ^ {2} } . $$

This relation allows the approximate calculation of $ w ( x) $ for small values of $ a $. The limit system, corresponding to $ a = 0 $, is critical in the sense that for it there is no non-degenerate limit distribution $ w ( x) $, and $ w ( x) = 1 $ for each $ x > 0 $( the waiting time of the $ n $- th client increases unboundedly as $ n $ increases). Relation (*) can be extended to a broad class of queues with waiting under very general assumptions on the control sequences.

The emergence of queueing theory has produced an interest in the novel mathematical problems which arise in the organization of telephone networks. The first publication in this connection is due to A. Erlang in 1907. The later development of queueing theory occurred in the 1940's and 1950's in papers by C. Palm, F. Pollaczek, A.Ya. Khinchin, and others. The last coined the term "queue" . In the USSR, work on queueing theory was continued by B.V. Gnedenko, with a group of his students, and others.

The development of queueing theory has been stimulated both by a variety of applications and by the mathematical content of the problems that arise. Although formally a part of the theory of random processes, queueing theory has evolved into an independent area of research with its own problems and methods of solution.

References

[1] A.Ya. Khinchin, "Mathematical methods in the theory of queueing" , Griffin (1960) (Translated from Russian)
[2] B.V. Gnedenko, I.N. Kovalenko, "Introduction to queueing theory" , Israel Program Sci. Transl. (1968) (Translated from Russian)
[3] A.A. Borovkov, "Stochastic processes in queueing theory" , Springer (1976) (Translated from Russian)
[4] A.A. Borovkov, "Asymptotic methods in queueing theory" , Wiley (1984) (Translated from Russian)

Comments

A facility for collective use has usually a limited capacity and congestion (loss) arises when the momentary demands of the users surpass the capacity. Facilities for collective use are encountered in a large variety in present day society, e.g. ticket windows, road junctions, beds in a hospital, communication trunks in a telephone network, the central processor unit in a computer.

The need to evaluate the performance of a facility led to the development of queueing theory. The basic model concerns a single-server system and the description of the arrival process, of the service times required by the customers and the service discipline, which specifies the schedule of handling the customers.

The irregularities in the arrival stream and also those in the demands of the service times require for their modelling a probabilistic approach; in fact, they are modelled as stochastic processes. Consequently, performance characteristics such as the waiting time of the $ m $- th arriving customer, the queue length of the $ n $- th arrival and the workload of the server as a function of time have to be analyzed as stochastic processes. Queueing theory studies the relations between these performance characteristics and the input processes (arrival and service times), and as such queueing theory is an important branch of applied probability theory.

The early developments of queueing theory took place in the first decade of the 20th century; congestion phenomena in telephone communication have been the direct impetus. Until 1940 queueing theory has been developed mainly for purposes in telecommunication engineering. The growing interest after 1940 in operations research had a considerable influence on the developments of queueing theory. At present a huge variety of queueing models are studied: many-server models, batch arrivals instead of individual arrivals, group service, and sophisticated service disciplines like random service, priority service, processor sharing, and feedback of customers. Next to a single-service facility, networks of queues require analysis. In a network a customer or a message has to be transported via the nodes connected by links to a certain destination; at the switching nodes congestion may occur. The routing of the customers through the network is usually modelled as a stochastic protocol.

The mathematical analysis concerned with the relations between the performance and model characteristics is the analytical part of queueing theory; simulation techniques are used to study such relations experimentally.

References

[a1] W. Feller, "An introduction to probability theory and its applications", 1–2, Wiley (1966)
[a2] L. Kleinrock, "Queueing systems", 1–2, Wiley (1976)
[a3] J.W. Cohen, "The single server queue", North-Holland (1982) pp. Chapt. II.1
[a4] R. Syski, "Congestion theory", North-Holland (1986)
How to Cite This Entry:
Queueing theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Queueing_theory&oldid=37785
This article was adapted from an original article by A.A. Borovkov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article