Queuing theory

Queuing theory , or queuing theory , is a section of probability theory whose research objective is to rationally select the structure of the service system and the service process based on the study of flows of service requirements entering and leaving the system, waiting times and lengths queues ^[1] . In queuing theory, methods of probability theory and mathematical statistics are used .

Content

History

The theory of the flow of homogeneous events , which formed the basis of the theory of mass service, was developed by the Soviet mathematician A. Ya. Khinchin . ^[2]

The first tasks of the theory of queuing ( TMT ) were considered by an employee of the Copenhagen Telephone Company, a scientist Agner Erlang , between 1908 and 1922. The task was to streamline the work of the telephone exchange and to calculate in advance the quality of customer service depending on the number of devices used.

There is a telephone unit ( service device ) on which telephonists occasionally connect individual telephone numbers to each other. Queuing systems (QS) can be of two types: with expectation and without expectation (that is, with losses). In the first case, the call ( request, request ) that arrives at the station when the desired line is busy is left to wait for the moment of connection. In the second case, he “leaves the system” and does not require the attention of the QS.

Queuing systems are an effective mathematical tool for researching a wide range of real socio-economic ^[3] and demographic processes ^[4] .

Stream

Homogeneous flow

The flow of applications is uniform if:

all applications are equal,
only the time of receipt of applications is considered, that is, the facts of applications without specifying the details of each specific application.

Stream without aftereffect

A stream without aftereffect if the number of events of any time interval ( $t$ ${\ displaystyle t}$ , $t+x$ ${\ displaystyle t + x}$ ) does not depend on the number of events on any other that does not intersect with ours ( $t$ ${\ displaystyle t}$ , $t+x$ ${\ displaystyle t + x}$ ) time interval.

Stationary flow

The flow of applications is stationary if the probability of occurrence of n events in the time interval ( $t$ ${\ displaystyle t}$ , $t+x$ ${\ displaystyle t + x}$ ) does not depend on time $t$ ${\ displaystyle t}$ , but depends only on the length $x$ ${\ displaystyle x}$ of this site.

The simplest stream

A homogeneous stationary flow without aftereffects is the simplest , Poisson flow .

Number $n$ ${\ displaystyle n}$ events of such a stream falling over a length interval $x$ ${\ displaystyle x}$ , distributed according to Poisson's Law :

P(n,x)={\frac {(\lambda x)^{n}e^{-\lambda x}}{n!}}.

{\ displaystyle P (n, x) = {\ frac {(\ lambda x) ^ {n} e ^ {- \ lambda x}} {n!}}.}

The Poisson stream of applications is convenient for solving problems of thermoelectric materials. Strictly speaking, the simplest flows are rare in practice, however, many simulated flows can be considered as simple.

Normal flow

A stationary flow without aftereffects, for which the intervals between events are distributed according to the normal law, is called a normal flow ^[5] : $f(t)={\frac {1}{{\sqrt {2\pi }}\sigma _{t}}}\exp {-{\frac {1}{2}}\left({\frac {t-m_{t}}{\sigma _{t}}}\right)^{2}}$ ${\ displaystyle f (t) = {\ frac {1} {{\ sqrt {2 \ pi}} \ sigma _ {t}}} \ exp {- {\ frac {1} {2}} \ left ({ \ frac {t-m_ {t}} {\ sigma _ {t}}} \ right) ^ {2}}}$ .

Erlang Stream

Erlang stream $k$ ${\ displaystyle k}$ -th order is called a stationary flow without aftereffects, in which the intervals between events are the sum $k+1$ ${\ displaystyle k + 1}$ independent random variables distributed identically exponentially with the parameter $\lambda$ ${\ displaystyle \ lambda}$ ^[6] . At $k=0$ ${\ displaystyle k = 0}$ Erlang flow is the simplest flow.

The distribution density of a random variable of the T-interval between two adjacent events in the Erlang flow $k$ ${\ displaystyle k}$ th order is equal to: $f_{k}(t)={\frac {\lambda (\lambda t)^{k}}{\Gamma (\alpha )}}\exp {-\beta t}$ ${\ displaystyle f_ {k} (t) = {\ frac {\ lambda (\ lambda t) ^ {k}} {\ Gamma (\ alpha)}} \ exp {- \ beta t}}$ , $t>0,\alpha \geqslant 1$ ${\ displaystyle t> 0, \ alpha \ geqslant 1}$ .

Gamma Stream

A gamma stream is a stationary stream without aftereffects, in which the intervals between events are random variables subject to a gamma distribution with parameters $\alpha$ ${\ displaystyle \ alpha}$ and $\beta$ ${\ displaystyle \ beta}$ : $f(t)={\frac {\beta ^{\alpha }t^{\alpha -1}}{k!}}\exp {-\lambda t}$ ${\ displaystyle f (t) = {\ frac {\ beta ^ {\ alpha} t ^ {\ alpha -1}} {k!}} \ exp {- \ lambda t}}$ , $t>0$ ${\ displaystyle t> 0}$ where $\Gamma (\alpha )=\int _{0}^{\infty }x^{\alpha -1}\exp {-x}dx$ ${\ displaystyle \ Gamma (\ alpha) = \ int _ {0} ^ {\ infty} x ^ {\ alpha -1} \ exp {-x} dx}$ ^[7] .

At $\alpha =k+1$ ${\ displaystyle \ alpha = k + 1}$ gamma stream is Erlang stream $k$ ${\ displaystyle k}$ th order.

Instant Density

The instantaneous density ( intensity ) of the flow is equal to the limit of the ratio of the average number of events per elementary time interval ( $t$ ${\ displaystyle t}$ , $t+x$ ${\ displaystyle t + x}$ ) to the length of the interval ( $x$ ${\ displaystyle x}$ ) when the latter tends to zero.

\lambda (t)=\lim _{x\to 0}\left({\frac {M(t+x)-M(t)}{x}}\right)

{\ displaystyle \ lambda (t) = \ lim _ {x \ to 0} \ left ({\ frac {M (t + x) -M (t)} {x}} \ right)}

or, for the simplest flow,

\lambda ={\frac {M(x)}{x}},

{\ displaystyle \ lambda = {\ frac {M (x)} {x}},}

Where $M(x)$ ${\ displaystyle M (x)}$ equal to the mathematical expectation of the number of events in the interval $x$ ${\ displaystyle x}$ .

Little Formula

N^{*}=\lambda T.

{\ displaystyle N ^ {*} = \ lambda T.}

The average number of applications in the system is equal to the product of the input stream intensity and the average residence time of the application in the system.

Notes

↑ Queuing theory // Mathematical Encyclopedic Dictionary, M., “Soviet Encyclopedia”, 1988, pp. 327–328
↑ Dictionary of Cybernetics / Edited by Academician V. S. Mikhalevich . - 2nd. - Kiev: The main edition of the Ukrainian Soviet Encyclopedia named after M.P. Bazhan, 1989. - S. 486. - 751 p. - (C48). - 50,000 copies. - ISBN 5-88500-008-5 .
↑ Afanasyeva L. G., Rudenko I. V. Service systems GI | G | ∞ and their applications to the analysis of transport models // Probability Theory and its Application. - 2012.Vol. 57 Vol. 3. - S. 427–452.
↑ Nosova MG. Autonomous non-Markov queuing system and its application in demographic problems: dis. ... cand. Fiz.Mat. Sciences: 05.13.18. - Tomsk, 2010 .-- S. 204.
↑ Ovcharov, 1969 , p. 22.
↑ Ovcharov, 1969 , p. 24.
↑ Ovcharov, 1969 , p. 40.

Literature

Ivchenko G.I., Kashtanov V.A., Kovalenko I.N. Queuing theory. - Textbook for universities. - M .: Higher school, 1982. - 256 p. - 20,000 copies.
Kleinrock L. Queuing Theory. Per. from English / Per. I.I. Grushko; ed. IN AND. Neumann. - M .: Mechanical Engineering, 1979. - 432 p. - 10,000 copies.
Matveev V.F., Ushakov V.G. Queuing systems. - M .: Moscow State University, 1984.- 240 p.
Mathematical Encyclopedic Dictionary / Ch. ed. Prokhorov Yu.V. - M .: Soviet Encyclopedia, 1988 .-- 847 p.
Lifshits A.L., Maltz E.A. Statistical modeling of queuing systems / Preface. Corresponding Member USSR Academy of Sciences N.P. Buslenko. - M .: Sov. Radio, 1978.- 248 p.
Ventzel E.S. , Ovcharov L.A. Probability Theory (Chapter 10. Markov Processes. Streams of Events. Queuing Theory). - M .: "Science." The main publishing house of Physics and Mathematics, 1969. - 368 p. - 100,000 copies.
Borovkov A.A. Probabilistic processes in queuing theory. - M .: "Science." The main publishing house of Physics and Mathematics, 1972. - 368 p. - (Theory of Probability and Mathematical Statistics). - 13,000 copies.
Ovcharov L.A. Applied problems of queuing theory. - M .: Mechanical Engineering, 1969 .-- 323 p. - 7500 copies.

[1] Queuing theory // Mathematical Encyclopedic Dictionary, M., “Soviet Encyclopedia”, 1988, pp. 327–328

[cyber-2] Dictionary of Cybernetics / Edited by Academician V. S. Mikhalevich . - 2nd. - Kiev: The main edition of the Ukrainian Soviet Encyclopedia named after M.P. Bazhan, 1989. - S. 486. - 751 p. - (C48). - 50,000 copies. - ISBN 5-88500-008-5 .

[3] Afanasyeva L. G., Rudenko I. V. Service systems GI | G | ∞ and their applications to the analysis of transport models // Probability Theory and its Application. - 2012.Vol. 57 Vol. 3. - S. 427–452.

[4] Nosova MG. Autonomous non-Markov queuing system and its application in demographic problems: dis. ... cand. Fiz.Mat. Sciences: 05.13.18. - Tomsk, 2010 .-- S. 204.

[_6d2992e7085dc491-5] Ovcharov, 1969 , p. 22.

[_6d2992e7085dc497-6] Ovcharov, 1969 , p. 24.

[_6d2998e7085dcee5-7] Ovcharov, 1969 , p. 40.