# Queueing theory

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.

How to Cite This Entry:
Queueing theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Queueing_theory&oldid=48405
This article was adapted from an original article by A.A. Borovkov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article