Queue, multi-channel with waiting

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.