The Gated-Service M/GI/1 Queue with Single Vacations

and Its Application to Batch-Service Queues · 2026

Read The Gated-Service M/GI/1 Queue with Single Vacations by and Its Application to Batch-Service Queues (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-10891.txt.

Introduction

Takine analyzes a single-server queue with single vacations under gated service. Under gated service, only customers present when service starts are served in that visit. He derives the generating function of the steady queue length. He also derives the transform of the steady system delay and the joint transform for busy-cycle length and served count in it. As an application, he treats a batch-service queue where service times depend on batch size.

Catalog record

CREATORand Its Application to Batch-Service Queues
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43837
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.10891

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Gated-Service M/GI/1 Queue with Single Vacations and Its Application to Batch-Service Queues Abstract Abstract In this paper, we consider the M/GI/1 queue with single vacations under the gated service discipline. We obtain the probability generating function of the stationary queue length, the Laplace-Stieltjes transform of the system delay distribution in steady state, and the joint transform of the busy cycle length and the number of customers served in the busy cycle. Furthermore, as an application, we consider a batch-service M/G/1 queue, where service times depend on the number of customers in batch. Keywords M/GI/1 queue, gated service, single vacations, batch-service, branching process, limiting distribution, final value theorem Mathematics Subject Classification 60K25, 60J80 1 Introduction We consider the M/G/1 queue with single vacations under the gated service discipline. Customers arrive according to a Poisson process with rate \lambda . Service times of customers are independent and identically distributed (i.i.d.) according to a general distribution H(x) ( x\geq 0 ). We assume \rho=\lambda\mathrm{E}[H]<1 , where H denotes a generic random variable for service times. Let h^{*}(s)=\mathrm{E}[\exp(-sH)] ( s>0 ). The server serves customers according to the gated service discipline with single vacations. (i) When the system is empty and the server is idle, the server waits for the next arrival and starts the service as soon as the next customer arrives. After the service completion, the server takes a vacation. (ii-a) If there are k ( k=1,2,\ldots ) waiting customers on return from a vacation, the server serves those k customers successively and takes another vacation. (ii-b) If the system is empty on return from a vacation, the server becomes idle. We assume that vacation lengths are i.i.d. according to a general distribution V(x) ( x\geq 0 ) and \mathrm{E}[V]<\infty , where V denotes a generic random variable for vacation lengths. Let v^{*}(s)=\mathrm{E}[\exp(-sV)] ( s>0 ). M/GI/1 queues with gated vacations have been studied in the literature, e.g., [ 6 ] and references therein. Most of them, however, consider so-called multiple-vacation queues, where if the server finds the empty system on return from a vacation, the server takes another vacation immediately, and to the best of our knowledge, the above-mentioned single-vacation model has not been considered. In [ 5 ] and [ 7 ] , the following model is called the gated-service M/G/1 queue with single vacations: The server becomes idle after taking a vacation if no customers arrive during the vacation, regardless of whether waiting customers (who arrived during services of other customers) exist or not, and the server starts to serve customers when the next arrival occurs. In what follows, we first consider the queue length and system delay distributions in steady state. We then consider the joint distribution of the length of a busy cycle and the number of customers served in the busy cycle. Finally, we provide some remarks on the MAP/GI/1 queue with gated vacations. For convenience, let \{H_{i}\}_{i=1,2,\ldots} (resp. \{V_{i}\}_{i=1,2,\ldots} ) denote a sequence of i.i.d. random variables whose distribution function is given by H(x) (resp. V(x) ). 2 Queue length and system delay distributions Let N_{\lambda}(x) ( x\geq 0 ) denote the number of Poisson arrivals with rate \lambda during an interval of length x . We then define the probability generating functions (PGF) a_{H}^{*}(z) and a_{V}^{*}(z) as a_{H}^{*}(z)=\mathrm{E}[z^{N_{\lambda}(H)}]=h^{*}(\lambda-\lambda z),\qquad a_{V}^{*}(z)=\mathrm{E}[z^{N_{\lambda}(V)}]=v^{*}(\lambda-\lambda z). Let L_{\rm B} and L_{\rm E} denote the number of customers at the beginning of a vacation and at the end of a vacation in steady state. We define \ell_{\rm B}^{*}(z) and \ell_{\rm E}^{*}(z) as PGF’s of L_{\rm B} and L_{\rm E} . \ell_{\rm B}^{*}(z)=\mathrm{E}[z^{L_{\rm B}}],\qquad\ell_{\rm E}^{*}(z)=\mathrm{E}[z^{L_{\rm E}}]. By definition, we have \ell_{\rm E}^{*}(z)=\ell_{\rm B}^{*}(z)a_{V}^{*}(z),\qquad\ell_{\rm B}^{*}(z)=\ell_{\rm E}^{*}(a_{H}^{*}(z))-\ell_{\rm E}^{*}(0)+\ell_{\rm E}^{*}(0)a_{H}^{*}(z). (1) Let L denote the stationary queue length. It is clear that the model is a special case of the M/GI/1 queue with generalized vacations [ 2 ] , so that the stochastic decomposition holds. L=L_{\rm M/G/1}+L_{\rm V}, (2) where L_{\rm M/G/1} denote the stationary queue length in the ordinary M/GI/1 queue characterized by the arrival rate \lambda and the service time distribution H(x) and L_{\rm V} denote the conditional queue length in steady state, given that the server does not serve customers. Note that L_{\rm M/G/1} and L_{\rm V} are independent. Because \Pr(\mbox{the server is idle}\mid\mbox{the server is not serving customers})=\frac{\ell_{\rm E}^{*}(0)\times 1/\lambda}{\mathrm{E}[V]+\ell_{\rm E}^{*}(0)\times 1/\lambda}, we have L_{\rm V}=\begin{cases}0,&\mbox{with probability }\displaystyle\frac{\ell_{\rm E}^{*}(0)}{\lambda\mathrm{E}[V]+\ell_{\rm E}^{*}(0)},\\[11.38109pt] L_{\rm B}+N_{\lambda}(\hat{V}),&\mbox{with probability }\displaystyle\frac{\lambda\mathrm{E}[V]}{\lambda\mathrm{E}[V]+\ell_{\rm E}^{*}(0)},\end{cases} (3) where \hat{V} denotes the equilibrium random variable of V , which is independent of L_{\rm B} . We define \ell^{*}(z) as the PGF of the stationary queue length L . \ell^{*}(z)=\mathrm{E}[z^{L}],\quad|z|<1. It then follows from ( 2 ) and ( 3 ) that \ell^{*}(z)=\ell_{\rm M/G/1}^{*}(z)\bigg[\frac{\ell_{\rm E}^{*}(0)}{\lambda\mathrm{E}[V]+\ell_{\rm E}^{*}(0)}+\frac{\lambda\mathrm{E}[V]}{\lambda\mathrm{E}[V]+\ell_{\rm E}^{*}(0)}\ell_{\rm B}^{*}(z)\frac{1-a_{V}^{*}(z)}{\lambda\mathrm{E}[V](1-z)}\bigg],\quad|z|<1, (4) where \ell_{\rm M/G/1}^{*}(z) denotes the PGF of the stationary queue length in the ordinary M/GI/1 queue. \ell_{\rm M/G/1}^{*}(z)=\frac{(1-\rho)(z-1)a_{H}^{*}(z)}{z-a_{H}^{*}(z)},\quad|z|<1. (5) We observe from ( 1 ) and ( 4 ) that if \ell_{\rm E}^{*}(z) is obtained, \ell^{*}(z) is determined completely. In what follows, we derive \ell_{\rm E}^{*}(z) . Let Q_{n} ( n=0,1,\ldots ) denote the number of customers at the end of the n th vacation. It is clear that \{Q_{n}\} forms a discrete-time Markov chain on \mathbbm{Z}^{+}=\{0,1,\ldots\} . Because \displaystyle\Pr(Q_{n+1}=j\mid Q_{n}=0) \displaystyle>\Pr(N_{\lambda}(H)=0)\Pr(N_{\lambda}(V)=j)>0, \displaystyle\Pr(Q_{n+1}=j\mid Q_{n}=i) \displaystyle>\Pr(N_{\lambda}(H_{1}+H_{2}+\cdots+H_{i})=0)\Pr(N_{\lambda}(V)=j)>0,\quad i=1,2,\ldots, for all j\in\mathbbm{Z}^{+} , the Markov chain \{Q_{n}\} is irreducible and aperiodic. Furthermore, because \rho<1 , \mathrm{E}[V]<\infty , and for j=1,2,\ldots , \mathrm{E}[Q_{n+1}\mid Q_{n}=j]<j\ \Leftrightarrow\ \lambda\big(j\mathrm{E}[H]+\mathrm{E}[V]\big)<j\ \Leftrightarrow\ j>\frac{\lambda\mathrm{E}[V]}{1-\rho}, there exists j^{*} such that \mathrm{E}[Q_{n+1}\mid Q_{n}=j]<j for all j\geq j^{*} , so that \{Q_{n}\} is positive recurrent. Therefore, if \rho<1 and \mathrm{E}[V]<\infty , the limiting distribution of \{Q_{n}\} exists, i.e., \lim_{n\to\infty}\Pr(Q_{n}=k)=\Pr(L_{\rm E}=k),\quad k=0,1,\ldots. (6) Note that the limiting distribution is independent of the initial state Q_{0} . We define q_{n}^{*}(z) ( n=0,1,\ldots ) as the PGF of Q_{n} . q_{n}^{*}(z)=\mathrm{E}[z^{Q_{n}}],\quad n=0,1,\ldots. Theorem 1 . The PGF q_{n}^{*}(z) ( n=1,2,\ldots ) satisfies q_{n}^{*}(z)=q_{0}^{*}(\psi_{n}^{H}(z))\prod_{k=1}^{n}\psi_{k}^{V}(z)-\sum_{j=1}^{n}q_{n-j}^{*}(0)\big(1-\psi_{j}^{H}(z)\big)\prod_{k=1}^{j}\psi_{k}^{V}(z),\quad n=1,2,\ldots, (7) where \psi_{n}^{H}(z) and \psi_{n}^{V}(z) ( n=1,2,\ldots ) are defined recursively as \displaystyle\psi_{1}^{H}(z) \displaystyle=a_{H}^{*}(z),\qquad\psi_{n}^{H}(z)=a_{H}^{*}\big(\psi_{n-1}^{H}(z)\big)=\psi_{n-1}^{H}\big(a_{H}^{*}(z)\big),\quad n=2,3,\ldots, (8) \displaystyle\psi_{1}^{V}(z) \displaystyle=a_{V}^{*}(z),\qquad\psi_{n}^{V}(z)=a_{V}^{*}\big(\psi_{n-1}^{H}(z)\big),\quad n=2,3,\ldots. (9) Remark 2 . If we model customers served in a busy period of the ordinary M/G/1 queue by a Galton-Watson branching process [ 1 ] , \psi_{n}^{H}(z) denote the number of customers in the n th generation. Similarly, \psi_{n}^{V}(z) can be related to the number of customers in the n th generation in a delayed busy period, where the service time of the first customer follows the distribution V(x) . Proof. We prove Theorem 1 by induction. By definition, we have q_{1}^{*}(z)=\big(q_{0}^{*}(a_{H}^{*}(z))-q_{0}^{*}(0)+q_{0}^{*}(0)a_{H}^{*}(z)\big)a_{V}^{*}(z)=q_{0}^{*}(\psi_{1}^{H}(z))\psi_{1}^{V}(z)-q_{0}^{*}(0)\big(1-\psi_{1}^{H}(z)\big)\psi_{1}^{V}(z), so that Theorem 1 holds for n=1 . Suppose Theorem 1 holds for some n ( n=1,2,\ldots ). It then follows that \displaystyle q_{n+1}^{*}(z) \displaystyle=\big(q_{n}^{*}(a_{H}^{*}(z))-q_{n}^{*}(0)+q_{n}^{*}(0)a_{H}^{*}(z)\big)a_{V}^{*}(z) (10) \displaystyle=\bigg[q_{0}^{*}(\psi_{n}^{H}(a_{H}^{*}(z)))\prod_{k=1}^{n}\psi_{k}^{V}(a_{H}^{*}(z))-\sum_{j=1}^{n}q_{n-j}^{*}(0)\big(1-\psi_{j}^{H}(a_{H}^{*}(z))\big)\prod_{k=1}^{j}\psi_{k}^{V}(a_{H}^{*}(z))\bigg]a_{V}^{*}(z) \displaystyle\qquad{}-q_{n}^{*}(0)\big(1-a_{H}^{*}(z)\big)a_{V}^{*}(z) \displaystyle=q_{0}^{*}(\psi_{n+1}^{H}(z))\bigg(\prod_{k=1}^{n}\psi_{k+1}^{V}(z)\bigg))\psi_{1}^{V}(z)-\sum_{j=1}^{n}q_{n-j}^{*}(0)\big(1-\psi_{j+1}^{H}(z)\big)\bigg(\prod_{k=1}^{j}\psi_{k+1}^{V}(z)\bigg)\psi_{1}^{V}(z) \displaystyle\qquad{}-q_{n}^{*}(0)\big(1-\psi_{1}^{H}(z)\big)\psi_{1}^{V}(z) \displaystyle=q_{0}^{*}(\psi_{n+1}^{H}(z))\prod_{k=1}^{n+1}\psi_{k+1}^{V}(z)-\sum_{j=2}^{n+1}q_{n+1-j}^{*}(0)\big(1-\psi_{j}^{H}(z)\big)\prod_{k=1}^{j}\psi_{k}^{V}(z)-q_{n}^{*}(0)\big(1-\psi_{1}^{H}(z)\big)\psi_{1}^{V}(z), which shows that Theorem 1 holds for n+1 . ∎ It follows from ( 6 ) that \lim_{n\to\infty}q_{n}^{*}(z)=\ell_{E}^{*}(z),\quad|z|<1. (11) To obtain \ell_{E}^{*}(z) , we use the the final value theorem of the Z -transform. Lemma 3 (Final value theorem of the Z -transform) . If \{a_{n}\}_{n=1,2,\ldots} has a finite limit a^{*} , then a^{*}=\lim_{n\to\infty}a_{n}=\lim_{\omega\to 1-}(1-\omega)\sum_{n=1}^{\infty}a_{n}\omega^{n} For completeness, we provide the proof of Lemma 3 in Appendix A . Theorem 4 . If \rho=\lambda\mathrm{E}[H]<1 and \mathrm{E}[V]<\infty , \ell_{E}^{*}(z) is given by \ell_{E}^{*}(z)=\prod_{k=1}^{\infty}\psi_{k}^{V}(z)-\ell_{E}^{*}(0)\sum_{n=1}^{\infty}\big(1-\psi_{n}^{H}(z)\big)\prod_{k=1}^{n}\psi_{k}^{V}(z), (12) where \ell_{E}^{*}(0)=\displaystyle\frac{\displaystyle\prod_{k=1}^{\infty}\psi_{k}^{V}(0)}{1+\displaystyle\sum_{n=1}^{\infty}\big(1-\psi_{n}^{H}(0)\big)\displaystyle\prod_{k=1}^{n}\psi_{k}^{V}(0)}. (13) Proof. We apply Lemma 3 to ( 7 ). Specifically, multiplying both sides of ( 7 )

Read the complete text