Namespaces
Variants
Actions

Difference between revisions of "Queue, multi-channel with waiting"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(latex details)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 +
<!--
 +
q0768201.png
 +
$#A+1 = 228 n = 0
 +
$#C+1 = 228 : ~/encyclopedia/old_files/data/Q076/Q.0706820 Queue, multi\AAhchannel with waiting,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''multi-server queue''
 
''multi-server queue''
  
 
A queue for which the algorithm provides for the calls to form a queue if the system is busy at the time of their arrival; here the service of calls takes place in several channels simultaneously. The basic definitions and notations are as in [[Queue|Queue]].
 
A queue for which the algorithm provides for the calls to form a queue if the system is busy at the time of their arrival; here the service of calls takes place in several channels simultaneously. The basic definitions and notations are as in [[Queue|Queue]].
  
The operation of a multi-server queue, controlled by a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q0768201.png" />, is as follows. Calls arrive at times <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q0768202.png" />. A time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q0768203.png" /> is spent on the service of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q0768204.png" />-th call, no matter which of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q0768205.png" /> channels serves the call. Calls arrive and are immediately directed (in order of arrival) to a free channel if not all channels are busy, or wait until some channel is free and then proceed into service. For simplicity, let the system be free at time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q0768206.png" />.
+
The operation of a multi-server queue, controlled by a sequence $  \{ \tau _ {j}  ^ {e} , \tau _ {j}  ^ {s} \} $,  
 +
is as follows. Calls arrive at times 0 , \tau _ {1}  ^ {e} , \tau _ {1}  ^ {e} + \tau _ {2}  ^ {e} ,\dots $.  
 +
A time $  \tau _ {j}  ^ {s} $
 +
is spent on the service of the $  j $-
 +
th call, no matter which of the $  m \geq  1 $
 +
channels serves the call. Calls arrive and are immediately directed (in order of arrival) to a free channel if not all channels are busy, or wait until some channel is free and then proceed into service. For simplicity, let the system be free at time $  t = 0 $.
  
1) For clarity of exposition the following notation is used: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q0768207.png" /> is the vector of waiting times of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q0768208.png" />-th call, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q0768209.png" /> is the time this call must wait until <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682010.png" /> channels are free of calls which arrived before it, so <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682011.png" /> is the  "actual"  waiting time. In addition, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682012.png" />,
+
1) For clarity of exposition the following notation is used: $  \mathbf w _ {n} = ( w _ {n,1} \dots w _ {n,m} ) $
 +
is the vector of waiting times of the $  n $-
 +
th call, where $  w _ {n,i} $
 +
is the time this call must wait until $  i $
 +
channels are free of calls which arrived before it, so $  w _ {n,1} $
 +
is the  "actual"  waiting time. In addition, let $  x  ^ {+} = \max ( 0 , x ) $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682013.png" /></td> </tr></table>
+
$$
 +
\mathbf x  ^ {+}  = \
 +
( x _ {1}  ^ {+} \dots x _ {m}  ^ {+} ) ,\  \mathbf e  = \
 +
( 1 , 0 \dots 0 ) ,\  \mathbf i  = ( 1 \dots 1 ) ,
 +
$$
  
and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682014.png" /> be the vector obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682015.png" /> by placing the coordinates in increasing order (so the first coordinate of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682016.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682017.png" />). Then the following recurrence relation holds for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682018.png" />, generalizing the one-dimensional case:
+
and let $  \mathbf R ( \mathbf x ) $
 +
be the vector obtained from $  \mathbf x $
 +
by placing the coordinates in increasing order (so the first coordinate of $  \mathbf R ( \mathbf x ) $
 +
is $  \min ( x _ {1} \dots x _ {m} ) $).  
 +
Then the following recurrence relation holds for $  \mathbf w _ {n} $,  
 +
generalizing the one-dimensional case:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682019.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
\mathbf w _ {n+1}  = [ \mathbf R ( \mathbf w _ {n} + \tau _ {n}  ^ {s} \mathbf e ) -
 +
\tau _ {n}  ^ {e} \mathbf i ]  ^ {+} .
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682021.png" />, then there is a proper sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682022.png" /> which satisfies (1) and is such that the distribution function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682023.png" /> converges monotone to the distribution function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682024.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682025.png" />. This result has a generalization to the case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682026.png" /> and can also be extended to the queue length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682027.png" /> at the time of arrival of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682028.png" />-th call (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682029.png" /> is the queue length excluding calls in service). There are formulas connecting the limit distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682030.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682031.png" />.
+
If $  \{ \tau _ {j}  ^ {e} , \tau _ {j}  ^ {s} \} \in G _ {S} $
 +
and $  {\mathsf E} ( \tau _ {n}  ^ {s} - m \tau _ {n}  ^ {e} ) < 0 $,  
 +
then there is a proper sequence $  \{ w  ^ {k} \} \in G _ {S} $
 +
which satisfies (1) and is such that the distribution function of $  \mathbf w _ {n} $
 +
converges monotone to the distribution function of $  \mathbf w _ {n}  ^ {0} $
 +
as $  n \rightarrow \infty $.  
 +
This result has a generalization to the case $  \nu _ {j}  ^ {e} \not\equiv 1 $
 +
and can also be extended to the queue length q _ {n} $
 +
at the time of arrival of the $  n $-
 +
th call ( q _ {n} $
 +
is the queue length excluding calls in service). There are formulas connecting the limit distributions of $  \mathbf w _ {n} $
 +
and q _ {n} $.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682033.png" />, then (1) allows one to write an integral equation for the stationary distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682034.png" />. In this case it is possible to also give simple relations between the stationary distribution of the queue length and the waiting time. Specifically, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682035.png" /> denotes the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682036.png" />-th coordinate of the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682037.png" />, then for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682038.png" />,
+
If $  \{ \tau _ {j}  ^ {e} \} \in G _ {I} $,  
 +
$  \{ \tau _ {j}  ^ {s} \} \in G _ {I} $,  
 +
then (1) allows one to write an integral equation for the stationary distribution of $  \mathbf w  ^ {0} $.  
 +
In this case it is possible to also give simple relations between the stationary distribution of the queue length and the waiting time. Specifically, if $  w _ {k}  ^ {0} $
 +
denotes the $  k $-
 +
th coordinate of the vector $  \mathbf w  ^ {0} $,  
 +
then for $  k \geq  m - 1 $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682039.png" /></td> </tr></table>
+
$$
 +
\lim\limits _ {n \rightarrow \infty } \
 +
{\mathsf P} \{ q _ {n} > k \}  = {\mathsf P} \{ w _ {1}  ^ {e} > \tau _ {1}  ^ {e} + \dots + \tau _ {k-m+ 1}  ^ {e} \} .
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682040.png" />, then
+
If $  m > k \geq  0 $,  
 +
then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682041.png" /></td> </tr></table>
+
$$
 +
\lim\limits _ {n \rightarrow \infty } \
 +
{\mathsf P} \{ q _ {n} \geq  m - k \}  = {\mathsf P} \{ w _ {k+1}  ^ {0} > 0 \} .
 +
$$
  
 
Here, all random variables under the probability sign are independent.
 
Here, all random variables under the probability sign are independent.
  
If, in addition, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682042.png" /> has a non-lattice distribution, similar formulas are true for the limit distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682043.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682044.png" />, then
+
If, in addition, $  \tau _ {j}  ^ {e} $
 +
has a non-lattice distribution, similar formulas are true for the limit distribution of q ( t) $.  
 +
If $  \{ \tau _ {j}  ^ {e} \} \in E $,  
 +
then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682045.png" /></td> </tr></table>
+
$$
 +
\lim\limits _ {n \rightarrow \infty } \
 +
{\mathsf P} \{ q _ {n} = k \} \
 +
= \lim\limits _ {t \rightarrow \infty } \
 +
{\mathsf P} \{ q ( t) = k \} .
 +
$$
  
2) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682046.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682047.png" />, then it is possible to give explicit formulas for the limit distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682049.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682050.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682051.png" /> be the index of the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682052.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682053.png" />. Then the numbers
+
2) If $  \{ \tau _ {j}  ^ {e} \} \in G _ {I} $,  
 +
$  \{ \tau _ {j}  ^ {s} \} \in E $,  
 +
then it is possible to give explicit formulas for the limit distribution of q _ {n} $,  
 +
q ( t) $
 +
and $  \mathbf w _ {n} $.  
 +
Let $  \alpha $
 +
be the index of the distribution of $  \tau _ {j}  ^ {s} $
 +
and let $  \alpha m {\mathsf E} \tau  ^ {e} > 1 $.  
 +
Then the numbers
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682054.png" /></td> </tr></table>
+
$$
 +
p _ {k}  = \lim\limits _ {n \rightarrow \infty }  {\mathsf P} \{ q _ {n} = k \}
 +
$$
  
can be described explicitly by rational functions of the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682055.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682056.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682057.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682058.png" /> is the unique root in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682059.png" /> of the equation
+
can be described explicitly by rational functions of the values $  \mu $
 +
and $  \psi ( - j \alpha ) $,  
 +
$  j= 1 \dots m $,  
 +
where $  \mu $
 +
is the unique root in $  | \mu | < 1 $
 +
of the equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682060.png" /></td> </tr></table>
+
$$
 +
\mu  = \psi ( ( \mu - 1 ) m \alpha ) ,\ \
 +
\psi ( \mu )  = {\mathsf E} e ^ {\mu \tau  ^ {e} } .
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682061.png" />, then
+
If $  k > m $,  
 +
then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682062.png" /></td> </tr></table>
+
$$
 +
p _ {k}  = A \mu  ^ {k-m} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682063.png" /> does not depend on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682064.png" />. For the limit distribution of the waiting time,
+
where $  A $
 +
does not depend on $  k $.  
 +
For the limit distribution of the waiting time,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682065.png" /></td> </tr></table>
+
$$
 +
W ( x)  = \lim\limits _ {n \rightarrow \infty } \
 +
{\mathsf P} \{ w _ {n,1} > x \}  = \
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682066.png" /> is a non-lattice random variable, then
+
\frac{A e ^ {- m \alpha ( 1 - \mu ) x } }{1 - \mu }
 +
.
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682067.png" /></td> </tr></table>
+
If  $  \tau _ {j}  ^ {e} $
 +
is a non-lattice random variable, then
 +
 
 +
$$
 +
\lim\limits _ {t \rightarrow \infty } \
 +
{\mathsf P} \{ q ( t) = k \}  = p _ {k}  $$
  
 
exists, where
 
exists, where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682068.png" /></td> </tr></table>
+
$$
 +
p _ {k}  = \
 +
 
 +
\frac{p _ {k-1} }{k \alpha {\mathsf E} \tau  ^ {e} }
 +
\ \
 +
\textrm{ for }  1 \leq  k < m ,
 +
$$
 +
 
 +
$$
 +
p _ {k}  =
 +
\frac{p _ {k-1} }{m \alpha {\mathsf E} \tau  ^ {e} }
 +
\  \textrm{ for }  k \geq  m .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682069.png" /></td> </tr></table>
+
In case  $  \{ \tau _ {j}  ^ {e} \} \in E $,
 +
$  \{ \tau _ {j}  ^ {s} \} \in E $,
  
In case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682070.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682071.png" />,
+
$$
 +
p _ {k}  = \
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682072.png" /></td> </tr></table>
+
\frac{p _ {0} }{k ! m  ^ {k} }
 +
\lambda  ^ {k} \ \
 +
\textrm{ for }  1 \leq  k \leq  m ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682073.png" /></td> </tr></table>
+
$$
 +
p _ {k}  =
 +
\frac{p _ {0} }{m ! m  ^ {m} }
 +
\lambda  ^ {k} \  \textrm{ for }  k \geq  m ,
 +
$$
  
 
where
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682074.png" /></td> </tr></table>
+
$$
 +
\lambda  = \
 +
 
 +
\frac{1}{\alpha m {\mathsf E} \tau  ^ {e} }
 +
  < 1 .
 +
$$
  
3) Stability theorems (about the continuous dependence of the stationary distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682075.png" /> on the distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682076.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682077.png" />) are obtained in a less general form than for single-server systems, and are connected with a condition on the existence of so-called renewal events. However, in case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682078.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682079.png" />, the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682080.png" />, must be satisfied. If for such systems, in triangular arrays, the distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682081.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682082.png" /> converge weakly to the distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682083.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682084.png" />, respectively, and, in addition, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682085.png" />, then the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682086.png" /> will converge weakly to the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682087.png" />.
+
3) Stability theorems (about the continuous dependence of the stationary distributions of $  \mathbf w  ^ {0} $
 +
on the distributions of $  \tau _ {j}  ^ {e} $
 +
and $  \tau _ {j}  ^ {s} $)  
 +
are obtained in a less general form than for single-server systems, and are connected with a condition on the existence of so-called renewal events. However, in case $  \{ \tau _ {j}  ^ {e} \} \in G _ {I} $,  
 +
$  \{ \tau _ {j}  ^ {s} \} \in G _ {I} $,  
 +
the condition $  {\mathsf E} ( \tau _ {n}  ^ {s} - m \tau _ {n}  ^ {e} ) < 0 $,  
 +
must be satisfied. If for such systems, in triangular arrays, the distributions of $  \tau _ {j}  ^ {(n)} e $
 +
and $  \tau _ {j}  ^ {(n)} s $
 +
converge weakly to the distributions of $  \tau _ {j}  ^ {e} $
 +
and $  \tau _ {j}  ^ {s} $,  
 +
respectively, and, in addition, $  {\mathsf E} \tau _ {j}  ^ {(n)} s \rightarrow {\mathsf E} \tau _ {j}  ^ {s} $,  
 +
then the distribution of $  \mathbf w  ^ {(n)} 0 $
 +
will converge weakly to the distribution of $  \mathbf w  ^ {0} $.
  
 
4) Asymptotic methods used in the analysis of multi-server systems with heavy traffic give results similar to the corresponding results for single-server systems.
 
4) Asymptotic methods used in the analysis of multi-server systems with heavy traffic give results similar to the corresponding results for single-server systems.
  
In a series of control sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682088.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682089.png" />, let
+
In a series of control sequences $  \{ \tau _ {j}  ^ {e} \} \in G _ {I} $,
 +
$  \{ \tau _ {j}  ^ {s} \} \in G _ {I} $,
 +
let
 +
 
 +
$$
 +
\delta  =
 +
\frac{1}{ {\mathsf E} \tau  ^ {e} }
 +
-
 +
 
 +
\frac{m}{ {\mathsf E} \tau  ^ {s} }
 +
  \rightarrow  0
 +
$$
 +
 
 +
( $  \delta $
 +
is the difference between the mean number of calls joining the system and the mean number of calls which the system can serve in unit time: if  $  \nu _ {j}  ^ {e} \not\equiv 1 $,
 +
$  \nu _ {j}  ^ {s} \not\equiv 1 $,
 +
then  $  \delta $
 +
can be taken to be the number  $  {\mathsf E} \nu  ^ {e} / {\mathsf E} \tau  ^ {e} - m {\mathsf E} \nu  ^ {s} / {\mathsf E} \tau  ^ {s} $,  
 +
which has the same meaning). Now if
 +
 
 +
$$
 +
 
 +
\frac{ {\mathsf D} \tau  ^ {e} }{( {\mathsf E} \tau  ^ {e} )  ^ {3} }
 +
+
 +
m
 +
\frac{ {\mathsf D} \tau  ^ {s} }{( {\mathsf E} \tau  ^ {s} )  ^ {3} }
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682090.png" /></td> </tr></table>
+
\rightarrow  \sigma  ^ {2}  > 0
 +
$$
  
(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682091.png" /> is the difference between the mean number of calls joining the system and the mean number of calls which the system can serve in unit time: if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682092.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682093.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682094.png" /> can be taken to be the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682095.png" />, which has the same meaning). Now if
+
and $  {\mathsf E} | \tau  ^ {e} | ^ {2 + \epsilon } $,
 +
$  {\mathsf E} | \tau  ^ {s} | ^ {2 + \epsilon } $
 +
are uniformly bounded for some  $  \epsilon > 0 $,  
 +
then the following holds as  $  t \rightarrow \infty $,
 +
$  \delta \rightarrow 0 $
 +
for the queue length  $  q ( t) $
 +
at time  $  t $:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682096.png" /></td> </tr></table>
+
for  $  \delta \sqrt t \rightarrow v $,
 +
$  v \geq  - \infty $,
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682097.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682098.png" /> are uniformly bounded for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q07682099.png" />, then the following holds as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820100.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820101.png" /> for the queue length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820102.png" /> at time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820103.png" />:
+
$$
 +
\lim\limits _ {\delta \rightarrow 0 } \
 +
{\mathsf P} \left \{ q ( t) <  
 +
\frac{x}{| \delta | }
 +
\right \} =
 +
$$
  
for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820104.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820105.png" />,
+
$$
 +
= \
 +
{\mathsf P} \left \{ w ( u) <  
 +
\frac{x - u  \mathop{\rm sign} \
 +
\delta } \sigma
 +
\mid  0 \leq  u \leq  v  ^ {2} \right \} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820106.png" /></td> </tr></table>
+
where  $  w ( u) $
 +
is a standard [[Wiener process|Wiener process]];
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820107.png" /></td> </tr></table>
+
for  $  \delta \sqrt t \rightarrow 0 $,
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820108.png" /> is a standard [[Wiener process|Wiener process]];
+
$$
 +
\lim\limits _ {t \rightarrow \infty } \
 +
{\mathsf P} \{ q ( t) < x \sqrt t \}  = \sqrt {
 +
\frac{2} \pi
 +
}
 +
\int\limits _ { 0 } ^ { {x }  / \sigma }
 +
e ^ {- u  ^ {2} /2 }  d u ;
 +
$$
  
for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820109.png" />,
+
for $  \delta \sqrt t \rightarrow \infty $,
 +
$  \delta > 0 $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820110.png" /></td> </tr></table>
+
$$
 +
\lim\limits _ {t \rightarrow \infty } \
 +
{\mathsf P} \{ q ( t) < \delta t + x \sqrt t \}  = \
  
for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820111.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820112.png" />,
+
\frac{1}{\sqrt {2 \pi } }
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820113.png" /></td> </tr></table>
+
\int\limits _ {- \infty } ^ { {x }  / \sigma }
 +
e ^ {- u  ^ {2} /2 }  d u .
 +
$$
  
Similar relations are true for the queue length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820114.png" /> and the waiting time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820115.png" />.
+
Similar relations are true for the queue length q _ {n} $
 +
and the waiting time $  \mathbf w _ {n} $.
  
Another possible direction for asymptotic investigation of multi-server systems is the study of systems with intensive input stream and an unboundedly increasing (with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820116.png" />) number of service channels.
+
Another possible direction for asymptotic investigation of multi-server systems is the study of systems with intensive input stream and an unboundedly increasing (with $  {\mathsf E} ( e ( 1) - e ( 0) ) $)
 +
number of service channels.
  
5) The behaviour of multi-server systems with an infinite number of service channels and with a control sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820117.png" /> is described in the same way as the behaviour of multi-server systems with waiting; the only difference being that here there is always a free channel and, consequently, the waiting time for any call is equal to zero. As a characteristic of the state of the system one takes the number of busy lines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820118.png" /> at the time of arrival of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820119.png" />-th call or the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820120.png" /> of busy lines at time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820121.png" /> (as everywhere above, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820122.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820123.png" /> are the queue lengths and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820124.png" />).
+
5) The behaviour of multi-server systems with an infinite number of service channels and with a control sequence $  \{ \tau _ {j}  ^ {e} , \tau _ {j}  ^ {s} \} $
 +
is described in the same way as the behaviour of multi-server systems with waiting; the only difference being that here there is always a free channel and, consequently, the waiting time for any call is equal to zero. As a characteristic of the state of the system one takes the number of busy lines q _ {n} $
 +
at the time of arrival of the $  n $-
 +
th call or the number q ( t) $
 +
of busy lines at time $  t $(
 +
as everywhere above, q _ {n} $
 +
and q ( t) $
 +
are the queue lengths and $  q _ {1} = 0 $).
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820125.png" /> and, in addition, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820126.png" /> be metrically transitive. Then, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820127.png" />, the distribution of the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820128.png" /> converges monotone, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820129.png" />, to the distribution of the strictly stationary sequence
+
Let $  \{ \tau _ {j}  ^ {e} , \tau _ {j}  ^ {s} \} \in G _ {S} $
 +
and, in addition, let $  \{ \tau _ {j}  ^ {e} \} $
 +
be metrically transitive. Then, if $  {\mathsf E} \tau _ {j}  ^ {s} < \infty $,  
 +
the distribution of the sequence $  \{ {q _ {n+k}} : {k \geq  0 } \} $
 +
converges monotone, as $  n \rightarrow \infty $,  
 +
to the distribution of the strictly stationary sequence
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820130.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
q  ^ {k}  = \sum_{i=0}^  \infty 
 +
I \{ \tau _ {k-1}  ^ {s} > \tau _ {k-l}  ^ {e} + \dots + \tau _ {k}  ^ {e} \} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820131.png" /> is the indicator of the event <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820132.png" />. The condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820133.png" /> is nearly a necessary condition for the finiteness of (2).
+
where $  I \{ A \} $
 +
is the indicator of the event $  A $.  
 +
The condition $  {\mathsf E} \tau _ {j}  ^ {s} < \infty $
 +
is nearly a necessary condition for the finiteness of (2).
  
6) For systems in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820134.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820135.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820136.png" />, the distribution of the stationary queue length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820137.png" /> can be described with the help of equations. For this, one introduces the variable
+
6) For systems in which $  m = \infty $,  
 +
$  \{ \tau _ {j}  ^ {e} \} \in G _ {I} $,  
 +
$  \{ \tau _ {j}  ^ {s} \} \in G _ {I} $,  
 +
the distribution of the stationary queue length q ^ {k} $
 +
can be described with the help of equations. For this, one introduces the variable
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820138.png" /></td> </tr></table>
+
$$
 +
q  ^ {0} ( x)  = \sum_{k=0}^  \infty 
 +
I \{ \tau _ {k}  ^ {s} > x + \tau _ {0}  ^ {e} + \dots + \tau _ {k}  ^ {e} \} .
 +
$$
  
The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820139.png" /> indicates how many calls are in the system operating in a stationary regime, if one goes back to a time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820140.png" /> after the arrival of a certain call but not counting that call and the calls arriving after it.
+
The number $  q  ^ {0} ( x) $
 +
indicates how many calls are in the system operating in a stationary regime, if one goes back to a time $  x $
 +
after the arrival of a certain call but not counting that call and the calls arriving after it.
  
 
Denoting
 
Denoting
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820141.png" /></td> </tr></table>
+
$$
 +
P _ {j} ( x)  = {\mathsf P} \{ q  ^ {0} ( x) = j \} ,\ \
 +
j = 0 , 1 \dots
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820142.png" /></td> </tr></table>
+
$$
 +
P ( x)  = {\mathsf P} \{ \tau  ^ {s} > x \} ,\ \
 +
F ( x)  = {\mathsf P} \{ \tau  ^ {e} < x \} ,
 +
$$
  
 
one obtains
 
one obtains
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820143.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ q  ^ {k} = j \}  = {\mathsf P} \{ q  ^ {0} ( 0) =
 +
j \}  = P _ {j} ( 0) ;
 +
$$
  
the system of functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820144.png" /> satisfies the equations
+
the system of functions $  P _ {j} ( x) $
 +
satisfies the equations
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820145.png" /></td> </tr></table>
+
$$
 +
P _ {k} ( x)  = \
 +
\int\limits _ { 0 } ^  \infty 
 +
d F ( t) P ( t + x ) P _ {k-1} ( t + x ) +
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820146.png" /></td> </tr></table>
+
$$
 +
+
 +
\int\limits _ { 0 } ^  \infty  d F ( t) ( 1 - P ( t + x )
 +
) P _ {k} ( t + x ) ,\  k = 1 , 2 ,\dots .
 +
$$
  
Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820147.png" /> must be equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820148.png" />. Each of the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820149.png" /> equations of this system, relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820150.png" />, has a unique solution in the class of functions of bounded variation with the properties
+
Here $  P _ {-1} ( x) $
 +
must be equal to 0 $.  
 +
Each of the first $  k + 1 $
 +
equations of this system, relative to $  P _ {0} ( x) \dots P _ {k} ( x) $,  
 +
has a unique solution in the class of functions of bounded variation with the properties
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820151.png" /></td> </tr></table>
+
$$
 +
P _ {0} ( x)  \rightarrow  1 ,\ \
 +
P _ {i} ( x)  \rightarrow  0 \ \
 +
\textrm{ as }  i \geq  1 ,\ \
 +
x \rightarrow \infty .
 +
$$
  
Similar results hold for the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820152.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820153.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820154.png" />, then
+
Similar results hold for the distribution of q ( t) $.  
 +
If $  \{ \tau _ {j}  ^ {e} \} \in E $,  
 +
$  \{ \tau _ {j}  ^ {s} \} \in G $,  
 +
then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820155.png" /></td> </tr></table>
+
$$
 +
\lim\limits _ {t \rightarrow \infty } \
 +
{\mathsf P} \{ q ( t) = k \}  = \lim\limits _ {t \rightarrow \infty } \
 +
{\mathsf P} \{ q _ {n} = k \}  =
 +
\frac{( a \alpha )  ^ {k} }{k!}
 +
e ^ {- a \alpha } ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820156.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820157.png" /> is the exponent of the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820158.png" />.
+
where $  a = {\mathsf E} \tau _ {j}  ^ {s} $
 +
and $  \alpha $
 +
is the exponent of the distribution of $  \tau _ {j}  ^ {e} $.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820159.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820160.png" />, then
+
If $  \{ \tau _ {j}  ^ {e} \} \in G _ {I} $,  
 +
$  \{ \tau _ {j}  ^ {s} \} \in E $,  
 +
then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820161.png" /></td> </tr></table>
+
$$
 +
P _ {k}  = \
 +
\lim\limits _ {n \rightarrow \infty } \
 +
{\mathsf P} \{ q _ {n} = k \} = \sum_{j=k}^  \infty 
 +
( - 1 )  ^ {j-k}
 +
\left ( \begin{array}{c}
 +
j \\
 +
k
 +
\end{array}
 +
\right ) C _ {j} ,
 +
$$
  
 
where
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820162.png" /></td> </tr></table>
+
$$
 +
C _ {0}  = 1 ,\  C _ {j}  = \prod_{j=1}^ { j }
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820163.png" /></td> </tr></table>
+
\frac{\psi ( - l \alpha ) }{1 - \psi ( - l \alpha ) }
 +
;
 +
$$
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820164.png" /> is the exponent of the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820165.png" />. If, in addition, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820166.png" /> is a non-lattice random variable, then
+
$$
 +
j = 1 , 2 \dots \  \psi ( \lambda )  = {\mathsf E} e ^ {\lambda \tau  ^ {e} } ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820167.png" /></td> </tr></table>
+
and  $  \alpha $
 +
is the exponent of the distribution of  $  \tau _ {j}  ^ {s} $.
 +
If, in addition,  $  \tau _ {j}  ^ {e} $
 +
is a non-lattice random variable, then
  
7) Stability theorems in the case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820168.png" />, as in the preceding sections, give conditions under which a small change in the control sequences leads to a small change in the stationary distribution of the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820169.png" /> of busy lines.
+
$$
 +
\lim\limits _ {t \rightarrow \infty } \
 +
{\mathsf P} \{ q ( t) = k \} \
 +
=
 +
\frac{P _ {k-1} }{k \alpha {\mathsf E} \tau  ^ {e} }
 +
,\ \
 +
k = 1 , 2 ,\dots .
 +
$$
  
For triangular arrays, when the system is controlled by a stationary sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820170.png" /> depending on a parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820171.png" /> let the following conditions hold.
+
7) Stability theorems in the case  $  m = \infty $,  
 +
as in the preceding sections, give conditions under which a small change in the control sequences leads to a small change in the stationary distribution of the number  $  q _ {n} $
 +
of busy lines.
  
A) There is a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820172.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820173.png" /> is metrically transitive, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820174.png" /> and the finite-dimensional distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820175.png" /> converge to the distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820176.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820177.png" />.
+
For triangular arrays, when the system is controlled by a stationary sequence $  \{ \tau  ^ {(n)} e , \tau  ^ {(n)} s \} $
 +
depending on a parameter  $  n = 1 , 2 \dots $
 +
let the following conditions hold.
  
B) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820178.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820179.png" />.
+
A) There is a sequence  $  \{ \tau _ {j}  ^ {e} , \tau _ {j}  ^ {s} \} \in G _ {S} $
 +
such that  $  \{ \tau _ {j}  ^ {e} \} $
 +
is metrically transitive,  $  {\mathsf E} \tau _ {j}  ^ {s} < \infty $
 +
and the finite-dimensional distributions of  $  \{ \tau _ {j}  ^ {(n)} e , \tau _ {j}  ^ {(n)} s \} $
 +
converge to the distributions of  $  \{ \tau _ {j}  ^ {e} , \tau _ {j}  ^ {s} \} $
 +
as $  n \rightarrow \infty $.
  
C) The distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820180.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820181.png" /> are continuous at the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820182.png" />.
+
B) $  {\mathsf E} \tau _ {j}  ^ {(n)} s \rightarrow {\mathsf E} \tau _ {j}  ^ {s} $
 +
as  $  n \rightarrow \infty $.
  
The stability theorem then asserts that under conditions A)–C) the distributions of the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820183.png" /> of queue lengths (defined by (2) with respect to the control sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820184.png" />) converge to the distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820185.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820186.png" />.
+
C) The distributions of $  \tau _ {-j}  ^ {s} - \sum _ {k=-j}  ^ {0} \tau _ {k}  ^ {e} $
 +
for all  $  j \geq  0 $
 +
are continuous at the point  $  0 $.
  
All three conditions A), B) and C) in this result are essential; the failure of any one of these immediately allows the construction of examples where the distributions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820187.png" /> do not converge.
+
The stability theorem then asserts that under conditions A)–C) the distributions of the sequence  $  \{ q  ^ {(n)} k \} $
 +
of queue lengths (defined by (2) with respect to the control sequence  $  \{ \tau _ {j}  ^ {(n)} e , \tau _ {j}  ^ {(n)} s \} $)
 +
converge to the distributions of  $  \{ q  ^ {k} \} $
 +
as  $  n \rightarrow \infty $.
 +
 
 +
All three conditions A), B) and C) in this result are essential; the failure of any one of these immediately allows the construction of examples where the distributions of $  \{ q ^ {(n)} k \} $
 +
do not converge.
  
 
8) Asymptotic analysis of systems with an infinite number of service channels is natural and effective in the study of so-called traffic systems, when the input stream has high intensity. The advantage of the asymptotic approach lies in the great generality and universality of the laws established.
 
8) Asymptotic analysis of systems with an infinite number of service channels is natural and effective in the study of so-called traffic systems, when the input stream has high intensity. The advantage of the asymptotic approach lies in the great generality and universality of the laws established.
  
Let the input stream <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820188.png" />, denoting the number of calls arriving in the system up to time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820189.png" />, depend on a parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820190.png" /> (a triangular array), so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820191.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820192.png" /> for each fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820193.png" /> and, in addition, let there exist a non-decreasing function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820194.png" />, a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820195.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820196.png" /> and a continuous random process <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820197.png" />, defined on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820198.png" />, such that the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820199.png" />, where
+
Let the input stream $  e ( t) = e _ {T} ( t) $,  
 +
denoting the number of calls arriving in the system up to time $  t $,  
 +
depend on a parameter $  T \rightarrow \infty $(
 +
a triangular array), so that $  e _ {T} ( t) \rightarrow \infty $
 +
as $  T \rightarrow \infty $
 +
for each fixed $  t > 0 $
 +
and, in addition, let there exist a non-decreasing function $  m ( t) $,  
 +
a function $  B ( T) \rightarrow \infty $
 +
as $  T \rightarrow \infty $
 +
and a continuous random process $  \xi ( t) $,  
 +
defined on $  [ 0 , t _ {0} ] $,  
 +
such that the distribution of $  f ( \xi _ {T} ( t) ) $,
 +
where
 +
 
 +
$$
 +
\xi _ {T} ( t)  = \
 +
 
 +
\frac{e _ {T} ( t) - T _ {m} ( t) }{B ( t) }
 +
,
 +
$$
 +
 
 +
converges weakly to the distribution of  $  f ( \xi ( t) ) $
 +
as  $  T \rightarrow \infty $,
 +
for any functional  $  f $
 +
which is measurable and continuous in the uniform metric.
 +
 
 +
For example, if  $  \{ \tau _ {j} \} \in G _ {I} $
 +
and if the control of the system is via a sequence  $  \tau _ {j}  ^ {e} = \tau _ {j} / T $,
 +
then the condition stated will be satisfied for any  $  t _ {0} $,
 +
where
 +
 
 +
$$
 +
m ( t)  = \
 +
 
 +
\frac{t}{ {\mathsf E} \tau _ {j} }
 +
,\ \
 +
B  ^ {2} ( T)  = \
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820200.png" /></td> </tr></table>
+
\frac{T {\mathsf D} \tau _ {j} }{( {\mathsf E} \tau _ {j} )  ^ {3} }
 +
,
 +
$$
  
converges weakly to the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820201.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820202.png" />, for any functional <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820203.png" /> which is measurable and continuous in the uniform metric.
+
and  $  \xi ( t) $
 +
is a standard Wiener process.
  
For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820204.png" /> and if the control of the system is via a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820205.png" />, then the condition stated will be satisfied for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820206.png" />, where
+
Regarding the service mechanism it is assumed that  $  \{ \tau _ {j}  ^ {e} \} \in G _ {I} $.  
 +
Then:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820207.png" /></td> </tr></table>
+
a) If  $  B ( T) / \sqrt T \rightarrow \infty $,
 +
then the finite-dimensional distributions of the normalized queue
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820208.png" /> is a standard Wiener process.
+
$$
 +
z _ {1} ( t)  = \
  
Regarding the service mechanism it is assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820209.png" />. Then:
+
\frac{q ( t) - T Q ( t) }{B ( t) }
 +
,
 +
$$
  
a) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820210.png" />, then the finite-dimensional distributions of the normalized queue
+
$$
 +
Q ( t) = \int\limits _ { 0 } ^  \infty  G ( t - u )  d m
 +
( u) ,\  G ( t)  = {\mathsf P} \{ \tau _ {j}  ^ {s} \geq  t \} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820211.png" /></td> </tr></table>
+
converge weakly as  $  T \rightarrow \infty $
 +
to the distributions of the process
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820212.png" /></td> </tr></table>
+
$$
 +
\zeta _ {1} ( t)  = \
 +
\int\limits _ { 0 } ^ { t }
 +
G ( t - u )  d \xi ( u) .
 +
$$
  
converge weakly as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820213.png" /> to the distributions of the process
+
b) If  $  B ( T) / \sqrt E \rightarrow \sigma \geq  0 $,
 +
then the finite-dimensional distributions of the process
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820214.png" /></td> </tr></table>
+
$$
 +
z _ {2} ( t)  = \
  
b) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820215.png" />, then the finite-dimensional distributions of the process
+
\frac{q ( t) - T Q ( t) }{\sqrt T }
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820216.png" /></td> </tr></table>
+
$$
  
 
converge weakly to the finite-dimensional distributions of the process
 
converge weakly to the finite-dimensional distributions of the process
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820217.png" /></td> </tr></table>
+
$$
 +
\zeta _ {2} ( t)  = \
 +
\theta ( t) + \sigma
 +
\int\limits _ { 0 } ^ { t }
 +
G ( t - u )  d \xi ( u) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820218.png" /> is a centred [[Gaussian process|Gaussian process]] not depending on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820219.png" /> with covariance function
+
where $  \theta ( t) $
 +
is a centred [[Gaussian process|Gaussian process]] not depending on $  \xi ( t) $
 +
with covariance function
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820220.png" /></td> </tr></table>
+
$$
 +
{\mathsf E} \theta ( t) \theta ( t + u )  = \
 +
\int\limits _ { 0 } ^ { t }
 +
F ( t + u - v ) ( 1 - G ( t - v ) )  d m ( v) .
 +
$$
  
If the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820221.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820222.png" /> are required to have some degree of smoothness, then the convergence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820223.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820224.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820225.png" />, holds even in a stronger sense (for example, convergence of the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820226.png" /> to that of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820227.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076820/q076820228.png" /> for all functionals continuous relative to the uniform metric).
+
If the functions $  m ( t) $
 +
or $  G ( t) $
 +
are required to have some degree of smoothness, then the convergence of $  z _ {i} ( t) $
 +
to $  \zeta _ {i} ( t) $,
 +
$  i = 1 , 2 $,  
 +
holds even in a stronger sense (for example, convergence of the distribution of $  f ( z _ {i} ( t) ) $
 +
to that of $  f ( \zeta _ {i} ( t) ) $
 +
as $  T \rightarrow \infty $
 +
for all functionals continuous relative to the uniform metric).
  
 
For references see [[Queueing theory|Queueing theory]].
 
For references see [[Queueing theory|Queueing theory]].

Latest revision as of 19:29, 16 January 2024


multi-server queue

A queue for which the algorithm provides for the calls to form a queue if the system is busy at the time of their arrival; here the service of calls takes place in several channels simultaneously. The basic definitions and notations are as in Queue.

The operation of a multi-server queue, controlled by a sequence $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} $, is as follows. Calls arrive at times $ 0 , \tau _ {1} ^ {e} , \tau _ {1} ^ {e} + \tau _ {2} ^ {e} ,\dots $. A time $ \tau _ {j} ^ {s} $ is spent on the service of the $ j $- th call, no matter which of the $ m \geq 1 $ channels serves the call. Calls arrive and are immediately directed (in order of arrival) to a free channel if not all channels are busy, or wait until some channel is free and then proceed into service. For simplicity, let the system be free at time $ t = 0 $.

1) For clarity of exposition the following notation is used: $ \mathbf w _ {n} = ( w _ {n,1} \dots w _ {n,m} ) $ is the vector of waiting times of the $ n $- th call, where $ w _ {n,i} $ is the time this call must wait until $ i $ channels are free of calls which arrived before it, so $ w _ {n,1} $ is the "actual" waiting time. In addition, let $ x ^ {+} = \max ( 0 , x ) $,

$$ \mathbf x ^ {+} = \ ( x _ {1} ^ {+} \dots x _ {m} ^ {+} ) ,\ \mathbf e = \ ( 1 , 0 \dots 0 ) ,\ \mathbf i = ( 1 \dots 1 ) , $$

and let $ \mathbf R ( \mathbf x ) $ be the vector obtained from $ \mathbf x $ by placing the coordinates in increasing order (so the first coordinate of $ \mathbf R ( \mathbf x ) $ is $ \min ( x _ {1} \dots x _ {m} ) $). Then the following recurrence relation holds for $ \mathbf w _ {n} $, generalizing the one-dimensional case:

$$ \tag{1 } \mathbf w _ {n+1} = [ \mathbf R ( \mathbf w _ {n} + \tau _ {n} ^ {s} \mathbf e ) - \tau _ {n} ^ {e} \mathbf i ] ^ {+} . $$

If $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} \in G _ {S} $ and $ {\mathsf E} ( \tau _ {n} ^ {s} - m \tau _ {n} ^ {e} ) < 0 $, then there is a proper sequence $ \{ w ^ {k} \} \in G _ {S} $ which satisfies (1) and is such that the distribution function of $ \mathbf w _ {n} $ converges monotone to the distribution function of $ \mathbf w _ {n} ^ {0} $ as $ n \rightarrow \infty $. This result has a generalization to the case $ \nu _ {j} ^ {e} \not\equiv 1 $ and can also be extended to the queue length $ q _ {n} $ at the time of arrival of the $ n $- th call ( $ q _ {n} $ is the queue length excluding calls in service). There are formulas connecting the limit distributions of $ \mathbf w _ {n} $ and $ q _ {n} $.

If $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $, $ \{ \tau _ {j} ^ {s} \} \in G _ {I} $, then (1) allows one to write an integral equation for the stationary distribution of $ \mathbf w ^ {0} $. In this case it is possible to also give simple relations between the stationary distribution of the queue length and the waiting time. Specifically, if $ w _ {k} ^ {0} $ denotes the $ k $- th coordinate of the vector $ \mathbf w ^ {0} $, then for $ k \geq m - 1 $,

$$ \lim\limits _ {n \rightarrow \infty } \ {\mathsf P} \{ q _ {n} > k \} = {\mathsf P} \{ w _ {1} ^ {e} > \tau _ {1} ^ {e} + \dots + \tau _ {k-m+ 1} ^ {e} \} . $$

If $ m > k \geq 0 $, then

$$ \lim\limits _ {n \rightarrow \infty } \ {\mathsf P} \{ q _ {n} \geq m - k \} = {\mathsf P} \{ w _ {k+1} ^ {0} > 0 \} . $$

Here, all random variables under the probability sign are independent.

If, in addition, $ \tau _ {j} ^ {e} $ has a non-lattice distribution, similar formulas are true for the limit distribution of $ q ( t) $. If $ \{ \tau _ {j} ^ {e} \} \in E $, then

$$ \lim\limits _ {n \rightarrow \infty } \ {\mathsf P} \{ q _ {n} = k \} \ = \lim\limits _ {t \rightarrow \infty } \ {\mathsf P} \{ q ( t) = k \} . $$

2) If $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $, $ \{ \tau _ {j} ^ {s} \} \in E $, then it is possible to give explicit formulas for the limit distribution of $ q _ {n} $, $ q ( t) $ and $ \mathbf w _ {n} $. Let $ \alpha $ be the index of the distribution of $ \tau _ {j} ^ {s} $ and let $ \alpha m {\mathsf E} \tau ^ {e} > 1 $. Then the numbers

$$ p _ {k} = \lim\limits _ {n \rightarrow \infty } {\mathsf P} \{ q _ {n} = k \} $$

can be described explicitly by rational functions of the values $ \mu $ and $ \psi ( - j \alpha ) $, $ j= 1 \dots m $, where $ \mu $ is the unique root in $ | \mu | < 1 $ of the equation

$$ \mu = \psi ( ( \mu - 1 ) m \alpha ) ,\ \ \psi ( \mu ) = {\mathsf E} e ^ {\mu \tau ^ {e} } . $$

If $ k > m $, then

$$ p _ {k} = A \mu ^ {k-m} , $$

where $ A $ does not depend on $ k $. For the limit distribution of the waiting time,

$$ W ( x) = \lim\limits _ {n \rightarrow \infty } \ {\mathsf P} \{ w _ {n,1} > x \} = \ \frac{A e ^ {- m \alpha ( 1 - \mu ) x } }{1 - \mu } . $$

If $ \tau _ {j} ^ {e} $ is a non-lattice random variable, then

$$ \lim\limits _ {t \rightarrow \infty } \ {\mathsf P} \{ q ( t) = k \} = p _ {k} $$

exists, where

$$ p _ {k} = \ \frac{p _ {k-1} }{k \alpha {\mathsf E} \tau ^ {e} } \ \ \textrm{ for } 1 \leq k < m , $$

$$ p _ {k} = \frac{p _ {k-1} }{m \alpha {\mathsf E} \tau ^ {e} } \ \textrm{ for } k \geq m . $$

In case $ \{ \tau _ {j} ^ {e} \} \in E $, $ \{ \tau _ {j} ^ {s} \} \in E $,

$$ p _ {k} = \ \frac{p _ {0} }{k ! m ^ {k} } \lambda ^ {k} \ \ \textrm{ for } 1 \leq k \leq m , $$

$$ p _ {k} = \frac{p _ {0} }{m ! m ^ {m} } \lambda ^ {k} \ \textrm{ for } k \geq m , $$

where

$$ \lambda = \ \frac{1}{\alpha m {\mathsf E} \tau ^ {e} } < 1 . $$

3) Stability theorems (about the continuous dependence of the stationary distributions of $ \mathbf w ^ {0} $ on the distributions of $ \tau _ {j} ^ {e} $ and $ \tau _ {j} ^ {s} $) are obtained in a less general form than for single-server systems, and are connected with a condition on the existence of so-called renewal events. However, in case $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $, $ \{ \tau _ {j} ^ {s} \} \in G _ {I} $, the condition $ {\mathsf E} ( \tau _ {n} ^ {s} - m \tau _ {n} ^ {e} ) < 0 $, must be satisfied. If for such systems, in triangular arrays, the distributions of $ \tau _ {j} ^ {(n)} e $ and $ \tau _ {j} ^ {(n)} s $ converge weakly to the distributions of $ \tau _ {j} ^ {e} $ and $ \tau _ {j} ^ {s} $, respectively, and, in addition, $ {\mathsf E} \tau _ {j} ^ {(n)} s \rightarrow {\mathsf E} \tau _ {j} ^ {s} $, then the distribution of $ \mathbf w ^ {(n)} 0 $ will converge weakly to the distribution of $ \mathbf w ^ {0} $.

4) Asymptotic methods used in the analysis of multi-server systems with heavy traffic give results similar to the corresponding results for single-server systems.

In a series of control sequences $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $, $ \{ \tau _ {j} ^ {s} \} \in G _ {I} $, let

$$ \delta = \frac{1}{ {\mathsf E} \tau ^ {e} } - \frac{m}{ {\mathsf E} \tau ^ {s} } \rightarrow 0 $$

( $ \delta $ is the difference between the mean number of calls joining the system and the mean number of calls which the system can serve in unit time: if $ \nu _ {j} ^ {e} \not\equiv 1 $, $ \nu _ {j} ^ {s} \not\equiv 1 $, then $ \delta $ can be taken to be the number $ {\mathsf E} \nu ^ {e} / {\mathsf E} \tau ^ {e} - m {\mathsf E} \nu ^ {s} / {\mathsf E} \tau ^ {s} $, which has the same meaning). Now if

$$ \frac{ {\mathsf D} \tau ^ {e} }{( {\mathsf E} \tau ^ {e} ) ^ {3} } + m \frac{ {\mathsf D} \tau ^ {s} }{( {\mathsf E} \tau ^ {s} ) ^ {3} } \rightarrow \sigma ^ {2} > 0 $$

and $ {\mathsf E} | \tau ^ {e} | ^ {2 + \epsilon } $, $ {\mathsf E} | \tau ^ {s} | ^ {2 + \epsilon } $ are uniformly bounded for some $ \epsilon > 0 $, then the following holds as $ t \rightarrow \infty $, $ \delta \rightarrow 0 $ for the queue length $ q ( t) $ at time $ t $:

for $ \delta \sqrt t \rightarrow v $, $ v \geq - \infty $,

$$ \lim\limits _ {\delta \rightarrow 0 } \ {\mathsf P} \left \{ q ( t) < \frac{x}{| \delta | } \right \} = $$

$$ = \ {\mathsf P} \left \{ w ( u) < \frac{x - u \mathop{\rm sign} \ \delta } \sigma \mid 0 \leq u \leq v ^ {2} \right \} , $$

where $ w ( u) $ is a standard Wiener process;

for $ \delta \sqrt t \rightarrow 0 $,

$$ \lim\limits _ {t \rightarrow \infty } \ {\mathsf P} \{ q ( t) < x \sqrt t \} = \sqrt { \frac{2} \pi } \int\limits _ { 0 } ^ { {x } / \sigma } e ^ {- u ^ {2} /2 } d u ; $$

for $ \delta \sqrt t \rightarrow \infty $, $ \delta > 0 $,

$$ \lim\limits _ {t \rightarrow \infty } \ {\mathsf P} \{ q ( t) < \delta t + x \sqrt t \} = \ \frac{1}{\sqrt {2 \pi } } \int\limits _ {- \infty } ^ { {x } / \sigma } e ^ {- u ^ {2} /2 } d u . $$

Similar relations are true for the queue length $ q _ {n} $ and the waiting time $ \mathbf w _ {n} $.

Another possible direction for asymptotic investigation of multi-server systems is the study of systems with intensive input stream and an unboundedly increasing (with $ {\mathsf E} ( e ( 1) - e ( 0) ) $) number of service channels.

5) The behaviour of multi-server systems with an infinite number of service channels and with a control sequence $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} $ is described in the same way as the behaviour of multi-server systems with waiting; the only difference being that here there is always a free channel and, consequently, the waiting time for any call is equal to zero. As a characteristic of the state of the system one takes the number of busy lines $ q _ {n} $ at the time of arrival of the $ n $- th call or the number $ q ( t) $ of busy lines at time $ t $( as everywhere above, $ q _ {n} $ and $ q ( t) $ are the queue lengths and $ q _ {1} = 0 $).

Let $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} \in G _ {S} $ and, in addition, let $ \{ \tau _ {j} ^ {e} \} $ be metrically transitive. Then, if $ {\mathsf E} \tau _ {j} ^ {s} < \infty $, the distribution of the sequence $ \{ {q _ {n+k}} : {k \geq 0 } \} $ converges monotone, as $ n \rightarrow \infty $, to the distribution of the strictly stationary sequence

$$ \tag{2 } q ^ {k} = \sum_{i=0}^ \infty I \{ \tau _ {k-1} ^ {s} > \tau _ {k-l} ^ {e} + \dots + \tau _ {k} ^ {e} \} , $$

where $ I \{ A \} $ is the indicator of the event $ A $. The condition $ {\mathsf E} \tau _ {j} ^ {s} < \infty $ is nearly a necessary condition for the finiteness of (2).

6) For systems in which $ m = \infty $, $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $, $ \{ \tau _ {j} ^ {s} \} \in G _ {I} $, the distribution of the stationary queue length $ q ^ {k} $ can be described with the help of equations. For this, one introduces the variable

$$ q ^ {0} ( x) = \sum_{k=0}^ \infty I \{ \tau _ {k} ^ {s} > x + \tau _ {0} ^ {e} + \dots + \tau _ {k} ^ {e} \} . $$

The number $ q ^ {0} ( x) $ indicates how many calls are in the system operating in a stationary regime, if one goes back to a time $ x $ after the arrival of a certain call but not counting that call and the calls arriving after it.

Denoting

$$ P _ {j} ( x) = {\mathsf P} \{ q ^ {0} ( x) = j \} ,\ \ j = 0 , 1 \dots $$

$$ P ( x) = {\mathsf P} \{ \tau ^ {s} > x \} ,\ \ F ( x) = {\mathsf P} \{ \tau ^ {e} < x \} , $$

one obtains

$$ {\mathsf P} \{ q ^ {k} = j \} = {\mathsf P} \{ q ^ {0} ( 0) = j \} = P _ {j} ( 0) ; $$

the system of functions $ P _ {j} ( x) $ satisfies the equations

$$ P _ {k} ( x) = \ \int\limits _ { 0 } ^ \infty d F ( t) P ( t + x ) P _ {k-1} ( t + x ) + $$

$$ + \int\limits _ { 0 } ^ \infty d F ( t) ( 1 - P ( t + x ) ) P _ {k} ( t + x ) ,\ k = 1 , 2 ,\dots . $$

Here $ P _ {-1} ( x) $ must be equal to $ 0 $. Each of the first $ k + 1 $ equations of this system, relative to $ P _ {0} ( x) \dots P _ {k} ( x) $, has a unique solution in the class of functions of bounded variation with the properties

$$ P _ {0} ( x) \rightarrow 1 ,\ \ P _ {i} ( x) \rightarrow 0 \ \ \textrm{ as } i \geq 1 ,\ \ x \rightarrow \infty . $$

Similar results hold for the distribution of $ q ( t) $. If $ \{ \tau _ {j} ^ {e} \} \in E $, $ \{ \tau _ {j} ^ {s} \} \in G $, then

$$ \lim\limits _ {t \rightarrow \infty } \ {\mathsf P} \{ q ( t) = k \} = \lim\limits _ {t \rightarrow \infty } \ {\mathsf P} \{ q _ {n} = k \} = \frac{( a \alpha ) ^ {k} }{k!} e ^ {- a \alpha } , $$

where $ a = {\mathsf E} \tau _ {j} ^ {s} $ and $ \alpha $ is the exponent of the distribution of $ \tau _ {j} ^ {e} $.

If $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $, $ \{ \tau _ {j} ^ {s} \} \in E $, then

$$ P _ {k} = \ \lim\limits _ {n \rightarrow \infty } \ {\mathsf P} \{ q _ {n} = k \} = \sum_{j=k}^ \infty ( - 1 ) ^ {j-k} \left ( \begin{array}{c} j \\ k \end{array} \right ) C _ {j} , $$

where

$$ C _ {0} = 1 ,\ C _ {j} = \prod_{j=1}^ { j } \frac{\psi ( - l \alpha ) }{1 - \psi ( - l \alpha ) } ; $$

$$ j = 1 , 2 \dots \ \psi ( \lambda ) = {\mathsf E} e ^ {\lambda \tau ^ {e} } , $$

and $ \alpha $ is the exponent of the distribution of $ \tau _ {j} ^ {s} $. If, in addition, $ \tau _ {j} ^ {e} $ is a non-lattice random variable, then

$$ \lim\limits _ {t \rightarrow \infty } \ {\mathsf P} \{ q ( t) = k \} \ = \frac{P _ {k-1} }{k \alpha {\mathsf E} \tau ^ {e} } ,\ \ k = 1 , 2 ,\dots . $$

7) Stability theorems in the case $ m = \infty $, as in the preceding sections, give conditions under which a small change in the control sequences leads to a small change in the stationary distribution of the number $ q _ {n} $ of busy lines.

For triangular arrays, when the system is controlled by a stationary sequence $ \{ \tau ^ {(n)} e , \tau ^ {(n)} s \} $ depending on a parameter $ n = 1 , 2 \dots $ let the following conditions hold.

A) There is a sequence $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} \in G _ {S} $ such that $ \{ \tau _ {j} ^ {e} \} $ is metrically transitive, $ {\mathsf E} \tau _ {j} ^ {s} < \infty $ and the finite-dimensional distributions of $ \{ \tau _ {j} ^ {(n)} e , \tau _ {j} ^ {(n)} s \} $ converge to the distributions of $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} $ as $ n \rightarrow \infty $.

B) $ {\mathsf E} \tau _ {j} ^ {(n)} s \rightarrow {\mathsf E} \tau _ {j} ^ {s} $ as $ n \rightarrow \infty $.

C) The distributions of $ \tau _ {-j} ^ {s} - \sum _ {k=-j} ^ {0} \tau _ {k} ^ {e} $ for all $ j \geq 0 $ are continuous at the point $ 0 $.

The stability theorem then asserts that under conditions A)–C) the distributions of the sequence $ \{ q ^ {(n)} k \} $ of queue lengths (defined by (2) with respect to the control sequence $ \{ \tau _ {j} ^ {(n)} e , \tau _ {j} ^ {(n)} s \} $) converge to the distributions of $ \{ q ^ {k} \} $ as $ n \rightarrow \infty $.

All three conditions A), B) and C) in this result are essential; the failure of any one of these immediately allows the construction of examples where the distributions of $ \{ q ^ {(n)} k \} $ do not converge.

8) Asymptotic analysis of systems with an infinite number of service channels is natural and effective in the study of so-called traffic systems, when the input stream has high intensity. The advantage of the asymptotic approach lies in the great generality and universality of the laws established.

Let the input stream $ e ( t) = e _ {T} ( t) $, denoting the number of calls arriving in the system up to time $ t $, depend on a parameter $ T \rightarrow \infty $( a triangular array), so that $ e _ {T} ( t) \rightarrow \infty $ as $ T \rightarrow \infty $ for each fixed $ t > 0 $ and, in addition, let there exist a non-decreasing function $ m ( t) $, a function $ B ( T) \rightarrow \infty $ as $ T \rightarrow \infty $ and a continuous random process $ \xi ( t) $, defined on $ [ 0 , t _ {0} ] $, such that the distribution of $ f ( \xi _ {T} ( t) ) $, where

$$ \xi _ {T} ( t) = \ \frac{e _ {T} ( t) - T _ {m} ( t) }{B ( t) } , $$

converges weakly to the distribution of $ f ( \xi ( t) ) $ as $ T \rightarrow \infty $, for any functional $ f $ which is measurable and continuous in the uniform metric.

For example, if $ \{ \tau _ {j} \} \in G _ {I} $ and if the control of the system is via a sequence $ \tau _ {j} ^ {e} = \tau _ {j} / T $, then the condition stated will be satisfied for any $ t _ {0} $, where

$$ m ( t) = \ \frac{t}{ {\mathsf E} \tau _ {j} } ,\ \ B ^ {2} ( T) = \ \frac{T {\mathsf D} \tau _ {j} }{( {\mathsf E} \tau _ {j} ) ^ {3} } , $$

and $ \xi ( t) $ is a standard Wiener process.

Regarding the service mechanism it is assumed that $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $. Then:

a) If $ B ( T) / \sqrt T \rightarrow \infty $, then the finite-dimensional distributions of the normalized queue

$$ z _ {1} ( t) = \ \frac{q ( t) - T Q ( t) }{B ( t) } , $$

$$ Q ( t) = \int\limits _ { 0 } ^ \infty G ( t - u ) d m ( u) ,\ G ( t) = {\mathsf P} \{ \tau _ {j} ^ {s} \geq t \} , $$

converge weakly as $ T \rightarrow \infty $ to the distributions of the process

$$ \zeta _ {1} ( t) = \ \int\limits _ { 0 } ^ { t } G ( t - u ) d \xi ( u) . $$

b) If $ B ( T) / \sqrt E \rightarrow \sigma \geq 0 $, then the finite-dimensional distributions of the process

$$ z _ {2} ( t) = \ \frac{q ( t) - T Q ( t) }{\sqrt T } $$

converge weakly to the finite-dimensional distributions of the process

$$ \zeta _ {2} ( t) = \ \theta ( t) + \sigma \int\limits _ { 0 } ^ { t } G ( t - u ) d \xi ( u) , $$

where $ \theta ( t) $ is a centred Gaussian process not depending on $ \xi ( t) $ with covariance function

$$ {\mathsf E} \theta ( t) \theta ( t + u ) = \ \int\limits _ { 0 } ^ { t } F ( t + u - v ) ( 1 - G ( t - v ) ) d m ( v) . $$

If the functions $ m ( t) $ or $ G ( t) $ are required to have some degree of smoothness, then the convergence of $ z _ {i} ( t) $ to $ \zeta _ {i} ( t) $, $ i = 1 , 2 $, holds even in a stronger sense (for example, convergence of the distribution of $ f ( z _ {i} ( t) ) $ to that of $ f ( \zeta _ {i} ( t) ) $ as $ T \rightarrow \infty $ for all functionals continuous relative to the uniform metric).

For references see Queueing theory.

How to Cite This Entry:
Queue, multi-channel with waiting. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Queue,_multi-channel_with_waiting&oldid=17489
This article was adapted from an original article by A.A. Borovkov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article