Namespaces
Variants
Actions

Difference between revisions of "Queue with waiting and one service channel"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
m (fix tex)
 
Line 16: Line 16:
  
 
The most natural characteristics of the state of a queueing system are the following: a) the waiting time  $  w _ {n} $
 
The most natural characteristics of the state of a queueing system are the following: a) the waiting time  $  w _ {n} $
to the beginning of the service of the  $  n $-
+
to the beginning of the service of the  $  n $-th request, and the virtual waiting time  $  w ( t) $,  
th request, and the virtual waiting time  $  w ( t) $,  
 
 
which is defined as the time necessary for the system to be free of the calls which arrived up to time  $  t $;  
 
which is defined as the time necessary for the system to be free of the calls which arrived up to time  $  t $;  
 
b) the queue length  $  q _ {n} $
 
b) the queue length  $  q _ {n} $
at the time of arrival of the  $  n $-
+
at the time of arrival of the  $  n $-th call and the queue length  $  q ( t) $
th call and the queue length  $  q ( t) $
 
 
at time  $  t $.
 
at time  $  t $.
  
Line 29: Line 27:
  
 
$$ \tag{1 }
 
$$ \tag{1 }
w _ {n+} 1 =  \max ( 0 , w _ {n} + \xi _ {n} ) ,\ \  
+
w _ {n+1}  =  \max ( 0 , w _ {n} + \xi _ {n} ) ,\ \  
 
\xi _ {n}  =  \tau _ {n}  ^ {s} - \tau _ {n}  ^ {e} .
 
\xi _ {n}  =  \tau _ {n}  ^ {s} - \tau _ {n}  ^ {e} .
 
$$
 
$$
Line 39: Line 37:
  
 
$$ \tag{2 }
 
$$ \tag{2 }
q _ {n+} 1 =  \max ( 0 , q _ {n} + \nu _ {n}  ^ {e} - \beta _ {n} ) ,
+
q _ {n+1}  =  \max ( 0 , q _ {n} + \nu _ {n}  ^ {e} - \beta _ {n} ) ,
 
$$
 
$$
  
Line 54: Line 52:
 
\left [
 
\left [
 
\tau _ {n}  ^ {e} \alpha
 
\tau _ {n}  ^ {e} \alpha
\sum _ { k= } 1 ^  \infty   
+
\sum _ { k=1 } ^  \infty   
 
( e ^ {i \lambda k } - 1 )
 
( e ^ {i \lambda k } - 1 )
 
{\mathsf P} \{ \nu _ {j}  ^ {s} = k \} \right ] ,
 
{\mathsf P} \{ \nu _ {j}  ^ {s} = k \} \right ] ,
Line 67: Line 65:
  
 
$$ \tag{3 }
 
$$ \tag{3 }
w _ {n+} 1 =  X _ {n} -
+
w _ {n+1}  =  X _ {n} -
 
\min ( - w _ {1} , X _ {1} \dots X _ {n} ) =
 
\min ( - w _ {1} , X _ {1} \dots X _ {n} ) =
 
$$
 
$$
Line 73: Line 71:
 
$$  
 
$$  
 
= \  
 
= \  
\max ( X _ {n} + w _ {1} , X _ {n} - X _ {1} \dots X _ {n} - X _ {n-} 1 , 0 ) .
+
\max ( X _ {n} + w _ {1} , X _ {n} - X _ {1} \dots X _ {n} - X _ {n-1} , 0 ) .
 
$$
 
$$
  
Line 91: Line 89:
 
$$  
 
$$  
 
Y  =  \sup _ {k \geq  0 }  Y _ {k} ,\ \  
 
Y  =  \sup _ {k \geq  0 }  Y _ {k} ,\ \  
Y _ {k}  =  \xi _ {-} k + \dots + \xi _ {-} 1 ,\  Y _ {0}  =  0 .
+
Y _ {k}  =  \xi _ {-k} + \dots + \xi _ {-1} ,\  Y _ {0}  =  0 .
 
$$
 
$$
  
Here the variables  $  \xi _ {-} k $
+
Here the variables  $  \xi _ {-k} $
 
are the elements of the sequence  $  \{ \xi _ {n} \} _ {n = - \infty }  ^  \infty  $
 
are the elements of the sequence  $  \{ \xi _ {n} \} _ {n = - \infty }  ^  \infty  $
which extends  $  \{ \xi _ {n} \} _ {n=} 1 ^  \infty  $
+
which extends  $  \{ \xi _ {n} \} _ {n=1}  ^  \infty  $
 
to a sequence which is stationary on the whole line. In what follows it will be assumed that such an extension has been made for all control sequences.
 
to a sequence which is stationary on the whole line. In what follows it will be assumed that such an extension has been made for all control sequences.
  
Line 103: Line 101:
 
$$  
 
$$  
 
w  ^ {k}  =  \sup  
 
w  ^ {k}  =  \sup  
( 0 , \xi _ {k} , \xi _ {k} + \xi _ {k-} 1 , \xi _ {k} +
+
( 0 , \xi _ {k} , \xi _ {k} + \xi _ {k-1} , \xi _ {k} +
\xi _ {k-} 1 + \xi _ {k-} 2 ,\dots )
+
\xi _ {k-1} + \xi _ {k-2} ,\dots )
 
$$
 
$$
  
Line 122: Line 120:
 
if  $  {\mathsf E} \xi _ {k} < 0 $
 
if  $  {\mathsf E} \xi _ {k} < 0 $
 
or if  $  {\mathsf E} \xi _ {k} = 0 $
 
or if  $  {\mathsf E} \xi _ {k} = 0 $
and  $  \xi _ {k} = \eta _ {k+} 1 - \eta _ {k} $,  
+
and  $  \xi _ {k} = \eta _ {k+1} - \eta _ {k} $,  
 
where  $  \{ \eta _ {k} \} \in G _ {S} $.  
 
where  $  \{ \eta _ {k} \} \in G _ {S} $.  
 
Otherwise
 
Otherwise
Line 281: Line 279:
  
 
$$  
 
$$  
w  ^ {0}  =  \sup ( 0 , \xi _ {0} , \xi _ {0} + \xi _ {-} 1
+
w  ^ {0}  =  \sup ( 0 , \xi _ {0} , \xi _ {0} + \xi _ {-1}
 
,\dots ) ,\  \xi _ {j}  =  \tau _ {j}  ^ {s} - \tau _ {j}  ^ {e} .
 
,\dots ) ,\  \xi _ {j}  =  \tau _ {j}  ^ {s} - \tau _ {j}  ^ {e} .
 
$$
 
$$
Line 432: Line 430:
 
w _ {+} ( \lambda )  = \  
 
w _ {+} ( \lambda )  = \  
  
\frac{Q _ {n} ( \lambda ) }{\prod _ { k= } 1 ^ { n }  ( \lambda - \lambda _ {k} ) }
+
\frac{Q _ {n} ( \lambda ) }{\prod _ { k=1} ^ { n }  ( \lambda - \lambda _ {k} ) }
 
  ,
 
  ,
 
$$
 
$$
Line 462: Line 460:
 
the function  $  ( 1 - f  ) Q _ {n} $
 
the function  $  ( 1 - f  ) Q _ {n} $
 
has  $  n- 1 $
 
has  $  n- 1 $
zeros  $  \lambda _ {1} \dots \lambda _ {n-} 1 $,  
+
zeros  $  \lambda _ {1} \dots \lambda _ {n-1} $,  
 
and
 
and
  
Line 469: Line 467:
 
i \lambda
 
i \lambda
  
\frac{\prod _ { k= } 1 ^ { n- }  1
+
\frac{\prod _ { k=1 } ^ { n- 1}   
 
( \lambda - \lambda _ {k} ) }{Q _ {n} ( \lambda ) ( 1 - f ( \lambda ) ) }
 
( \lambda - \lambda _ {k} ) }{Q _ {n} ( \lambda ) ( 1 - f ( \lambda ) ) }
 
  .
 
  .
Line 491: Line 489:
 
$$  
 
$$  
 
{\mathsf P} \{ Y > x \}  = \  
 
{\mathsf P} \{ Y > x \}  = \  
c _ {1} e  ^ {-} qx ( 1+ o ( 1) ) .
+
c _ {1} e  ^ {-qx} ( 1+ o ( 1) ) .
 
$$
 
$$
  
Line 515: Line 513:
 
are exponentially distributed), whereas, in reality, these assumptions are only approximately satisfied. The question is whether the solution of such  "idealized"  problems is close to the solution of the actual problem.
 
are exponentially distributed), whereas, in reality, these assumptions are only approximately satisfied. The question is whether the solution of such  "idealized"  problems is close to the solution of the actual problem.
  
To obtain a precise statement of the problem, triangular arrays are used, where equation (1) is controlled by stationary sequences (triangular arrays)  $  \xi  ^ {(} n) = \{ {\xi _ {j}  ^ {(} n) } : {- \infty < j < \infty } \} $,  
+
To obtain a precise statement of the problem, triangular arrays are used, where equation (1) is controlled by stationary sequences (triangular arrays)  $  \xi  ^ {( n)} = \{ {\xi _ {j}  ^ {( n)} } : {- \infty < j < \infty } \} $,  
 
$  n = 1 , 2 ,\dots $.  
 
$  n = 1 , 2 ,\dots $.  
 
In addition, one considers a stationary sequence  $  \xi = \{ {\xi _ {j} } : {- \infty < j < \infty } \} $
 
In addition, one considers a stationary sequence  $  \xi = \{ {\xi _ {j} } : {- \infty < j < \infty } \} $
Line 521: Line 519:
  
 
$$  
 
$$  
Y  ^ {(} n)  = \  
+
Y  ^ {( n)} = \  
\sup _ {k \geq  0 }  Y _ {k}  ^ {(} n) ,\ \  
+
\sup _ {k \geq  0 }  Y _ {k}  ^ {( n)} ,\ \  
Y _ {k}  ^ {(} n)  =  \sum _ { j= } 1 ^ { n }  \xi _ {-} j ^ {(} n) .
+
Y _ {k}  ^ {( n)} =  \sum _ { j=1 } ^ { n }  \xi _ {-j}  ^ {( n)} .
 
$$
 
$$
  
 
The answer to the question posed above is given by the following result.
 
The answer to the question posed above is given by the following result.
  
Let the finite-dimensional distributions of  $  \xi  ^ {(} n) $
+
Let the finite-dimensional distributions of  $  \xi  ^ {( n)} $
 
converge weakly to the corresponding distributions of  $  \xi $,  
 
converge weakly to the corresponding distributions of  $  \xi $,  
 
which is assumed to be ergodic, and let  $  {\mathsf E} \xi _ {j} < 0 $.  
 
which is assumed to be ergodic, and let  $  {\mathsf E} \xi _ {j} < 0 $.  
Line 534: Line 532:
  
 
$$ \tag{6 }
 
$$ \tag{6 }
{\mathsf P} \{ Y  ^ {(} n) < t \}  \Rightarrow  {\mathsf P} \{ Y < t \}
+
{\mathsf P} \{ Y  ^ {( n)} < t \}  \Rightarrow  {\mathsf P} \{ Y < t \}
 
$$
 
$$
  
Line 540: Line 538:
  
 
$$  
 
$$  
{\mathsf E} ( \xi _ {j}  ^ {(} n) : \xi _ {j}  ^ {(} n) \geq  0 )  \rightarrow \  
+
{\mathsf E} ( \xi _ {j}  ^ {( n)} : \xi _ {j}  ^ {( n)} \geq  0 )  \rightarrow \  
 
{\mathsf E} ( \xi _ {j} : \xi _ {j} \geq  0 ) .
 
{\mathsf E} ( \xi _ {j} : \xi _ {j} \geq  0 ) .
 
$$
 
$$
Line 560: Line 558:
  
 
The situation is similar for the stationary distribution of the virtual waiting time  $  w  ^ {s} ( t) $.  
 
The situation is similar for the stationary distribution of the virtual waiting time  $  w  ^ {s} ( t) $.  
If the finite-dimensional distributions of the processes  $  Y  ^ {(} n) ( t) \in G _ {IS} $
+
If the finite-dimensional distributions of the processes  $  Y  ^ {( n)} ( t) \in G _ {IS} $
 
converge to the distributions of  $  Y ( t) \in G _ {IS} $
 
converge to the distributions of  $  Y ( t) \in G _ {IS} $
 
and if the sequence  $  \{ \eta _ {k} = Y ( k+ 1) - Y ( k) \} $
 
and if the sequence  $  \{ \eta _ {k} = Y ( k+ 1) - Y ( k) \} $
Line 567: Line 565:
  
 
$$  
 
$$  
\sup _ {t \geq  0 }  Y  ^ {(} n) ( t) \ \  
+
\sup _ {t \geq  0 }  Y  ^ {(n)} ( t) \ \  
 
\textrm{ and } \ \  
 
\textrm{ and } \ \  
 
\sup _ {t \geq  0 }  Y ( t)
 
\sup _ {t \geq  0 }  Y ( t)
Line 575: Line 573:
  
 
$$  
 
$$  
{\mathsf E} \{ {\eta _ {k}  ^ {(} n) } : {\eta _ {k}  ^ {(} n) \geq  0 } \}
+
{\mathsf E} \{ {\eta _ {k}  ^ {(n)} } : {\eta _ {k}  ^ {( n)} \geq  0 } \}
 
  \rightarrow \  
 
  \rightarrow \  
 
{\mathsf E} \{ {\eta _ {k} } : {\eta _ {k} \geq  0 } \}
 
{\mathsf E} \{ {\eta _ {k} } : {\eta _ {k} \geq  0 } \}
Line 636: Line 634:
 
A similar result holds for the stationary distribution of  $  w  ^ {k} $.
 
A similar result holds for the stationary distribution of  $  w  ^ {k} $.
  
If the condition of heavy traffic is imposed on the sequence  $  \{ \xi  ^ {(} n) = \tau _ {j} ^ {( n) e } - \tau _ {j} ^ {( n) e } \} \in G _ {I} $(
+
If the condition of heavy traffic is imposed on the sequence  $  \{ \xi  ^ {(n)} = \tau _ {j} ^ {( n) e } - \tau _ {j} ^ {( n) e } \} \in G _ {I} $(
 
also in a triangular array relative to the parameter  $  n $),  
 
also in a triangular array relative to the parameter  $  n $),  
 
and it is required that
 
and it is required that
  
 
$$ \tag{7 }
 
$$ \tag{7 }
0  >  \alpha _ {n}  =  {\mathsf E} \xi _ {j}  ^ {(} n)  \rightarrow  0 ,\ \  
+
0  >  \alpha _ {n}  =  {\mathsf E} \xi _ {j}  ^ {( n)} \rightarrow  0 ,\ \  
{\mathsf D} \xi _ {j}  ^ {(} n)  \rightarrow  \sigma  ^ {2}  >  0 ,
+
{\mathsf D} \xi _ {j}  ^ {( n)} \rightarrow  \sigma  ^ {2}  >  0 ,
 
$$
 
$$
  
Line 650: Line 648:
 
$$  
 
$$  
 
\lim\limits _ {n \rightarrow \infty } \  
 
\lim\limits _ {n \rightarrow \infty } \  
{\mathsf E} [ ( \xi _ {j}  ^ {(} n) )  ^ {2} :\  
+
{\mathsf E} [ ( \xi _ {j}  ^ {( n)} )  ^ {2} :\  
| \xi _ {j}  ^ {(} n) | > \epsilon \sqrt n ]  =  0
+
| \xi _ {j}  ^ {( n)} | > \epsilon \sqrt n ]  =  0
 
$$
 
$$
  
Line 709: Line 707:
  
 
$$  
 
$$  
q _ {n+} 1 =  \min
+
q _ {n+1}  =  \min
 
( N , \max ( 0 , q _ {n} + \eta _ {n} ) ) ,\ \  
 
( N , \max ( 0 , q _ {n} + \eta _ {n} ) ) ,\ \  
 
n \geq  0.
 
n \geq  0.
Line 718: Line 716:
 
or  $  {\mathsf E} \eta _ {1} = 0 $
 
or  $  {\mathsf E} \eta _ {1} = 0 $
 
and, in the second case,  $  \eta _ {n} $
 
and, in the second case,  $  \eta _ {n} $
cannot be represented in the form  $  \eta _ {n} = \gamma _ {n} - \gamma _ {n-} 1 $
+
cannot be represented in the form  $  \eta _ {n} = \gamma _ {n} - \gamma _ {n-1}$
 
with  $  \{ \gamma _ {n} \} \in G _ {S} $.  
 
with  $  \{ \gamma _ {n} \} \in G _ {S} $.  
 
Under these conditions there exists a limit distribution for  $  q _ {n} $
 
Under these conditions there exists a limit distribution for  $  q _ {n} $

Latest revision as of 16:42, 30 December 2020


single-server queue

A queue for which the algorithm provides for calls which are not served immediately (having found the system busy) to form a queue; in this connection the service of this call (or batch of calls) can begin only after the service of the previous call (or batch of calls, if the service is in batches) is complete. The basic definitions and notations are to be found in Queue.

The most natural characteristics of the state of a queueing system are the following: a) the waiting time $ w _ {n} $ to the beginning of the service of the $ n $-th request, and the virtual waiting time $ w ( t) $, which is defined as the time necessary for the system to be free of the calls which arrived up to time $ t $; b) the queue length $ q _ {n} $ at the time of arrival of the $ n $-th call and the queue length $ q ( t) $ at time $ t $.

1) In the "single" case ( $ \nu _ {j} ^ {e} \equiv 1 $) the values $ w _ {n} $ are connected by the recurrence relations

$$ \tag{1 } w _ {n+1} = \max ( 0 , w _ {n} + \xi _ {n} ) ,\ \ \xi _ {n} = \tau _ {n} ^ {s} - \tau _ {n} ^ {e} . $$

A queueing system in the "multiple" case, when $ \nu _ {j} ^ {e} $, $ \nu _ {j} ^ {s} $ are different from one, may be described by the same type of equation (for the waiting time or queue length). For example, for the queue length $ q _ {n} $ one has the relation

$$ \tag{2 } q _ {n+1} = \max ( 0 , q _ {n} + \nu _ {n} ^ {e} - \beta _ {n} ) , $$

where $ \beta _ {n} $ is the number of calls which can be served during a time $ \tau _ {n} ^ {e} $ under continuous operation of the system. If $ \{ \tau _ {j} ^ {s} \} \in E $, $ \{ \nu _ {j} ^ {s} \} \in G _ {I} $, then the distribution of $ \beta _ {n} $ may be found from the relations

$$ {\mathsf E} _ {\tau _ {n} ^ {e} } e ^ {i \lambda \beta _ {n} } = \ \mathop{\rm exp} \left [ \tau _ {n} ^ {e} \alpha \sum _ { k=1 } ^ \infty ( e ^ {i \lambda k } - 1 ) {\mathsf P} \{ \nu _ {j} ^ {s} = k \} \right ] , $$

where $ \alpha $ is the exponent of the distribution of $ \tau _ {j} ^ {s} $.

If one puts $ X _ {0} = 0 $, $ X _ {n} = \xi _ {1} + \dots + \xi _ {n} $, then the solution of (1) has the form

$$ \tag{3 } w _ {n+1} = X _ {n} - \min ( - w _ {1} , X _ {1} \dots X _ {n} ) = $$

$$ = \ \max ( X _ {n} + w _ {1} , X _ {n} - X _ {1} \dots X _ {n} - X _ {n-1} , 0 ) . $$

Hence it follows that if $ \{ \xi _ {n} \} \in G _ {S} $ and $ {\mathsf P} \{ X _ {n} \in \Delta \} \rightarrow 0 $ for any fixed interval $ \Delta $ as $ n \rightarrow \infty $, then there is a limit distribution for the waiting time:

$$ \lim\limits _ {n \rightarrow \infty } \ {\mathsf P} \{ w _ {n} > x \} = {\mathsf P} \{ Y > x \} , $$

where

$$ Y = \sup _ {k \geq 0 } Y _ {k} ,\ \ Y _ {k} = \xi _ {-k} + \dots + \xi _ {-1} ,\ Y _ {0} = 0 . $$

Here the variables $ \xi _ {-k} $ are the elements of the sequence $ \{ \xi _ {n} \} _ {n = - \infty } ^ \infty $ which extends $ \{ \xi _ {n} \} _ {n=1} ^ \infty $ to a sequence which is stationary on the whole line. In what follows it will be assumed that such an extension has been made for all control sequences.

The values

$$ w ^ {k} = \sup ( 0 , \xi _ {k} , \xi _ {k} + \xi _ {k-1} , \xi _ {k} + \xi _ {k-1} + \xi _ {k-2} ,\dots ) $$

satisfy (1) and have a distribution coinciding with the limit distribution of $ w _ {n} $. This is the stationary waiting time process.

Let $ \{ \xi _ {n} \} \in G _ {S} $ be ergodic ( $ X _ {n} / n \rightarrow {\mathsf E} \xi _ {1} $ with probability $ 1 $). Then

$$ {\mathsf P} \{ Y < \infty \} = \ {\mathsf P} \{ w ^ {k} < \infty \} = 1 $$

if $ {\mathsf E} \xi _ {k} < 0 $ or if $ {\mathsf E} \xi _ {k} = 0 $ and $ \xi _ {k} = \eta _ {k+1} - \eta _ {k} $, where $ \{ \eta _ {k} \} \in G _ {S} $. Otherwise

$$ {\mathsf P} \{ Y = \infty \} = {\mathsf P} \{ w ^ {k} = \infty \} = 1 . $$

If $ \{ \xi _ {n} \} \in G _ {I} $, then

$$ {\mathsf P} \{ Y < \infty \} = 1 $$

if and only if $ {\mathsf E} \xi _ {k} < 0 $( the trivial case $ \xi _ {k} = 0 $ being excluded).

2) As already noted, another possible characteristic of the state of the system is the virtual waiting time $ w ( t) $. Roughly speaking, this is the time which the call arriving at time $ t $ would have to wait until the beginning of its service. Let $ S ( t) $ be the sum of the service times of the calls which arrive in the system up to time $ t $, and let $ X ( t) = S ( t) - t $. An analogue of (3) here is the relation

$$ \tag{4 } w ( t) = X ( t) - \inf _ {0 \leq u \leq t } ( 0 , X ( u) ) . $$

Let $ G _ {IS} $ be the class of processes with stationary increments in the narrow sense and let $ G _ {II} $ be the class of processes with independent increments ( $ G _ {II} $ and $ G _ {IS} $ could here be narrower: for example, it can be supposed that $ G _ {II} $ is the class of generalized Poisson processes with positive jumps and drift $ - 1 $). If the process $ \{ {X ( t) } : {t \geq 0 } \} \in G _ {IS} $, then it can be extended to a process $ \{ {X ( t) } : {- \infty < t < \infty } \} $ given on the whole line and also in $ G _ {IS} $. In this case

$$ \lim\limits _ {t \rightarrow \infty } {\mathsf P} \{ w ( t) > x \} = \ {\mathsf P} \{ \overline{Y}\; > x \} $$

exists, where

$$ \overline{Y}\; = \sup _ {u \geq 0 } Y ( t) ,\ \ Y ( t) = X ( 0) - X (- t) . $$

If, in addition,

$$ {\mathsf E} ( X ( 1) - X ( 0) ) = {\mathsf E} ( Y ( 1) - Y ( 0) ) = a < 0 , $$

then the distribution of the process

$$ w _ {t} ( u) = \{ {w ( t - u ) } : {u \geq 0 } \} $$

converges as $ t \rightarrow \infty $ to the distribution of the process

$$ w ^ {s} ( u) = \sup _ {v \leq u } ( X ( u) - X ( v) ) , $$

which is the strictly stationary virtual waiting time process. Here convergence holds in the strong form:

$$ {\mathsf P} \{ w _ {t} \in B \} \rightarrow {\mathsf P} \{ w ^ {s} \in B \} $$

for any measurable $ B $.

Further, if $ \{ X ( t) \} \in G _ {IS} $ and $ a < 0 $, then $ X ( t) $ has a conditional renewal function $ H _ {0} ( x) $:

$$ H _ {0} ( x) = $$

$$ = \ \int\limits _ { 0 } ^ \infty {\mathsf P} \left \{ 0 \leq X ( u) - X ( 0) < x : X ( 0) = \inf _ {v \leq 0 } X ( v) \right \} d u < \infty ; $$

here

$$ \left . \begin{array}{c} {\mathsf P} \{ w ^ {s} ( u) \geq x \} = - a \frac{d H _ {0} ( x) }{dx} , \\ {\mathsf P} \{ w ^ {s} ( t) = 0 \} = - a . \end{array} \right \} $$

These formulas still hold when $ \nu _ {j} ^ {e} \neq 1 $.

For systems in which $ \{ \tau _ {j} ^ {s} - \tau _ {j} ^ {e} \} \in G _ {I} $ there are simple relations between the distributions of $ w ^ {k} $ and $ w ^ {s} ( t) $.

3) Ergodic theorems for the queue length can be obtained with the help of the corresponding theorems for the waiting time. For example, let the sequence $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {e} \} \in G _ {S} $ be ergodic (metrically transitive). If, in addition, $ {\mathsf E} ( \tau _ {j} ^ {s} - \tau _ {j} ^ {e} ) < 0 $, then there is a (stationary) limit distribution for $ q _ {n} $ such that

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

If $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $, $ \{ \tau _ {j} ^ {s} \} \in G _ {I} $ and $ \tau _ {j} ^ {e} $ has a non-lattice distribution, then

$$ \lim\limits _ {\tau \rightarrow \infty } \ {\mathsf P} \{ q ( t) > k + 1 \} \ = {\mathsf P} \{ w ^ {0} > \tau _ {1} ^ {e} + \dots + \tau _ {k} ^ {e} + \gamma \} ,\ k \geq 0 , $$

$$ \lim\limits _ {\tau \rightarrow 0 } {\mathsf P} \{ q ( t) = 0 \} = - \frac{a}{ {\mathsf E} \tau ^ {e} } , $$

where all the components under the probability sign on the right-hand side are independent, and $ \gamma $ has a density

$$ \frac{ {\mathsf P} \{ \tau _ {j} ^ {e} > x \} }{ {\mathsf E} \tau ^ {e} } , $$

$$ w ^ {0} = \sup ( 0 , \xi _ {0} , \xi _ {0} + \xi _ {-1} ,\dots ) ,\ \xi _ {j} = \tau _ {j} ^ {s} - \tau _ {j} ^ {e} . $$

If $ \{ \tau _ {j} ^ {e} \} \in E $, then the limit distributions of $ q _ {n} $ and $ q ( t) $ coincide.

4) If $ \{ \tau _ {j} ^ {e} \} \in E $, $ \{ \tau _ {j} ^ {s} \} \in G _ {I} $( it is also supposed that $ \nu _ {j} ^ {e} \neq 1 $, $ \{ \nu _ {j} ^ {e} \} \in G _ {I} $), then it is possible to obtain an exact formula for the limit distribution of $ w ( t) $:

$$ {\mathsf P} \{ w ( t) < x \} \ = {\mathsf P} \{ Y ( t) < x \} + $$

$$ + \frac \partial {\partial x } \int\limits _ { 0 } ^ { t } {\mathsf E} \left ( \frac{Y ( u) }{u} : \ Y ( u) < 0 \right ) {\mathsf P} \{ Y ( t - u ) < x \} d u , $$

$$ {\mathsf P} \{ w ( t) = 0 \} = - {\mathsf E} \left ( \frac{ Y ( t) }{t} : Y ( t) < 0 \right ) . $$

For $ a < 0 $ and $ t \rightarrow \infty $ there is the Khinchin–Pollaczek formula for the stationary distribution:

$$ {\mathsf E} e ^ {i \lambda w ^ {s} ( u) } \ = \frac{1 - \alpha {\mathsf E} \theta }{1 - \alpha \frac{\phi ( \lambda ) - 1 }{i \lambda } } ,\ \ \phi ( \lambda ) = {\mathsf E} e ^ {i \lambda \theta } , $$

where $ \theta $ is the jump of the process $ X ( t) $( $ \theta = \tau _ {j} ^ {s} $ if $ \nu _ {j} ^ {e} \equiv 1 $) and $ \alpha $ is the exponent of the distribution of $ \tau _ {j} ^ {e} $.

Let $ T _ {j} $, $ j = 1 , 2 \dots $ be the busy periods of the system (that is, the lengths of the time intervals during which $ w ( t) > 0 $). Then, for the systems considered,

$$ {\mathsf P} \{ T _ {j} \in ( u , u + d u ) \} \ = \frac{1}{\alpha u } {\mathsf P} \{ X ( u) \in ( 0 , d u ) \} . $$

5) For systems in which $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} \in G _ {I} $( it is also assumed that $ \nu _ {j} ^ {e} \neq 1 $, $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} , \nu _ {j} ^ {e} \} \in G _ {I} $), the distribution of $ w ^ {k} $ coincides with the distribution of the variable

$$ Y = \sup ( 0 , \xi _ {1} , \xi _ {1} + \xi _ {2} ,\dots ) . $$

If the distribution of $ \xi _ {j} $ is known, then the distribution of $ Y $ can be found as follows. If $ {\mathsf P} \{ Y < \infty \} = 1 $( this is always true if $ {\mathsf E} \xi _ {j} < 0 $), then the factorization identity

$$ 1 - {\mathsf E} e ^ {i \lambda \xi } = ( 1 - p ) \frac{1 - {\mathsf E} e ^ {i \lambda \chi } }{ {\mathsf E} e ^ {i \lambda Y } } ,\ \ \mathop{\rm Im} \lambda = 0 , $$

holds, where $ p = {\mathsf P} \{ Y < 0 \} $ and $ \chi \leq 0 $ is the size of the first non-positive sum among $ \xi _ {1} , \xi _ {1} + \xi _ {2} ,\dots $. This relation permits one to relate $ {\mathsf E} e ^ {i \lambda Y } $ to the ratio $ w _ {+} ( \lambda ) / w _ {+} ( 0) $ in any identity

$$ \tag{5 } 1 - {\mathsf E} e ^ {i \lambda \xi } = \frac{w _ {-} ( \lambda ) }{w _ {+} ( \lambda ) } ,\ \ \mathop{\rm Im} \lambda = 0 , $$

in which the functions $ w _ \pm ( \lambda ) $ admit a representation

$$ w _ \pm ( \lambda ) = \ \int\limits _ { 0 } ^ { \pm \infty } e ^ {i \lambda t } d V _ \pm ( t) $$

( $ V _ \pm $ are functions of bounded variation). Equality (5) provides the so-called $ V $- factorization of the function $ 1 - {\mathsf E} e ^ {i \lambda \xi } $. It explains the following cases, when it is possible to search for $ {\mathsf E} e ^ {i \lambda Y } $ explicitly.

Assume that $ - \infty < {\mathsf E} \xi < 0 $ and put

$$ f ( \lambda ) = {\mathsf E} e ^ {i \lambda \xi } ,\ \ f _ {+} ( \lambda ) = e ^ {i \lambda \tau ^ {s} } ,\ \ f _ {-} ( \lambda ) = e ^ {- i \lambda \tau ^ {e} } , $$

so that $ f ( \lambda ) = f _ {+} ( \lambda ) f _ {-} ( \lambda ) $.

A) If $ f _ {+} $ is a rational function, $ f _ {+} = P _ {m} / Q _ {n} $, where $ P _ {m} $ and $ Q _ {n} $ are polynomials of degree $ m $ and $ n $, respectively, then in the domain $ \mathop{\rm Im} \lambda < 0 $ the function $ ( 1 - f ) Q _ {n} $ has exactly $ n $ zeros $ \lambda _ {1} \dots \lambda _ {n} $, and

$$ w _ {+} ( \lambda ) = \ \frac{Q _ {n} ( \lambda ) }{\prod _ { k=1} ^ { n } ( \lambda - \lambda _ {k} ) } , $$

$$ {\mathsf E} e ^ {i \lambda Y } = \frac{w _ {+} ( \lambda ) }{w _ {+} ( 0) } . $$

This means that if the distribution of $ \tau ^ {s} $ can be represented as

$$ {\mathsf P} \{ \tau ^ {s} > x \} = \ \sum _ { k } P _ {k} ( x) e ^ {- \alpha _ {k} x } ,\ \ \mathop{\rm Re} \alpha _ {k} > 0 , $$

where $ P _ {k} ( x) $ is a polynomial, then the same type of representation (for other $ \alpha _ {k} $ and $ P _ {k} $, determined by $ \lambda _ {1} \dots \lambda _ {n} $) also holds for $ {\mathsf P} \{ Y < x \} $.

B) If $ f _ {-} = P _ {m} / Q _ {n} $ is a rational function, then in the domain $ \mathop{\rm Im} \lambda > 0 $ the function $ ( 1 - f ) Q _ {n} $ has $ n- 1 $ zeros $ \lambda _ {1} \dots \lambda _ {n-1} $, and

$$ w _ {+} ( \lambda ) = \ i \lambda \frac{\prod _ { k=1 } ^ { n- 1} ( \lambda - \lambda _ {k} ) }{Q _ {n} ( \lambda ) ( 1 - f ( \lambda ) ) } . $$

In addition to these formulas, giving explicit expressions for the distribution of $ Y $, it is also possible, in a broad class of cases, to describe the asymptotic behaviour of $ {\mathsf P} \{ Y > x \} $ as $ x \rightarrow \infty $. Namely, if

$$ \gamma = \ \sup ( \mu : {\mathsf E} e ^ {\mu \xi } \langle \infty ) \rangle 0 $$

and $ {\mathsf E} e ^ {\gamma \xi } > 1 $, then there is a unique root of the equation $ {\mathsf E} e ^ {q \xi } = 1 $. In this case, as $ x \rightarrow \infty $,

$$ {\mathsf P} \{ Y > x \} = \ c _ {1} e ^ {-qx} ( 1+ o ( 1) ) . $$

If $ \gamma = 0 $, $ - \infty < {\mathsf E} \xi < 0 $, then

$$ {\mathsf P} \{ Y > x \} = \ c _ {2} \int\limits _ { x } ^ \infty {\mathsf P} \{ \xi > t \} dt ( 1 + o ( 1) ) . $$

The constants $ c _ {1} $ and $ c _ {2} $ have been found explicitly.

Results similar to those discussed in parts 2)–5) are true even for discrete-time systems, when the time $ t $ and the random variables of the control sequences take only integer values.

6) Stability theorems investigate conditions under which a small change in the finite-dimensional distributions of the control sequences leads to a small change in the stationary distribution of the waiting time or queue length. The importance of stability for queues is explained by the fact that in real problems various assumptions are usually made on the nature of the control sequences (for example, it is assumed that the $ \xi _ {j} $ are independent or that the $ \tau _ {j} ^ {e} $ are exponentially distributed), whereas, in reality, these assumptions are only approximately satisfied. The question is whether the solution of such "idealized" problems is close to the solution of the actual problem.

To obtain a precise statement of the problem, triangular arrays are used, where equation (1) is controlled by stationary sequences (triangular arrays) $ \xi ^ {( n)} = \{ {\xi _ {j} ^ {( n)} } : {- \infty < j < \infty } \} $, $ n = 1 , 2 ,\dots $. In addition, one considers a stationary sequence $ \xi = \{ {\xi _ {j} } : {- \infty < j < \infty } \} $ and puts

$$ Y ^ {( n)} = \ \sup _ {k \geq 0 } Y _ {k} ^ {( n)} ,\ \ Y _ {k} ^ {( n)} = \sum _ { j=1 } ^ { n } \xi _ {-j} ^ {( n)} . $$

The answer to the question posed above is given by the following result.

Let the finite-dimensional distributions of $ \xi ^ {( n)} $ converge weakly to the corresponding distributions of $ \xi $, which is assumed to be ergodic, and let $ {\mathsf E} \xi _ {j} < 0 $. Then for the weak convergence

$$ \tag{6 } {\mathsf P} \{ Y ^ {( n)} < t \} \Rightarrow {\mathsf P} \{ Y < t \} $$

(that is, for the convergence of the distributions of the stationary waiting times) it is sufficient that

$$ {\mathsf E} ( \xi _ {j} ^ {( n)} : \xi _ {j} ^ {( n)} \geq 0 ) \rightarrow \ {\mathsf E} ( \xi _ {j} : \xi _ {j} \geq 0 ) . $$

The stated condition for convergence is almost necessary.

If the control sequences $ \{ \tau _ {j} ^ {( n) e } , \tau _ {j} ^ {( n) s } \} $ and $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} $ are such that $ \tau _ {j} ^ {( n) e } $ and $ \tau _ {j} ^ {( n) s } $ are independent and the distributions of $ \{ \tau _ {j} ^ {( n) e } , \tau _ {j} ^ {( n) s } \} $ converge weakly to the distributions of $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} $, then for (6) it is sufficient that

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

The situation is similar for the stationary distribution of the virtual waiting time $ w ^ {s} ( t) $. If the finite-dimensional distributions of the processes $ Y ^ {( n)} ( t) \in G _ {IS} $ converge to the distributions of $ Y ( t) \in G _ {IS} $ and if the sequence $ \{ \eta _ {k} = Y ( k+ 1) - Y ( k) \} $ is ergodic, $ {\mathsf E} \eta _ {k} = a < 0 $, then for the convergence of the distributions of

$$ \sup _ {t \geq 0 } Y ^ {(n)} ( t) \ \ \textrm{ and } \ \ \sup _ {t \geq 0 } Y ( t) $$

it is sufficient that

$$ {\mathsf E} \{ {\eta _ {k} ^ {(n)} } : {\eta _ {k} ^ {( n)} \geq 0 } \} \rightarrow \ {\mathsf E} \{ {\eta _ {k} } : {\eta _ {k} \geq 0 } \} . $$

7) Asymptotic methods for studying single-server systems (which include stability theorems) give approximate formulas for the case of heavy and light traffic. Let $ \{ Y ( t) \} \in G _ {IS} $. Then the system is said to be in heavy traffic conditions if

$$ a = {\mathsf E} ( Y ( t+ 1) - Y ( t) ) < 0 $$

is close to 0 and in light traffic conditions if $ a $ is close to $ - 1 $.

A precise statement, as in part (6), is again related to the introduction of triangular arrays. Specifically, for heavy traffic one considers processes $ X ^ {a} ( t) $, depending on a parameter $ a \rightarrow 0 $. Let $ X ^ {a} ( t) $ satisfy the conditions of weak dependence, which guarantee that, as $ t \rightarrow \infty $,

$$ {\mathsf E} \left ( \frac{| X ^ {a} ( t) - X ^ {a} ( 0) - at | ^ {2+ \gamma } }{A} \right ) < c t ^ {1 + \gamma / 2 } , $$

$$ \lim\limits _ {t \rightarrow \infty } {\mathsf P} \left \{ \frac{ X ^ {a} ( t) - X ^ {a} ( 0) - at }{\sigma \sqrt t } < x \mid A \right \} = \int\limits _ {- \infty } ^ { x } e ^ {- u ^ {2} / 2 } du , $$

uniformly in $ a $, where

$$ \gamma , c , \sigma > 0 ,\ \ A = \ \left \{ X ^ {a} ( 0) = \inf _ {v \leq 0 } X ^ {a} ( v) \right \} . $$

Then for the stationary virtual waiting time $ w ^ {s} ( t) $, as $ a \rightarrow 0 $ one has

$$ {\mathsf P} \left \{ w ^ {s} ( t) > \frac{x}{| a | } \right \} \rightarrow e ^ {- 2 x / \sigma ^ {2} } . $$

A similar result holds for the stationary distribution of $ w ^ {k} $.

If the condition of heavy traffic is imposed on the sequence $ \{ \xi ^ {(n)} = \tau _ {j} ^ {( n) e } - \tau _ {j} ^ {( n) e } \} \in G _ {I} $( also in a triangular array relative to the parameter $ n $), and it is required that

$$ \tag{7 } 0 > \alpha _ {n} = {\mathsf E} \xi _ {j} ^ {( n)} \rightarrow 0 ,\ \ {\mathsf D} \xi _ {j} ^ {( n)} \rightarrow \sigma ^ {2} > 0 , $$

then it is also possible to give a fairly complete description of the distribution of the limit waiting time $ w _ {n} $, including the so-called transition phenomena. Specifically, in addition to (7), let

$$ \lim\limits _ {n \rightarrow \infty } \ {\mathsf E} [ ( \xi _ {j} ^ {( n)} ) ^ {2} :\ | \xi _ {j} ^ {( n)} | > \epsilon \sqrt n ] = 0 $$

for any $ \epsilon > 0 $. Then, if $ \alpha = \alpha _ {n} \rightarrow 0 $ as $ n \rightarrow \infty $ without changing sign, so that $ n \alpha ^ {2} \rightarrow v ^ {2} $, then

$$ \tag{8 } {\mathsf P} \left \{ w _ {n} < \frac{x}{| \alpha | } \right \} \rightarrow $$

$$ \rightarrow \ {\mathsf P} \left \{ w ( u) < \frac{( x - u \mathop{\rm sign} n \alpha ) } \sigma : 0 \leq u \leq v ^ {2} \right \} , $$

where $ w ( u) $ is a standard Wiener process. The value of the right-hand side of (8) can be explicitly calculated. If $ n \alpha ^ {2} \rightarrow 0 $, then

$$ {\mathsf P} \{ w _ {n} < x \sqrt n \} \rightarrow \ \sqrt { \frac{2} \pi } \int\limits _ { 0 } ^ { {x } / \sigma } e ^ {- u ^ {2} / 2 } du . $$

If $ n \alpha ^ {2} \rightarrow \infty $, $ \alpha > 0 $, then

$$ {\mathsf P} \{ w _ {n} < \alpha n + x \sqrt n \} = \ \frac{1}{\sqrt {2 \pi } } \int\limits _ {- \infty } ^ { {x } / \sigma } e ^ {- u ^ {2} / 2 } du . $$

8) Systems with finite waiting room are characterized as follows: Calls which arrive in the system and find a queue of size $ n \geq N $ are refused and removed from the system. In this case $ q _ {n} \leq N $, and the probability $ {\mathsf P} \{ q _ {n} = N \} $ will be the same as the probability that the $ n $- th call is refused.

Equation (2) must here be changed to an equation of the form

$$ q _ {n+1} = \min ( N , \max ( 0 , q _ {n} + \eta _ {n} ) ) ,\ \ n \geq 0. $$

Let $ \{ \eta _ {n} \} \in G _ {S} $ be metrically transitive. In addition, let the following condition be satisfied: Either $ {\mathsf E} \eta _ {1} \neq 0 $ or $ {\mathsf E} \eta _ {1} = 0 $ and, in the second case, $ \eta _ {n} $ cannot be represented in the form $ \eta _ {n} = \gamma _ {n} - \gamma _ {n-1}$ with $ \{ \gamma _ {n} \} \in G _ {S} $. Under these conditions there exists a limit distribution for $ q _ {n} $ as $ n \rightarrow \infty $.

If, in addition, $ \{ \eta _ {n} \} \in G _ {I} $( this holds, for example, when $ \{ \tau _ {j} ^ {s} \} \in E $ and if the remaining control sequences belong to $ G $), then it is possible to find an explicit form for the stationary distribution of $ q _ {n} $ as $ n \rightarrow \infty $, since in this case $ q _ {n} $ is related to a simple homogeneous Markov chain with a finite state space.

There is also a representation for the stationary distribution:

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

$$ = \ {\mathsf P} \{ \chi ( k - N , k ) = k \} {\mathsf P} \{ \chi ( - N , 1 ) \leq - N \} + $$

$$ + {\mathsf P} \{ \chi ( k- N , k ) = k- N \} {\mathsf P} \{ \chi ( - 1 , N ) \geq N \} , $$

where $ \chi ( - l , m ) $ is the position of a particle leaving 0 and wandering with jumps $ \eta _ {k} $, $ k = 1 , 2 \dots $ to the first exit time from the interval $ ( - l , m ) $. If $ \nu _ {j} ^ {e} \equiv 1 $( that is, if $ {\mathsf P} \{ \eta _ {n} \leq 1 \} = 1 $), then the probability (9) can be expressed explicitly in terms of the distributions of $ \tau _ {j} ^ {e} $ and $ \nu _ {j} ^ {s} $.

9) In systems with autonomous service, in contrast to the usual queueing system, the service of calls may begin only at the times $ 0 , \tau _ {1} ^ {s} , \tau _ {1} ^ {s} + \tau _ {2} ^ {s} \dots $ where $ \tau _ {j} ^ {s} $ are the elements of a control sequence. Thus, calls which find the system free must wait until the next stage of service.

Side by side with the process $ \{ e ( t) \} $, describing the input stream, one considers the process $ \{ s ( t) \} $, where $ s ( t) $ is defined as the number of calls which would be accepted into service up to time $ t $ if the queue could be infinite. Denoting by $ q ( t) $ the length of the queue at time $ t $, not counting calls in service, and putting $ X ( t) = e ( t) - s ( t) $, one obtains

$$ q ( t) = \ q ( 0) + X ( t) - \inf _ {0 \leq u < t } ( 0 , X ( u) + q ( 0) ) = $$

$$ = \ \sup _ {0 \leq u < t } ( q ( 0) + X ( t ) , X ( t) - X ( u) ) . $$

This equality is similar to (4) and leads to the following result. If the process $ \{ X ( t) \} \in G _ {IS} $ is ergodic and

$$ {\mathsf E} ( X ( 1) - X ( 0) ) < 0 , $$

then the distributions of the processes $ \{ {X _ {t} ( u) = X ( t+ u ) } : {u \geq 0 } \} $ converge as $ t \rightarrow \infty $ to the distribution of the stationary process

$$ \overline{X}\; ( u) = \ \sup _ {v \leq u } ( X ( u) - X ( v) ) . $$

If $ \{ \tau _ {j} ^ {s} \} \in E $ or $ \{ \tau _ {j} ^ {e} \} \in E $ and the remaining control sequences belong to $ G _ {I} $, it is possible to give explicit formulas for the distribution of $ \overline{X}\; ( u) $.

For references see Queueing theory.

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