# On the Discrete-TimeGeoX/G/1 Queues under N-Policy with Single and Multiple Vacations

Authors: Sung J. Kim; Nam K. Kim; Hyun-Min Park; Kyung Chul Chae; Dae-Eun Lim
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We consider the discrete-timeGeoX/G/1 queue under N-policy with single and multiple vacations. In this queueing system, the server takes multiple vacations and a single vacation whenever the system becomes empty and begins to serve customers only if the queue length is at least a predetermined threshold value N. Using the well-known property of stochastic decomposition, we derive the stationary queue-length distributions for both vacation models in a simple and unified manner. In addition, we derive their busy as well as idle-period distributions. Some classical vacation models are considered as special cases.


---

## Body

## 1. Introduction

Queueing systems with vacations have been studied by many researchers over the past four decades. A vacation is the period in which a server is not available for some reason: the server may break down, take time to warm up/close down/repair, or be serving other classes of customers and so forth. Such queuing systems are useful in modeling a variety of real-life queueing situations such as those in digital communications, computer networks, and production/inventory systems. Readers are referred to Doshi [1] and Takagi [2, 3] for excellent and extensive treatments of various types of queueing systems with vacations.In recent years, there has been a growing interest in the analysis of discrete-time queueing systems due to their applications in a variety of slotted digital communication systems and other related areas. Takagi [3] presents an extensive study on discrete-time queueing systems with vacations such as those with multiple vacations, single vacation, N-policy, and set-up times. Zhang and Tian [4] study the discrete-time Geo/G/1 queue with multiple adaptive vacations, which includes multiple-vacation and single-vacation models as its special cases. Fiems and Bruneel [5] consider the discrete-time GI/G/1 queue with timed vacations. Alfa [6] discusses a variety of vacation models with discrete-time Markovian arrival process.In this paper, we consider a discrete-time queueing system with batch arrivals,N-policy, and single and multiple vacations. In this queueing system, groups of customers arrive according to a Bernoulli process, and they are served by the single server. The server takes single and multiple vacations whenever the system becomes empty and restarts to serve the customers only if the number of the customers in the system is at least a predetermined threshold value N. We refer to this system as the GeoX/G/1 queue under N-policy with single and multiple vacations. The continuous-time counterpart of this queue, that is, the MX/G/1 queue under N-policy with single and multiple vacations, has been discussed by Lee et al. [7] and Lee et al. [8], respectively. As special cases, the GeoX/G/1 queues with multiple vacations, single vacation, and N-policy are also considered. Until recently, numerous studies have been reported regarding variations of queueing systems with N-policy and vacations including Markovian queues (Choudhury [9], Ke et al. [10], and Wang [11]), general input queues (Lim et al. [12]), and combination with other control policies (Ke et al. [13] and Feyaerts et al. [14]). Also, reported works are well summarized by Tian and Zhang [15]. Nonetheless, results included in this paper have not been introduced previously and the approach to solve complex queueing problem is novel and quite simple.It is well known that discrete-time queueing systems have been extensively applied in computer and digital communication systems. Also, control policies includingN-policy and two types of vacation considered in this paper have wide applicability to all sorts of different real life problems. Consider vulnerability of software system that is potentially dangerous since it might be exploited to cause loss or harm [16]. Single or multiple vulnerabilities of software systems are reported and stored in vulnerability databases daily. For example, vulnerabilities are collected in the NVD (national vulnerability database) of the NIST (National Institute of Standards and Technology) in the United States. Then, discovery and removal of reported vulnerabilities can be modelled using the discrete time batch arrival queueing system [16]. A day corresponds to a slot, and N-policy can be applied to operate system more efficiently. Other applications of queueing systems with vacations can be found in Tian and Zhang [15].This paper is organized as follows. In Section2, we describe the models in detail. We first study the queue with N-policy and multiple vacations in Section 3. Next, we consider the queue with N-policy and single vacation in Section 4. Finally, we conclude the paper in Section 5.


## 2. Model Description

In discrete-time queueing models, the time axis is segmented into a sequence of equal intervals of unit duration, called slots. It is always assumed that interarrival, service, and vacation times are integer multiples of unit duration. Because nothing is assumed to happen at any time during a slot, the state of the system changes only at a slot boundaryn=0,1,2,…. Under this discrete-time setting, note that an arrival and a departure may take place simultaneously at a slot boundary. Regarding the order of these simultaneous events, there have been two typical assumptions: arrivals first (AF) and departures first (DF). Specifically, under AF (DF), such an arrival (a departure) occurs just before a departure (an arrival). We also assume that, under AF (DF), a service and a vacation end before an arrival (a departure) and begin after a departure (an arrival). By all these assumptions, all the events that may occur simultaneously at a slot boundary are in order. For more details on the discrete-time queueing models, see Hunter [17], Takagi [3], and Bruneel and Kim [18]. Until addressing DF at the end, we assume AF.We consider two discrete-time queueing systems: the discrete-timeGeoX/G/1 queue under N-policy with single and multiple vacations. In the GeoX/G/1 queue with N-policy and multiple vacations, the server takes a vacation as soon as the system becomes empty. If the number of waiting customers is less than N when the server returns from the vacation, he takes another vacation. He keeps taking vacations until he finds at least N customers on return from a vacation. Finally, the server finding at least N customers starts to serve those customers. In the GeoX/G/1 queue with N-policy and single vacation, on the other hand, if the number of waiting customers is less than N after the server’s first vacation, the server becomes idle and just waits for the number to rise to be at least N. Such a waiting period is called a dormant period; as soon as the number reaches N (or more), he starts to serve the customers.LetA denote a generic random variable (r.v.) representing the number of customers that arrive during a single slot. It is assumed that numbers of such arrivals are independent and identically distributed (i.i.d.) with their common distribution and PGF (probability generating function) given by
(1)ak≜Pr[A=k],k=0,1,2,…,A(z)≜∑k=0∞akzk.
Note that this arrival process is considered as a batch Bernoulli process, where the interarrival times between batches are independent and geometrically distributed with parameter 1-a0, and the batch-size PMF (probability mass function) is ak/(1-a0), k=1,2,3,…. Service times of customers (denoted by a generic r.v. S) are independent of the arrival process and they are i.i.d. with their common PMF and PGF given by
(2)sk≜Pr[S=k],k=1,2,…,S(z)≜∑k=1∞skzk.
Lengths of vacations (denoted by a generic r.v. V) are independent of the arrival and service processes and they are i.i.d. with their common PMF and PGF given by
(3)vk≜Pr[V=k],k=1,2,…,V(z)≜∑k=1∞vkzk.


## 3. The Geox/G/1 Queue with N-Policy and Multiple Vacations

For this system, we derive PGFs of the stationary queue length, idle period, and busy period.


### 3.1. The Queue-Length Distribution

To obtain the queue-length PGF, we make use of the well-known property of stochastic decomposition [3, p. 90] and [17]: for a class of GeoX/G/1 queueing systems with server vacations, PGF P(z) of the queue length (i.e., the number of customers in system including the one, if any, being served) during an arbitrary slot is given by
(4)P(z)=PGeoX/G/1(z)·QN-(z),
where PGeoX/G/1(z)={(1-ρ)(1-z)S[A(z)]}/{S[A(z)]-z} is the corresponding PGF of the standard GeoX/G/1 queue without vacations [3, p. 21] and QN-(z) is the PGF of the number of customers that arrive during elapsed slots of an idle period. Note that QN-(z) is given by
(5)QN-(z)=1-QN(z)E[QN](1-z)÷1-A(z)E[A](1-z),
where QN with its PGF QN(z) is a r.v. of the number of customers that arrive during an idle period. Note that {1-QN(z)}/{E[QN](1-z)} and {1-A(z)}/{E[A](1-z)} are PGFs of the (discrete-time version of the) equilibrium distributions of QN and A, respectively.Letαi be the probability that i customers (i=0,1,2,…) arrive during a vacation with its PGF α(z)=V[A(z)], and let βi be the probability that a grand vacation process visits state i (i=0,1,2,…,N-1). By a grand vacation, we mean a series of vacations that ends with a vacation in which at least one customer arrives (see Lee et al. [8]). For the continuous-time MX/G/1 queue with N-policy and multiple vacations, Lee et al.[8] show that βi is given by
(6)β0=1,βi=∑k=1i{αk(1-α0)}βi-k,i=1,2,…,N-1.
Moreover, they show that QN(z) is fully characterized by αi and βi as follows:
(7)QN(z)=1+α(z)-11-α0∑j=0N-1βjzj,E[QN]=dQN(z)dz|z=1=E[A]E[V]1-α0∑j=0N-1βj.
Note that (E[A]E[V])/(1-α0) is interpreted as the expected number of customers that arrive during a grand vacation (see Wald’s equation [19, p. 98]) and ∑j=0N-1βj as the expected number of a grand vacation during an idle period. In derivations of (6) and (7), we notice that it is irrelevant whether the model is continuous or discrete; that is, (6) and (7) hold for their discrete-time counterparts as well.Now, substituting (7) into (5) and (4), we have the following theorem.Theorem 1.
For the discrete-timeGeoX/G/1 queue with N-policy and multiple vacations, the PGF of the stationary queue length and its mean L are given by
(8)P(z)=PGeoX/G/1(z)·1-α(z)E(V)[1-A(z)]·∑j=0N-1βjzj∑j=0N-1βj=PGeoX/G/1/MV(z)·∑j=0N-1βjzj∑j=0N-1βj,L=LGeoX/G/1/MV+∑j=0N-1jβj∑j=0N-1βj,
where PGeoX/G/1/MV(z) and LGeoX/G/1/MV are the corresponding PGF and mean of the GeoX/G/1 queue with multiple vacations.Remark 2.
The continuous-time counterpart of Theorem1 is derived by Lee et al. [8] using the supplementary variable technique.Remark 3.
Theorem1 is readily specialized for the corresponding results of the GeoX/G/1 queue with multiple vacations and the same queue with N-policy. By letting N be 1, the corresponding results for the GeoX/G/1 queue with multiple vacations [3, p. 98] are obtained. By letting V be a single slot (so thus α(z)=A(z)), on the other hand, the corresponding results for the GeoX/G/1 queue with N-policy [3, p. 174] are also obtained (under the discrete-time setting, note that taking a vacation whose length is a single slot is equivalent to taking no vacations).


### 3.2. The Cycle Time

In this section, we first consider the idle period and then the busy period. LetIN and IN(z) denote the number of slots of an idle period and its PGF. Then we have the following theorem.Theorem 4.
For the discrete-timeGeoX/G/1 queue with N-policy and multiple vacations, the PGF of an idle period and its mean E[IN] are given by
(9)IN(z)=11-V(a0z)×{+∑k=1N-1[[IN-k(z)-1]·[∑j=1∞zjak(j)vj]]V(z)-V(a0z)+∑k=1N-1[[IN-k(z)-1]·[∑j=1∞zjak(j)vj]]},(10)E[IN]=dIN(z)dz|z=1=E[V]1-α0∑j=0N-1βj.Proof.
Conditioning on the length of the first vacation and the number of arrivals during this vacation (denoted by#(V)), we have the following recursive equation:
(11)IN(z∣V=j,#(V)=k)={zj·IN-k(z)k<Nzjk≥N.
Then, unconditioning (11) on #(V), we have
(12)IN(z∣V=j)=∑k=0∞IN(z∣V=j,#(V)=k)·Pr(#(V)=k∣V=j)=zj[1+∑k=0N-1ak(j){IN-k(z)-1}],
where ak(j) is the probability that k customers arrive during j slots with its PGF given by [a(z)]j=∑k=0∞ak(j)zk. Next, unconditioning (12) on V, we have the desired result (9):
(13)IN(z)=∑j=1∞IN(z∣V=j)·vj=11-V(a0z)×{+∑k=1N-1[[IN-k(z)-1]·[∑j=1∞zjak(j)vj]]V(z)-V(a0z)+∑k=1N-1[[IN-k(z)-1]·[∑j=1∞zjak(j)vj]]}.
From (9), we have
(14)E[IN]=dIN(z)dz|z=1=E[V]1-α0+∑k=1N-1αk1-α0E[IN-k].
Using (6), it can be shown that (10) is a solution to the recursive equation (14). This completes the proof.Note thatE[V]/(1-α0) is interpreted as the expected length of a grand vacation.Next, we consider the busy period. LetBN and BN(z) denote the number of slots of a busy period and its PGF. Note that PGF for a busy period that begins with k customers in the queueing system is given by [Θ(z)]k [3, p. 40], where Θ(z) represents PGF of the length of a busy period that begins with one customer in the standard GeoX/G/1 queue without vacation. Thus we have the following.Theorem 5.
For the discrete-timeGeoX/G/1 queue with N-policy and multiple vacations, the PGF of a busy period and its mean E[BN] are given by
(15)BN(z)=QN[Θ(z)],E[BN]=dBN(z)dz|z=1=ρE[V]∑j=0N-1βj(1-ρ)(1-α0)=ρ1-ρE[IN].Remark 6.
Along the same lines as presented above, the continuous-time counterparts of Theorems4 and 5 have been derived by Lee et al. [8]. Theorems 4 and 5 are readily specialized for the corresponding results of the GeoX/G/1 queue with multiple vacations [3, p. 94-95] and the same queue with N-policy [3, p. 175].


## 3.1. The Queue-Length Distribution

To obtain the queue-length PGF, we make use of the well-known property of stochastic decomposition [3, p. 90] and [17]: for a class of GeoX/G/1 queueing systems with server vacations, PGF P(z) of the queue length (i.e., the number of customers in system including the one, if any, being served) during an arbitrary slot is given by
(4)P(z)=PGeoX/G/1(z)·QN-(z),
where PGeoX/G/1(z)={(1-ρ)(1-z)S[A(z)]}/{S[A(z)]-z} is the corresponding PGF of the standard GeoX/G/1 queue without vacations [3, p. 21] and QN-(z) is the PGF of the number of customers that arrive during elapsed slots of an idle period. Note that QN-(z) is given by
(5)QN-(z)=1-QN(z)E[QN](1-z)÷1-A(z)E[A](1-z),
where QN with its PGF QN(z) is a r.v. of the number of customers that arrive during an idle period. Note that {1-QN(z)}/{E[QN](1-z)} and {1-A(z)}/{E[A](1-z)} are PGFs of the (discrete-time version of the) equilibrium distributions of QN and A, respectively.Letαi be the probability that i customers (i=0,1,2,…) arrive during a vacation with its PGF α(z)=V[A(z)], and let βi be the probability that a grand vacation process visits state i (i=0,1,2,…,N-1). By a grand vacation, we mean a series of vacations that ends with a vacation in which at least one customer arrives (see Lee et al. [8]). For the continuous-time MX/G/1 queue with N-policy and multiple vacations, Lee et al.[8] show that βi is given by
(6)β0=1,βi=∑k=1i{αk(1-α0)}βi-k,i=1,2,…,N-1.
Moreover, they show that QN(z) is fully characterized by αi and βi as follows:
(7)QN(z)=1+α(z)-11-α0∑j=0N-1βjzj,E[QN]=dQN(z)dz|z=1=E[A]E[V]1-α0∑j=0N-1βj.
Note that (E[A]E[V])/(1-α0) is interpreted as the expected number of customers that arrive during a grand vacation (see Wald’s equation [19, p. 98]) and ∑j=0N-1βj as the expected number of a grand vacation during an idle period. In derivations of (6) and (7), we notice that it is irrelevant whether the model is continuous or discrete; that is, (6) and (7) hold for their discrete-time counterparts as well.Now, substituting (7) into (5) and (4), we have the following theorem.Theorem 1.
For the discrete-timeGeoX/G/1 queue with N-policy and multiple vacations, the PGF of the stationary queue length and its mean L are given by
(8)P(z)=PGeoX/G/1(z)·1-α(z)E(V)[1-A(z)]·∑j=0N-1βjzj∑j=0N-1βj=PGeoX/G/1/MV(z)·∑j=0N-1βjzj∑j=0N-1βj,L=LGeoX/G/1/MV+∑j=0N-1jβj∑j=0N-1βj,
where PGeoX/G/1/MV(z) and LGeoX/G/1/MV are the corresponding PGF and mean of the GeoX/G/1 queue with multiple vacations.Remark 2.
The continuous-time counterpart of Theorem1 is derived by Lee et al. [8] using the supplementary variable technique.Remark 3.
Theorem1 is readily specialized for the corresponding results of the GeoX/G/1 queue with multiple vacations and the same queue with N-policy. By letting N be 1, the corresponding results for the GeoX/G/1 queue with multiple vacations [3, p. 98] are obtained. By letting V be a single slot (so thus α(z)=A(z)), on the other hand, the corresponding results for the GeoX/G/1 queue with N-policy [3, p. 174] are also obtained (under the discrete-time setting, note that taking a vacation whose length is a single slot is equivalent to taking no vacations).


## 3.2. The Cycle Time

In this section, we first consider the idle period and then the busy period. LetIN and IN(z) denote the number of slots of an idle period and its PGF. Then we have the following theorem.Theorem 4.
For the discrete-timeGeoX/G/1 queue with N-policy and multiple vacations, the PGF of an idle period and its mean E[IN] are given by
(9)IN(z)=11-V(a0z)×{+∑k=1N-1[[IN-k(z)-1]·[∑j=1∞zjak(j)vj]]V(z)-V(a0z)+∑k=1N-1[[IN-k(z)-1]·[∑j=1∞zjak(j)vj]]},(10)E[IN]=dIN(z)dz|z=1=E[V]1-α0∑j=0N-1βj.Proof.
Conditioning on the length of the first vacation and the number of arrivals during this vacation (denoted by#(V)), we have the following recursive equation:
(11)IN(z∣V=j,#(V)=k)={zj·IN-k(z)k<Nzjk≥N.
Then, unconditioning (11) on #(V), we have
(12)IN(z∣V=j)=∑k=0∞IN(z∣V=j,#(V)=k)·Pr(#(V)=k∣V=j)=zj[1+∑k=0N-1ak(j){IN-k(z)-1}],
where ak(j) is the probability that k customers arrive during j slots with its PGF given by [a(z)]j=∑k=0∞ak(j)zk. Next, unconditioning (12) on V, we have the desired result (9):
(13)IN(z)=∑j=1∞IN(z∣V=j)·vj=11-V(a0z)×{+∑k=1N-1[[IN-k(z)-1]·[∑j=1∞zjak(j)vj]]V(z)-V(a0z)+∑k=1N-1[[IN-k(z)-1]·[∑j=1∞zjak(j)vj]]}.
From (9), we have
(14)E[IN]=dIN(z)dz|z=1=E[V]1-α0+∑k=1N-1αk1-α0E[IN-k].
Using (6), it can be shown that (10) is a solution to the recursive equation (14). This completes the proof.Note thatE[V]/(1-α0) is interpreted as the expected length of a grand vacation.Next, we consider the busy period. LetBN and BN(z) denote the number of slots of a busy period and its PGF. Note that PGF for a busy period that begins with k customers in the queueing system is given by [Θ(z)]k [3, p. 40], where Θ(z) represents PGF of the length of a busy period that begins with one customer in the standard GeoX/G/1 queue without vacation. Thus we have the following.Theorem 5.
For the discrete-timeGeoX/G/1 queue with N-policy and multiple vacations, the PGF of a busy period and its mean E[BN] are given by
(15)BN(z)=QN[Θ(z)],E[BN]=dBN(z)dz|z=1=ρE[V]∑j=0N-1βj(1-ρ)(1-α0)=ρ1-ρE[IN].Remark 6.
Along the same lines as presented above, the continuous-time counterparts of Theorems4 and 5 have been derived by Lee et al. [8]. Theorems 4 and 5 are readily specialized for the corresponding results of the GeoX/G/1 queue with multiple vacations [3, p. 94-95] and the same queue with N-policy [3, p. 175].


## 4. The GeoX/G/1 Queue with N-Policy and Single Vacation

### 4.1. The Queue-Length Distribution

For this system, we also make use of the well-known property of stochastic decomposition [3, p. 90] and [20] to derive the queue-length distribution. First, we consider an individual cycle by which we mean an idle period plus the following busy period. In a given cycle, we note that a dormant period exists with probability ∑k=0N-1αk. Then we let ri be the probability that the system visits state i (i=0,1,2,…,N-1) during such a dormant period. And πi be the probability that the system visits state i (i=0,1,2,…,N-1) during an idle period in the GeoX/G/1 under N-policy without vacations. For the continuous-time MX/G/1 queue with N-policy and single vacation, Lee et al. [7] show that ri is given by
(16)ri=∑k=0iαkπi-k,i=1,2,…,N-1,r0=α0,r(z)≜∑k=0N-1rkzk.
In this derivation, we notice that it is irrelevant whether the model is continuous or discrete; that is, (16) holds for its discrete-time counterpart as well.Following the procedure presented by Lee et al. [7], we obtain that QN(z) is fully characterized by αi, ai, and ri as follows:
(17)QN(z)=α(z)+A(z)-11-a0∑j=0N-1rjzj,(18)E[QN]=dQN(z)dz|z=1=E[A]E[V]+E[A]1-a0∑j=0N-1rj.
Note that ∑j=0N-1rj is interpreted as the mean number of batch arrivals during a dormant period and E[A]/(1-a0) as the mean batch size.Now, simply substituting (17) into (5) and (4), we have the following.Theorem 7.
For the discrete-timeGeoX/G/1 queue with N-policy and single vacation, the PGF of the stationary queue length and its mean L are given by
(19)P(z)=PGeoX/G/1(z)·1(1-a0)E[V]+∑j=0N-1rj·{(1-a0)[1-α(z)]1-A(z)+r(z)},L=LGeoX/G/1+1(1-a0)E[V]+∑j=0N-1rj·{E[A](1-a0)2E[V2-V]+∑j=0N-1jrj}.Remark 8.
The continuous-time counterpart of Theorem7 was derived by Lee et al. [7] using the supplementary variable technique.Remark 9.
Theorem7 is readily specialized for the corresponding results of the GeoX/G/1 queue with single vacation and the same queue with N-policy. By letting N be 1, the corresponding results for the GeoX/G/1 queue with single vacation [3, p. 132] are obtained. By letting V be a single slot, the corresponding results for the GeoX/G/1 queue with N-policy [3, p. 174] are also obtained.


### 4.2. The Cycle Time

In this section, we first consider the idle period and then the busy period. LetIN and IN(z) denote the number of slots of an idle period and its PGF. Then we have the following.Theorem 10.
For the discrete-timeGeoX/G/1 queue with N-policy and single vacation, the PGF of an idle period and its mean E[IN] are given by
(20)IN(z)=V(z)+∑k=0N-1[[IN-k0(z)-1]·[∑j=1∞zjak(j)vj]],(21)E[IN]=E[V]+11-a0∑j=0N-1rj.Proof.
Conditioning on the length of the first vacation and the number of customers that arrive during this vacation (denoted by#(V)), we have the following recursive equation:
(22)IN(z∣V=j,#(V)=k)={zj·IN-k0(z)k<Nzjk≥N,
where IN0(z) denotes the PGF for an idle period in GeoX/G/1 under N-policy without vacations. Then, unconditioning (22) on #(V), we have
(23)IN(z∣V=j)=∑k=0∞IN(z∣V=j,#(V)=k),·Pr(#(V)=k∣V=j)=zj[1+∑k=0N-1ak(j){IN-k0(z)-1}],
where ak(j) is the probability that k customers arrive during j slots with its PGF given by [a(z)]j=∑k=0∞ak(j)zk. Next, unconditioning (23) on V, we have the desired result (20):
(24)IN(z)=∑j=1∞IN(z∣V=j)·vj=V(z)+∑k=0N-1[[IN-k0(z)-1]·[∑j=1∞zjak(j)vj]].
From (18), we have
(25)E[IN]=E[QN]E[A]=E[V]+11-a0∑j=0N-1rj.Note that∑j=0N-1rj/(1-a0) is interpreted as the mean length of a dormant period, where 1/(1-a0) represents the mean interbatch time.Next, we consider the busy period. LetBN and BN(z) denote the number of slots of a busy period and its PGF. Following the same procedure as presented in Section 3, we have the following.Theorem 11.
For the discrete-timeGeoX/G/1 queue with N-policy and single vacation, the PGF of a busy period and its mean E[BN] are given by
(26)BN(z)=QN[Θ(z)],E[BN]=dBN(z)dz|z=1=ρ1-ρ{E[V]+11-a0∑j=0N-1rj}=ρ1-ρE[IN].Remark 12.
Along the same lines as presented above, the continuous-time counterparts of Theorems10 and 11 have been derived by Lee et al. [7]. Theorems 10 and 11 are readily specialized for the corresponding results of the GeoX/G/1 queue with single vacation [3, p. 130-131] and the same queue with N-policy [3, p. 175].


## 4.1. The Queue-Length Distribution

For this system, we also make use of the well-known property of stochastic decomposition [3, p. 90] and [20] to derive the queue-length distribution. First, we consider an individual cycle by which we mean an idle period plus the following busy period. In a given cycle, we note that a dormant period exists with probability ∑k=0N-1αk. Then we let ri be the probability that the system visits state i (i=0,1,2,…,N-1) during such a dormant period. And πi be the probability that the system visits state i (i=0,1,2,…,N-1) during an idle period in the GeoX/G/1 under N-policy without vacations. For the continuous-time MX/G/1 queue with N-policy and single vacation, Lee et al. [7] show that ri is given by
(16)ri=∑k=0iαkπi-k,i=1,2,…,N-1,r0=α0,r(z)≜∑k=0N-1rkzk.
In this derivation, we notice that it is irrelevant whether the model is continuous or discrete; that is, (16) holds for its discrete-time counterpart as well.Following the procedure presented by Lee et al. [7], we obtain that QN(z) is fully characterized by αi, ai, and ri as follows:
(17)QN(z)=α(z)+A(z)-11-a0∑j=0N-1rjzj,(18)E[QN]=dQN(z)dz|z=1=E[A]E[V]+E[A]1-a0∑j=0N-1rj.
Note that ∑j=0N-1rj is interpreted as the mean number of batch arrivals during a dormant period and E[A]/(1-a0) as the mean batch size.Now, simply substituting (17) into (5) and (4), we have the following.Theorem 7.
For the discrete-timeGeoX/G/1 queue with N-policy and single vacation, the PGF of the stationary queue length and its mean L are given by
(19)P(z)=PGeoX/G/1(z)·1(1-a0)E[V]+∑j=0N-1rj·{(1-a0)[1-α(z)]1-A(z)+r(z)},L=LGeoX/G/1+1(1-a0)E[V]+∑j=0N-1rj·{E[A](1-a0)2E[V2-V]+∑j=0N-1jrj}.Remark 8.
The continuous-time counterpart of Theorem7 was derived by Lee et al. [7] using the supplementary variable technique.Remark 9.
Theorem7 is readily specialized for the corresponding results of the GeoX/G/1 queue with single vacation and the same queue with N-policy. By letting N be 1, the corresponding results for the GeoX/G/1 queue with single vacation [3, p. 132] are obtained. By letting V be a single slot, the corresponding results for the GeoX/G/1 queue with N-policy [3, p. 174] are also obtained.


## 4.2. The Cycle Time

In this section, we first consider the idle period and then the busy period. LetIN and IN(z) denote the number of slots of an idle period and its PGF. Then we have the following.Theorem 10.
For the discrete-timeGeoX/G/1 queue with N-policy and single vacation, the PGF of an idle period and its mean E[IN] are given by
(20)IN(z)=V(z)+∑k=0N-1[[IN-k0(z)-1]·[∑j=1∞zjak(j)vj]],(21)E[IN]=E[V]+11-a0∑j=0N-1rj.Proof.
Conditioning on the length of the first vacation and the number of customers that arrive during this vacation (denoted by#(V)), we have the following recursive equation:
(22)IN(z∣V=j,#(V)=k)={zj·IN-k0(z)k<Nzjk≥N,
where IN0(z) denotes the PGF for an idle period in GeoX/G/1 under N-policy without vacations. Then, unconditioning (22) on #(V), we have
(23)IN(z∣V=j)=∑k=0∞IN(z∣V=j,#(V)=k),·Pr(#(V)=k∣V=j)=zj[1+∑k=0N-1ak(j){IN-k0(z)-1}],
where ak(j) is the probability that k customers arrive during j slots with its PGF given by [a(z)]j=∑k=0∞ak(j)zk. Next, unconditioning (23) on V, we have the desired result (20):
(24)IN(z)=∑j=1∞IN(z∣V=j)·vj=V(z)+∑k=0N-1[[IN-k0(z)-1]·[∑j=1∞zjak(j)vj]].
From (18), we have
(25)E[IN]=E[QN]E[A]=E[V]+11-a0∑j=0N-1rj.Note that∑j=0N-1rj/(1-a0) is interpreted as the mean length of a dormant period, where 1/(1-a0) represents the mean interbatch time.Next, we consider the busy period. LetBN and BN(z) denote the number of slots of a busy period and its PGF. Following the same procedure as presented in Section 3, we have the following.Theorem 11.
For the discrete-timeGeoX/G/1 queue with N-policy and single vacation, the PGF of a busy period and its mean E[BN] are given by
(26)BN(z)=QN[Θ(z)],E[BN]=dBN(z)dz|z=1=ρ1-ρ{E[V]+11-a0∑j=0N-1rj}=ρ1-ρE[IN].Remark 12.
Along the same lines as presented above, the continuous-time counterparts of Theorems10 and 11 have been derived by Lee et al. [7]. Theorems 10 and 11 are readily specialized for the corresponding results of the GeoX/G/1 queue with single vacation [3, p. 130-131] and the same queue with N-policy [3, p. 175].


## 5. Concluding Remarks

In this paper, we consider the discrete-timeGeoX/G/1 queues under N-policy with multiple and single vacations. As a result, PGFs of queue-length distributions are obtained, and PGFs of the lengths of idle and busy periods are also presented. These results have not been presented previously in the literature. In addition, our approach is fairly simple to solve complex problems comparing to other previous works. For example, the supplementary variable technique needs a lengthy and difficult calculation. Our simple and unified approach is based on the well-known property of stochastic decomposition. The results presented in this paper specialize some fundamental vacation models that include the GeoX/G/1 queues with single vacation, multiple vacations, and N policy.Finally, we remark that all the results obtained in this paper for models under AF assumptions also hold for those under DF assumptions. This is because assumptions on the order of simultaneous events at a slot boundary do not affect the system state during a slot (see Kim et al. [20]).



---

*Source: 587163-2013-12-26.xml*