# Analysis of Queue-Length Dependent Vacations and P-Limited Service in BMAP/G/1/N Systems: Stationary Distributions and Optimal Control

Authors: A. D. Banik
Journal: International Journal of Stochastic Analysis
 (2013)

---

## Abstract

We consider a finite-buffer single server queueing system with queue-length dependent vacations where arrivals occur according to a batch Markovian arrival process (BMAP). The service discipline is P-limited service, also called E-limited with limit variation (ELV) where the server serves until either the system is emptied or a randomly chosen limit ofL customers has been served. Depending on the number of customers present in the system, the server will monitor his vacation times. Queue-length distributions at various epochs such as before, arrival, arbitrary and after, departure have been obtained. Several other service disciplines like Bernoulli scheduling, nonexhaustive service, and E-limited service can be treated as special cases of the P-limited service. Finally, the total expected cost function per unit time is considered to determine locally optimal values N* of N or a maximum limit L^* of L^ as the number of customers served during a service period at a minimum cost.


---

## Body

## 1. Introduction

Queueing systems with vacations have found wide applications in the modelling and analysis of computer and communication networks and several other engineering systems in which single server is performing more than one type of jobs. Modelling such systems as single server queues with vacations allows one to analyze each queue in relative isolation since the time the server is attending to other jobs in the system may be modeled as vacation. For more details and versatile implementation of vacation models, one can refer to the comprehensive survey by Doshi [1]. Vacation models are distinguished by their scheduling disciplines, that is, the rules governing when a service stops and a vacation begins. Several service disciplines in combination with vacations are possible, for example, exhaustive, limited, gated, exhaustive limited (E-limited), gated limited (G-limited), and so forth. In fact, there is an extensive amount of literature available on infinite- and finite-buffer M/G/1 and GI/M/1 type vacation models that can be found in Takagi [2, 3], Tian and Zhang [4], and so forth.Traditional teletraffic analysis using Poisson process is not powerful enough to capture the correlated and bursty nature of traffic arising in the present high-speed networks where packets or cells of voice, video, images and data are sent over a common transmission channel on statistical multiplexing basis. The performance analysis of statistical multiplexers whose input consists of superposition of several packetized sources has been done through some analytically tractable arrival process, for example, Markovian arrival process (MAP); see Lucantoni et al. [5]. To consider batch arrival of variable capacity, Lucantoni [6, 7] introduced batch Markovian arrival process (BMAP) which is a convenient representation of the versatile Markovian point process; see Neuts [8]. BMAP includes many familiar input processes such as Markovian arrival process (MAP), Markov modulated Poisson process (MMPP), PH-type renewal process, interrupted Poisson process (IPP), Poisson process. Later on, some researchers have analyzed queueing systems of finite- or infinite-buffer with MAP or BMAP arrival, for example, Akar and Arikan [9], Nishimura [10], Lee et al. [11], Dudin [12], Dudin et al. [13], and so forth. Asymptotic analysis of MAP/G/1 type queueing system has been performed by a few researchers, for example, Kim et al. [14], Gouweleeuw [15], and so forth. Chydzinski [16] obtained probability distribution of time to reach a buffer capacity in a BMAP/G/1 system. Further, Matendo [17], Ferrandiz [18], and so forth have discussed BMAP/G/1 queue with vacations. As queueing analysis of finite systems is more realistic in applications than infinite systems, the detailed study of finite capacity vacation model BMAP/G/1/N queue under exhaustive service discipline was performed by Niu et al. [19] where they have included setup time, close-down time, and single/multiple vacations.In this paper, we analyze BMAP/G/1/N queue where the server serves until either the system empties or a randomly chosen limit of L(0≤L≤L^) customers has been served, whichever occurs first. The server then goes for a vacation of random length of time depending on the number of customers remaining in the system. For example, the duration of vacation time will be short if there are a large number of customers present in the system, whereas duration of vacation time will be long if there are very few number of customers who are waiting for service. Returning from a vacation if the queue is empty or the limit L=0 is chosen, then the server takes another vacation of length depending on the number of customers present in the preceding vacation termination instant. The service discipline analyzed in this paper is known as P-limited service; see Takagi [3, page 398]. P-limited service was earlier studied by LaMaire [20, 21] for the case of M/G/1 infinite and finite buffer queue, respectively, and he uses the term E-limited with limit variation (ELV) for P-limited service. The analysis of MAP/G/1/N queue with limited service discipline is carried out by Blondia [22] and Gupta et al. [23]. Banik et al. [24, 25] discussed BMAP/G/1/N queue under limited service disciplines. Queue-length dependent vacation schedule has been studied by Shin and Pearce [26] for the case of infinite-buffer BMAP/G/1 system with queue-length dependent vacation and Bernoulli scheduling. In case of finite-buffer batch arrival queue, a batch which upon arrival does not find enough space in the buffer is either fully rejected or a part of that batch is rejected. Some queueing protocols are based on the former strategy, and they are known as the total batch acceptance/rejection policy. The latter one is known as the partial batch acceptance/rejection policy. For more details on different type of batch acceptance/rejection policies in the context of finite-buffer BMAP/G/1 queue, readers are referred to Dudin et al. [13]. In this paper, we analyze partial batch acceptance strategy and obtain queue-length distributions at various epochs using a combination of embedded Markov chain and the supplementary variable method. One may note here that results of several vacation policies, namely, Bernoulli scheduling, exhaustive service, pure limited service and E-limited, service can be obtained as special cases of P-limited service model. Regarding the decision making, study of cost model for a practical situation is useful to optimize the cost, for example, see Lee and Srinivasan [27], Lee and Park [28], and Wang and Ke [29]. For this reason, we calculate the total expected cost function per unit time to determine locally optimal values N* of N and L^* of L^. At the end we provide some numerical results using the analytical results obtained in this paper. Finally, some conclusions and future research directions are discussed.


## 2. Description of the Model

Let us consider a BMAP/G/1/N queue wherein the server is allowed to serve a maximum of L(0≤L≤L^) customers during a busy period, and then the server goes for a vacation whose duration depends on the number of customers present in the system. Here, N is the capacity of queue excluding the one in service. That is, there is N+1 different type of vacations. The server may go for any one of the i(0≤i≤N)th type of vacation. If the queue has been emptied after a service, then the server will take (i=0)-type of vacation. On the other hands if L customers have been served during a service period and a total of i(0<i≤N) customers remain in the system, then the server will take i(0<i≤N)th type of vacation. After returning from a vacation, if the queue is empty or a limit zero is chosen, the server immediately goes on another vacation of ith (0≤i≤N) type if there are a i(0≤i≤N) number of customer who remain after the end of previous vacation completion instant. The limit L is a random variable whose mass function is denoted by pL(0≤L≤L^). The limit for the number of customers to be served during a service interval (i.e., a busy period) is determined at the preceding vacation termination instant. The sequence of limits chosen at these instants is independent and identically distributed random variables (i.i.d.r.vs.). By suitably choosing pL, one can obtain results for several other service disciplines, including Bernoulli scheduling, exhaustive service, pure limited service and E-limited service; for example, if we take pL^=1 and pL=0(0≤L<L^), then the service system is equivalent to E-limited service. If L^→∞(=1) in the above assumption, the service system is equivalent to exhaustive service system (= pure limited service). Bernoulli scheduling system can be thought of as a special case of P-limited service system with L^→∞, p0=0 and pL=(1-p)pL-1, 0<p<1 for L=1,2,….The input process is BMAP where arrivals are governed by an underlyingm-state Markov chain which is characterized by m×m matrices Dk, k≥0, where (i,j)th (1≤i,j≤m) element of D0 is the state transition rate from state i to state j in the underlying Markov chain without an arrival and (i,j)th element of Dk, k≥1, is the state transition rate from state i to state j in the underlying Markov chain with an arrival of batch size k. The matrix D0 has nonnegative off-diagonal and negative diagonal elements, and the matrix Dk, k≥1, has nonnegative elements. Let N(t) denote the number of arrivals in (0,t], and let J(t) be the state of the underlying Markov chain at time t. Then, {N(t),J(t)} is a two-dimensional Markov process of BMAP with state space {(n,i):n≥0,1≤i≤m}. The infinitesimal generator of BMAP is given by
(1)Q=(D0D1D2D3⋯0D0D1D2⋯00D0D1⋯⋮⋮⋮⋮⋱).
As Q is the infinitesimal generator of the BMAP, we have ∑k=0∞‍Dke=0, where e is an m×1 column vector with all its elements equal to 1. If e’s dimension is other than m, we denote by e regardless of its dimension. Further, since D=∑k=0∞‍Dk is irreducible infinitesimal generator of the underlying Markov chain {J(t)}, there exists a stationary probability vector π¯ such that π¯D=0, π¯e=1. Then, the average arrival rate λ* and average batch arrival rate λg of the stationary BMAP are given by λ*=π¯∑k=1∞‍kDke and λg=π¯∑k=1∞‍Dke=π¯D1′e, respectively, where Dn′=∑i=n∞‍Di.Let us define{P(n,t),0≤n≤N,t≥0} as m×m matrix whose (i,j)th element is the conditional probability that n customers accepted in the queueing system whose maximum capacity is N excluding the one in service. Since we deal with finite-buffer queue with of batch arrival, one may consider different kinds batch acceptance/or rejection strategies; see Dudin et al. [13]. The matrices P(n,t) satisfy the following system of difference-differential equations for the case of partial batch acceptance strategy:
(2)P(1)(n,t)=P(n,t)D0+∑k=0n-1‍P(k,t)Dn-k,0≤n≤N-1,P(1)(N,t)=P(N,t)D0′+∑k=0N-1‍P(k,t)DN-k′,
with P(0,0)=Im, where Im is an identity matrix of order m for the above three cases and P(1)(n,t)=(d/dt)P(n,t).LetS(x){s(x)}[S*(θ)] be the distribution function (DF) {probability density function (pdf)} [Laplace-Stieltjes transform (LST)] of the service time S of a typical customer. Similarly, Vi(x){vi(x)}[Vi*(θ)](0≤i≤N) is the DF {pdf} [LST] of a typical vacation time Vi of the server where i denotes the number of customers present in the system at the starting point of a vacation. The mean service [vacation] time is E(S)=-S*(1)(0)[E(Vi)=-Vi*(1)(0)], where f*(j)(ζ) is the jth (j≥1) derivative of f*(θ) at θ=ζ. The service, vacation times are assumed to be i.i.d.r.vs. and each is independent of the arrival process. The traffic intensity is given by ρ=λ*E(S). Further, let ρ′ be the probability that the server is busy. The state of the system at time t is described by the r.vs., namely,(i)
(3)ξ(t)={(k,L),iftheserverisservingkth(1≤k≤L)customerintheserviceperiodconsistingofservicesofatthemostL(1≤L≤L^)customers,i,iftheserverisonavacationwhichstartedwithi(0≤i≤N)customersinthesystem,(ii)
Nq(t) is the number of customers present in the queue excluding the one in service,(iii)
J(t) is the state of the underlying Markov chain of BMAP,(iv)
S~(t) is the remaining service time of the customer in service,(v)
V~i(t) is the remaining vacation time of the server, whereas this vacation started with i(0≤i≤N) customers in the system.We define for 1≤i≤m the joint probabilities of queue-length Nq(t), state of the server ξ(t), and the remaining service (vacation) time S~(V~j), respectively, by
(4)πi,L[k](n,x;t)Δx=P{Nq(t)=n,J(t)=i,x<S~(t)<x+Δx,ξ(t)=(k,L)},0≤n≤N,1≤L≤L^,1≤k≤L,x≥0,ωi,j(n,x;t)Δx=P{Nq(t)=n,J(t)=i,x<V~j(t)<x+Δx,ξ(t)=j},0≤n≤N,0≤j≤n,x≥0.
As we shall discuss the model in limiting case, that is, when t→∞ the above probabilities will be denoted by πi,L[k](n,x) and ωi,j(n,x). Let us further define the row vectors of order 1×m as follows:
(5)πL[k](n,x)=[πi,L[k](n,x)],ωj(n,x)=[ωi,j(n,x)],1≤i≤m,
where πi,L[k](n,x) denotes the arbitrary epoch probability that there are n customers in the queue and the state of the arrival process is i when the server is serving the kth customer whose remaining service time is x in the present busy period consisting of the sum of the service times of L or lesser number of customers. Similarly, ωi,j(n,x) denotes the arbitrary epoch probability that n customers are in the queue and state of the arrival process is i when the server is on vacation of jth (0≤j≤n) type with remaining vacation time x.


## 3. Queue-Length Distributions at Various Epochs

### 3.1. Queue-Length Distribution at Service Completion and Vacation Termination Epochs

Consider the system at service completion/vacation termination epochs which are taken as embedded points. Lett0,t1,t2,… be the time epochs at which either service completion or vacation termination occurs. ti+, i≥0 denotes the time epoch just after a service completion or vacation termination occurs. The state of the system at ti+ is defined as {Nq(ti+),ξ(ti+),J(ti+)}, where Nq(ti+), ξ(ti+) and J(ti+) are defined earlier. Therefore, ξ(ti+)=j(0≤j≤N) indicates that the embedded point is jth type vacation termination instant which started with j customers in the system, whereas ξ(ti+)=(k,L)(1≤L≤L^,1≤k≤L) indicates that the embedded point is a service completion instant of the kth customer in the present busy period consisting of services of L or lesser number of customers. In limiting case, these probability distributions are
(6)gj,L[k](n)=limi→∞P(Nq(ti+)=n,ξ(ti+)=(k,L),J(ti+)=j),0≤n≤N,1≤k≤L,1≤L≤L^,1≤j≤m,fj,r(n)=limi→∞P(Nq(ti+)=n,ξ(ti+)=j,J(ti+)=i),0≤n≤N,1≤j≤m,0≤r≤n,
where gj,L[k](n) represents the probability that there are n customers in the queue and the state of the arrival process is j at service completion epoch of the kth customer in the service period consisting of services of at the most L customers. Similarly, fi,j(n) represents the probability that there are n customers in the queue and the state of the arrival process is i at jth type vacation termination epoch. Further, let us denote the row vectors of order 1×m:
(7)gL[k](n)=[gj,L[k](n)],fj(n)=[fi,j(n)],1≤j≤m.LetAn(Vn,k), n≥0, 0≤k≤n, denote an m×m matrix whose (i,j)th element represents the conditional probability that n customers have been accepted during a service (kth type vacation, i.e., vacation started with k customers) time of a customer (the server), and the underlying Markov chain is in phase j at the end of the service (kth type vacation) time given that the underlying Markov chain was in phase i at the beginning of the service (kth type vacation). An and Vn,k as the m×m matrices of mass functions as defined above are given by
(8)An=∫0∞‍P(n,t)dS(t),0≤n≤N,(9)Anc=∑k=nN‍Ak,1≤n≤N,(10)Vn,k=∫0∞‍P(n,t)dVk(t),0≤n≤N,0≤k≤N,(11)Vn,kc=∑i=nN‍Vi,k,0≤n≤N,0≤k≤N.
Obviously, Aic, i≥N+1 will be equal to null matrix of order m×m and similarly, for Vi,kc, i≥N+1.Observing the system immediately after each embedded point, we have the transition probability matrix (TPM)𝒫  with four block matrices of the following form: (12)𝒫=[Ξ(N+1)(L^(L^+1)/2)m×(N+1)(L^(L^+1)/2)mΩ(N+1)(L^(L^+1)/2)m×((N+1)(N+2)/2)mΔ((N+1)(N+2)/2)m×(N+1)(L^(L^+1)/2)mΦ((N+1)(N+2)/2)m×((N+1)(N+2)/2)m]((N+1)(L^(L^+1)+N+2)/2)m×((N+1)(L^(L^+1)+N+2)/2)m,where Ξ describes the probability of transitions among the service completion epochs. A typical service completion epoch will be denoted by the triplet {Nq(ti+),ξ(ti+),J(ti+)} of which we first consider the change in Nq(ti+), that is, n(0≤n≤N), and the second element of ξ(ti+)=(k,L), that is, L(1≤L≤L^) to describe the construction of the first block of the TPM. Then the elements of Ξ can be written as follows:
(13)Ξ(i,L),(j,L′)={Qj-i+1(L),1≤i≤N,i-1≤j≤N-1,2≤L=L′≤L^,Q¯j-i+1(L),1≤i≤N,j=N,2≤L=L′≤L^,0lm,otherwise,
where Qr(L), Q¯r(L), 0≤r≤N, 2≤L≤L^ are all matrices of order lm×lm. 0 is the null matrix of order given in the suffix. The matrices Qr(L) and Qrc(L) are given by
(14)(Qr(L))i,j={Ar,2≤L≤L^,1≤i≤L;j=i+1,0m,otherwise,(Q¯r(L))i,j={Arc,2≤L≤L^,1≤i≤L;j=i+1,0m,otherwise.Ω gives the probability of transition from any service completion epoch to the next vacation termination epochs. Vacation termination epochs are classified by the {Nq(ti+),ξ(ti+),J(ti+)} of which we consider the change in Nq(ti+), that is, n(0≤n≤N) and in case of vacation termination epoch ξ(ti+)=s, that is, the number of customers present at the last service completion instant. The structure of Ω is given by
(15)Ω(i,L,k)(j,s)={Vj,s,i=0,s=i,1≤L≤L^,1≤k≤L,0≤j≤N-1,Vj,sc,i=0,s=i,1≤L≤L^,1≤k≤L,j=N,Vj-i,s,1≤i≤N,s=i,1≤L≤L^,k=L,i≤j≤N-1,Vj-i,sc,1≤i≤N,s=i,1≤L≤L^,k=L,j=N,0m,otherwise.Δ of TPM gives the probability of transition from every vacation termination epoch to the next service completion epochs. This block is of the given form following:
(16)Δ(i,s)(j,L,k)={pLAj-i+1,1≤i≤N,0≤s≤i,1≤L≤L^,k=1,i-1≤j≤N-1,pLAj-i+1c,1≤i≤N,0≤s≤i,1≤L≤L^,k=1,j=N,0motherwise.Φ of the TPM describes the probability of transitions among vacation termination epochs. This block matrix is of the following form:
(17)Φ(i,s)(j,k)={Vj,0,i=0,s=0=k,0≤j<N,Vj,0c,i=0,s=0=k,j=N,p0Vj-i,i,1≤i≤N,0≤s≤i,k=i,i≤j≤N-1,p0Vj-i,ic,1≤i≤N,0≤s≤i,k=i,j=N,0m,otherwise.The evaluation of the matricesAn(Vn,k), in general, for arbitrary service (vacation) time distribution requires numerical integration or infinite summation, and it can be carried out along the lines proposed by Lucantoni [6] for BMAP arrival. For the sake of completeness, in the following we present the derivation of finding the matrix An. As presented in [6], applying uniformization argument to the matrices P(n,t) is of the given form following:
(18)P(n,t)=∑l=0∞‍e-ψt(ψt)ll!Un(l),0≤n≤N,
where ψ=maxi{-[D0]ii}(1≤i≤m) and Un(l) is given by
(19)U0(0)=Im,Un(0)=0,U0(l+1)=U0(l)(Im+ψ-1D0),Un(l+1)=Un(l)(Im+ψ-1D0)+ψ-1∑i=0n-1‍Ui(l)Dn-i,1≤n≤N-1,l≥0,UN(l+1)=UN(l)(Im+ψ-1D0)+ψ-1∑i=0N-1‍Ui(l)DN-i′,l≥0.
Now, substituting the values of P(n,t) from (18) in (8), we obtain
(20)An=∑l=0∞‍rlUn(l),0≤n≤N,
where rl=∫0∞‍e-ψt((ψt)l/l!)dS(t). Similarly, the matrix Vn,k can be found out for any arbitrary vacation time distribution function Vk(t). However, when the service (vacation) time distributions are of phase type (PH-distribution), these matrices can be evaluated without any numerical integration; see Neuts [30, pages 67–70]. It may be noted here that various service (vacation) time distributions arising in practical applications can be approximated by PH-distribution. The following theorem gives a procedure for the computation of the matrices An(Vn,k).Theorem 1.
IfS(x) follow PH-distribution with irreducible representation (β,U), where β and U are of dimension γ, then the matrices An are given by
(21)An=Bn(Im⊗U0),0≤n≤N,
where
(22)B0=-(Im⊗β)[D0⊗Iγ+Im⊗U]-1,Bn=-∑i=0n-1‍Bi(Dn-i⊗Iγ)[D0⊗Iγ+Im⊗U]-1,Bn=-∑i=0n-1‍Bi(Dn-i⊗Iγ)….1≤n≤N-1,BN=-∑i=0N-1‍Bi[DN-i′⊗Iγ](D⊗Iγ+Im⊗U)-1,
with U0=-Ueγ, and the symbol ⊗ denotes the Kronecker product of two matrices. Similarly, let Vk(x) follow a PH-distribution with irreducible representation (αk,Tk), where αk and Tk are of dimension μk, then the matrices Vn,k are given by
(23)Vn,k=Rn,k(Im⊗T0),0≤n≤N,0≤k≤n,
where
(24)R0,k=-(Im⊗αk)[D0⊗Iμk+Im⊗Tk]-1,Rn,k=-∑i=0n-1‍Ri,k(Dn-i⊗Iμk)[D0⊗Iμk+Im⊗Tk]-1,Rn,k=-∑i=0n-1‍Ri,k(Dn-i⊗Iμk)1≤n≤N-1,RN,k=-∑i=0N-1‍Ri,k[DN-i′⊗Iμk](D⊗Iμk+Im⊗Tk)-1,
with T0=-Teμk.Proof.
See Neuts [30, pages 67–70], Banik and Gupta [25], and so forth.The unknown probability vectorsgL[k](n) and fj(n) can be obtained by solving the system of equations: (gL[k](n),fj(n))=(gL[k](n),fj(n))𝒫 and (gL[k](n),fj(n))e=1. We use GTH algorithm, see Grassmann et al. [31], for solving the system of equations.Considering the departure of a customer as an embedded point excluding vacation termination epochs, one may obtain queue-length distributions at departure epoch. Distributions of number of customers in the queue at service completion and departure epochs are proportional. LetuL[k](n) denote a row vector whose ith element represents steady-state probability that there are n(0≤n≤N) customers in the queue and phase of the arrival process is i(1≤i≤m) at departure epoch of the kth (1≤k≤L) customer in the service period consisting of services of L(1≤L≤L^) or lesser number of customers. Since uL[k](n) is proportional to gL[k](n) and ∑n=0N‍∑L=1L^‍∑k=1L‍uL[k](n)e=1, we get
(25)uL[k](n)=gL[k](n)∑i=0N∑r=1L^∑s=1rgr[s](n)e,0≤n≤N,1≤L≤L^,1≤k≤L.


### 3.2. Queue-Length Distribution at Arbitrary Epoch

To determine queue-length distribution at arbitrary epoch, we will develop relations between distributions of number of customers in the queue at service completion (vacation termination) and arbitrary epochs. Supplementary variable method has been used, and for that we relate the states of the system at two consecutive time epochst and t+Δt, and using probabilistic arguments, we have a set of partial differential equations for each phase i, (1≤i≤m). Taking limit as t→∞ and using matrices and vector notations, we obtain
(26)-ddxπL[1](0,x)=πL[1](0,x)D0+pL∑j=01‍ωj(1,0)s(x),-ddxπL[1](0,x)1≤L≤L^,-ddxπL[k](0,x)=πL[k](0,x)D0+πL[k-1](1,0)s(x),-ddxπL[1](0,x)2≤L≤L^,2≤k≤L,-ddxπL[1](n,x)=πL[1](n,x)D0+∑i=1n‍πL[1](n-i,x)Di+pL∑j=0n+1‍ωj(n+1,0)s(x),1≤n≤N-2,1≤L≤L^,-ddxπL[1](n,x)=πL[1](n,x)D0+∑i=1n‍πL[1](n-i,x)Di+pL∑j=0n+1‍ωj(n+1,0)s(x),-ddxπL[1](n,x)n=N-1,1≤L≤L^,-ddxπL[1](n,x)=πL[1](n,x)D0+∑i=1n‍πL[1](n-i,x)Di+πL[k-1](n+1,0)s(x),1≤n≤N-2,1≤L≤L^,2≤k≤L,-ddxπL[k](N,x)=πL[k](N,x)D0′+∑i=1N‍πL[k](N-i,x)Di′,1≤L≤L^,1≤k≤L,-ddxωj(0,x)=ωj(0,x)D0+(∑L=1L^‍∑k=1LπL[k](0,0)‍+ωj(0,0))vj(x),j=0,-ddxωj(n,x)=ωj(n,x)D0+∑i=0n-j-1‍ωj(j+i,x)Dn-j-i-ddxωj(n,x)=+p0ωj(n,0)vj(x),1≤n≤N-1,0≤j<n,-ddxωj(n,x)=ωj(n,x)D0+(∑L=1L^‍πL[L](n,0)+p0ωj(n,0))vj(x),1≤n≤N-1,j=n,-ddxωj(N,x)=ωj(N,x)D0′+∑i=0N-j-1‍ωj(j+i,x)DN-j-i′-ddxωj(N,x)=+p0ωj(N,0)vj(x),0≤j<N,-ddxωj(N,x)=ωj(N,x)D0′-ddxωj(N,x)=+(∑L=1L^‍πL[L](N,0)+p0ωj(N,0))vj(x),j=N,
where πL[k](n,0)(ωj(n,0)) are the respective departure rates of customers (vacation termination rates of the server). Let us define the Laplace transform of πL[k](n,x) and ωj(n,x) as
(27)πL*[k](n,θ)=∫0∞‍e-θxπL[k](n,x)dx,20ωj*(n,θ)=∫0∞‍e-θxωj(n,x)dx,0≤n≤N,1≤L≤L^,1≤k≤L,0≤n≤N,1.0≤j≤n,Reθ≥0,
so that
(28)πL[k](n)≡πL*[k](n,0)=∫0∞‍πL[k](n,x)dx,ωj(n)≡ωj*(n,0)=∫0∞‍ωj(n,x)dx.
Multiplying (26) by e-θx and integrating with respect to. x over 0 to ∞, we obtain
(29)-θπL*[1](0,θ)+πL[1](0,0)=πL*[1](0,θ)D0+pL∑j=01‍ωj(1,0)S*(θ),1≤L≤L^,(30)-θπL*[k](0,θ)+πL[k](0,0)=πL*[k](0,θ)D0+πL[k-1](1,0)S*(θ),2≤L≤L^,2≤k≤L,(31)-θπL*[1](n,θ)+πL[1](n,0)=πL*[1](n,θ)D0+∑i=1n‍πL*[1](n-i,θ)Di+pL∑j=0n+1‍ωj(n+1,0)S*(θ),1≤n≤N-2,1≤L≤L^,(32)-θπL*[1](n,θ)+πL[1](n,0)=πL*[1](n,θ)D0+∑i=1n‍πL*[1](n-i,θ)Di+pL∑j=0n+1‍ωj(n+1,0)S*(θ),n=N-1,1≤L≤L^,(33)-θπL*[k](n,θ)+πL[k](n,0)=πL*[k](n,θ)D0+∑i=1n‍πL*[k](n-i,θ)Di+πL[k-1](n+1,0)S*(θ),1≤n≤N-1,2≤L≤L^,2≤k≤L,(34)-θπL*[k](N,θ)+πL[k](N,0)=πL*[k](N,θ)D0′+∑i=1N‍πL*[k](N-i,θ)Di′,1≤n≤N-1,,,,,,1≤L≤L^,1≤k≤L,(35)-θωj*(0,θ)+ωj(0,0)=ωj*(0,θ)D0+(∑L=1L^‍∑k=1L‍πL[k](0,0)+ωj(0,0))Vj*(θ),j=0,(36)-θωj*(n,θ)+ωj(n,0)=ωj*(n,θ)D0+∑i=0n-j-1‍ωj*(j+i,θ)Dn-j-i+p0ωj(n,0)Vj*(θ),1≤n≤N-1,0≤j<n,(37)-θωj*(n,θ)+ωj(n,0)=ωj*(n,θ)D0+(∑L=1L^‍πL[L](n,0)+p0ωj(n,0))Vj*(θ),1≤n≤N-1,j=n,(38)-θωj*(N,θ)+ωj(N,0)=ωj*(N,θ)D0'+∑i=0N-j-1ωj*(j+i,θ)DN-j-i',,+p0ωj(N,0)Vj*(θ),0≤j<N,(39)-θωj*(N,θ)+ωj(N,0)=ωj*(N,θ)D0'+(∑L=1L^‍πL[L](N,0)+p0ωj(N,0))Vj*(θ),ωj*(N,θ)D0'+(∑L=1L^‍πL[L](N,0)+p0ωj(N,0))….j=N.
Using equations (29)–(39), we will derive certain results in the form of lemmas and theorems.Lemma 2.
Consider the following:(40)∑L=2L^‍∑k=1L-1‍πL[L](0,0)e+∑n=0N‍∑L=1L^‍πL[L](n,0)e=∑n=1N‍∑L=1L^‍∑j=0n‍pLωj(n,0)e.
The left hand side is the mean number of entrances into the vacation states per unit of time, and the right hand side is the mean number of departure from the vacation states per unit of time.Proof.
Settingθ=0 in (29)–(34), using (28), and then post-multiplying all the equations by the vector e and adding them, using D0′e=0 after simplification, we obtain the result.Theorem 3.
Consider the following:(41)E(S)∑n=0N‍∑L=1L^‍∑k=1L‍πL[k](n,0)e=∑n=0N‍∑L=1L^‍∑k=1L‍πL[k](n)e=ρ′,(42)∑n=0N‍∑j=0n‍E(Vj)ωj(n,0)e=∑n=0N‍∑j=0n‍ωj(n)e=1-ρ′.∑n=0N‍∑L=1L^‍∑k=1L‍πL[k](n,0)e denotes the mean number of service completions per unit of time, and multiplying this by E(S) will give ρ′. Similarly, the other result can be interpreted.Proof.
Differentiating (29)–(34) w.r.t. θ, setting θ=0 in those equations and postmultiplying by e, adding them using D0′e=0 and Lemma 2, after simplification, we obtain (41). Similarly, post-multiplying (35)–(39) by e, differentiating these equations w.r.t θ, and setting θ=0, after some algebraic manipulation, we obtain ∑n=0N‍∑j=0n‍E(Vj)ωj(n,0)e=∑n=0N‍∑j=0n‍ωj(n)e.


#### 3.2.1. Relation between Queue-Length Distributions at Arbitrary and Service Completion (Vacation Termination) Epochs

We first relate the service completion (vacation termination) epoch probabilities,gL[k](n) and fj(n), with the rates πL[k](n,0) and ωj(n,0) which are given by
(43)gi,L[k](n)=πi,L[k](n,0)∑n=0N∑r=1L^∑s=1rπr[s](n,0)e+∑n=0N∑r=0nωr(n,0)e=1σπi,L[k](n,0),0≤n≤N,1≤L≤L^,1≤k≤L,1≤i≤m,
and similarly,
(44)fi,j(n)=1σωi,j(n,0),0≤n≤N,0≤j≤n,1≤i≤m,
where σ=∑n=0N‍∑r=1L^‍∑s=1r‍πr[s](n,0)e+∑n=0N‍∑r=0n‍ωr(n,0)e. Employing the above relations, we will determine arbitrary epoch probabilities in terms of service completion or vacation termination epoch probabilities. Setting θ=0 in the (29)–(33) and (35)-(36), using (43) and (44), we obtain the following relations:
(45)πL[1](0)=(σ(pL∑j=01‍fj(1)-gL[1](0)))(-D0)-1,1≤L≤L^,πL[k](0)=σ(gL[k-1](1)-gL[k](0))(-D0)-1,2≤L≤L^,2≤k≤L,πL[1](n)=(∑i=1n‍πL[1](n-i)Di+σ(pL∑j=0n+1‍fj(n+1)-gL[1](n)))(-D0)-1,1≤n≤N-2,1≤L≤L^,πL[1](n)=(∑i=1n‍πL[1](n-i)Di+σ(pL∑j=0n+1‍fj(n+1)-gL[1](n)))(-D0)-1,fffffffffffffffffffffffffffffn=N-1,1≤L≤L^,πL[k](n)=(∑i=1n‍πL[k](n-i)Di∑i=1n‍+σ(gL[k-1](n+1)-gL[k](n)))(-D0)-1,gg1≤n≤N-1,2≤L≤L^,2≤k≤L,ωj(0)=σ(∑L=1L^‍∑k=1L‍gL[k](0))(-D0)-1,ωj(n)=(∑i=0n-j-1‍ωj(j+i)Dn-j-ik∑i=1n‍+σ(p0fj(n)-fj(n)))(-D0)-1,kkkkk1≤n≤N-1,0≤j<n,ωj(n)=(σ(∑L=1L^‍gL[L](n)+p0fj(n)-fj(n)))(-D0)-1,ωj(n)=σkkkkk(n)JJJJJJJJ1≤n≤N-1,j=n.
It may be noted here that we do not have such expression for πL[k](N) and ωj(N). However, one can compute ∑L=1L^‍∑k=1L‍πL[k](N)e and ∑j=0N‍ωj(N)e by using Theorem 1 and is given by ∑L=1L^‍∑k=1L‍πL[k](N)e=ρ′-∑n=0N-1‍∑L=1L^‍∑k=1L‍πL[k](n)e and ω(N)e=(1-ρ′)-∑n=0N-1‍∑j=0n‍ωj(n)e, respectively. Though the vectors πL[k](N) and ωj(N) are not obtained componentwise, ∑L=1L^‍∑k=1L‍πL[k](N)e and ∑j=0N‍ωj(N)e are sufficient to determine key performance measures (Section 4).Lemma 4.
ρ
′ (probability that the server is busy) is given by
(46)ρ′=E(S)∑n=0N∑L=1L^∑k=1LgL[k](n)e×(E(S)∑n=0N∑L=1L^∑k=1LgL[k](n)e+∑n=0N∑j=0NE(Vj)fj(n)e)-1.Proof.
LetΘb{Θi} be the random variable denoting the length of busy {idle} period and θb{θi} be the mean length of a busy {idle} period, then we have
(47)ρ′=θbθb+θi,θbθi=∑n=0N∑L=1L^∑k=1LπL[k](n)e∑n=0N∑j=0Nωj(n)e.
Applying Theorem 3, and then dividing numerator and denominator by σ, using (43) and (44), we can write the pervious ratio as
(48)θbθi=E(S)∑n=0N∑L=1L^∑k=1LgL[k](n)e∑n=0N∑j=0NE(Vj)fj(n)e.
The above ratio yields the result.Remark 5.
One may note here thatσ is frequently needed for calculation of the state probabilities, and it can be obtained by using ρ′ and (43) in (41).
Letq(n) denote the row vector of order 1×m whose ith component is the probability of n(0≤n≤N) customers in the queue at arbitrary epoch, and state of the arrival process is i(1≤i≤m). q(n) is given by
(49)q(0)=∑L=1L^‍∑k=1L‍πL[k](0)+ω0(0),q(n)=∑L=1L^‍∑k=1L‍πL[k](n)+∑j=0n‍ωj(n),1≤n≤N-1,q(N)=π--∑n=0N-1‍(∑L=1L^‍∑k=1L‍πL[k](n)+∑j=0n‍ωj(n)).


### 3.3. Queue-Length Distributions at Prearrival Epoch

Letp-(n) be the 1×m vectors whose jth components are given by pj-(n) which gives the probability that an arrival finds n(0≤n≤N) customers in the queue, and the arrival process is in state j at the postarrival instant. The vectors p-(n) is given by
(50)p-(n)=q(n)∑i=1∞Diλg=q(n)D1′λg,0≤n≤N.


## 3.1. Queue-Length Distribution at Service Completion and Vacation Termination Epochs

Consider the system at service completion/vacation termination epochs which are taken as embedded points. Lett0,t1,t2,… be the time epochs at which either service completion or vacation termination occurs. ti+, i≥0 denotes the time epoch just after a service completion or vacation termination occurs. The state of the system at ti+ is defined as {Nq(ti+),ξ(ti+),J(ti+)}, where Nq(ti+), ξ(ti+) and J(ti+) are defined earlier. Therefore, ξ(ti+)=j(0≤j≤N) indicates that the embedded point is jth type vacation termination instant which started with j customers in the system, whereas ξ(ti+)=(k,L)(1≤L≤L^,1≤k≤L) indicates that the embedded point is a service completion instant of the kth customer in the present busy period consisting of services of L or lesser number of customers. In limiting case, these probability distributions are
(6)gj,L[k](n)=limi→∞P(Nq(ti+)=n,ξ(ti+)=(k,L),J(ti+)=j),0≤n≤N,1≤k≤L,1≤L≤L^,1≤j≤m,fj,r(n)=limi→∞P(Nq(ti+)=n,ξ(ti+)=j,J(ti+)=i),0≤n≤N,1≤j≤m,0≤r≤n,
where gj,L[k](n) represents the probability that there are n customers in the queue and the state of the arrival process is j at service completion epoch of the kth customer in the service period consisting of services of at the most L customers. Similarly, fi,j(n) represents the probability that there are n customers in the queue and the state of the arrival process is i at jth type vacation termination epoch. Further, let us denote the row vectors of order 1×m:
(7)gL[k](n)=[gj,L[k](n)],fj(n)=[fi,j(n)],1≤j≤m.LetAn(Vn,k), n≥0, 0≤k≤n, denote an m×m matrix whose (i,j)th element represents the conditional probability that n customers have been accepted during a service (kth type vacation, i.e., vacation started with k customers) time of a customer (the server), and the underlying Markov chain is in phase j at the end of the service (kth type vacation) time given that the underlying Markov chain was in phase i at the beginning of the service (kth type vacation). An and Vn,k as the m×m matrices of mass functions as defined above are given by
(8)An=∫0∞‍P(n,t)dS(t),0≤n≤N,(9)Anc=∑k=nN‍Ak,1≤n≤N,(10)Vn,k=∫0∞‍P(n,t)dVk(t),0≤n≤N,0≤k≤N,(11)Vn,kc=∑i=nN‍Vi,k,0≤n≤N,0≤k≤N.
Obviously, Aic, i≥N+1 will be equal to null matrix of order m×m and similarly, for Vi,kc, i≥N+1.Observing the system immediately after each embedded point, we have the transition probability matrix (TPM)𝒫  with four block matrices of the following form: (12)𝒫=[Ξ(N+1)(L^(L^+1)/2)m×(N+1)(L^(L^+1)/2)mΩ(N+1)(L^(L^+1)/2)m×((N+1)(N+2)/2)mΔ((N+1)(N+2)/2)m×(N+1)(L^(L^+1)/2)mΦ((N+1)(N+2)/2)m×((N+1)(N+2)/2)m]((N+1)(L^(L^+1)+N+2)/2)m×((N+1)(L^(L^+1)+N+2)/2)m,where Ξ describes the probability of transitions among the service completion epochs. A typical service completion epoch will be denoted by the triplet {Nq(ti+),ξ(ti+),J(ti+)} of which we first consider the change in Nq(ti+), that is, n(0≤n≤N), and the second element of ξ(ti+)=(k,L), that is, L(1≤L≤L^) to describe the construction of the first block of the TPM. Then the elements of Ξ can be written as follows:
(13)Ξ(i,L),(j,L′)={Qj-i+1(L),1≤i≤N,i-1≤j≤N-1,2≤L=L′≤L^,Q¯j-i+1(L),1≤i≤N,j=N,2≤L=L′≤L^,0lm,otherwise,
where Qr(L), Q¯r(L), 0≤r≤N, 2≤L≤L^ are all matrices of order lm×lm. 0 is the null matrix of order given in the suffix. The matrices Qr(L) and Qrc(L) are given by
(14)(Qr(L))i,j={Ar,2≤L≤L^,1≤i≤L;j=i+1,0m,otherwise,(Q¯r(L))i,j={Arc,2≤L≤L^,1≤i≤L;j=i+1,0m,otherwise.Ω gives the probability of transition from any service completion epoch to the next vacation termination epochs. Vacation termination epochs are classified by the {Nq(ti+),ξ(ti+),J(ti+)} of which we consider the change in Nq(ti+), that is, n(0≤n≤N) and in case of vacation termination epoch ξ(ti+)=s, that is, the number of customers present at the last service completion instant. The structure of Ω is given by
(15)Ω(i,L,k)(j,s)={Vj,s,i=0,s=i,1≤L≤L^,1≤k≤L,0≤j≤N-1,Vj,sc,i=0,s=i,1≤L≤L^,1≤k≤L,j=N,Vj-i,s,1≤i≤N,s=i,1≤L≤L^,k=L,i≤j≤N-1,Vj-i,sc,1≤i≤N,s=i,1≤L≤L^,k=L,j=N,0m,otherwise.Δ of TPM gives the probability of transition from every vacation termination epoch to the next service completion epochs. This block is of the given form following:
(16)Δ(i,s)(j,L,k)={pLAj-i+1,1≤i≤N,0≤s≤i,1≤L≤L^,k=1,i-1≤j≤N-1,pLAj-i+1c,1≤i≤N,0≤s≤i,1≤L≤L^,k=1,j=N,0motherwise.Φ of the TPM describes the probability of transitions among vacation termination epochs. This block matrix is of the following form:
(17)Φ(i,s)(j,k)={Vj,0,i=0,s=0=k,0≤j<N,Vj,0c,i=0,s=0=k,j=N,p0Vj-i,i,1≤i≤N,0≤s≤i,k=i,i≤j≤N-1,p0Vj-i,ic,1≤i≤N,0≤s≤i,k=i,j=N,0m,otherwise.The evaluation of the matricesAn(Vn,k), in general, for arbitrary service (vacation) time distribution requires numerical integration or infinite summation, and it can be carried out along the lines proposed by Lucantoni [6] for BMAP arrival. For the sake of completeness, in the following we present the derivation of finding the matrix An. As presented in [6], applying uniformization argument to the matrices P(n,t) is of the given form following:
(18)P(n,t)=∑l=0∞‍e-ψt(ψt)ll!Un(l),0≤n≤N,
where ψ=maxi{-[D0]ii}(1≤i≤m) and Un(l) is given by
(19)U0(0)=Im,Un(0)=0,U0(l+1)=U0(l)(Im+ψ-1D0),Un(l+1)=Un(l)(Im+ψ-1D0)+ψ-1∑i=0n-1‍Ui(l)Dn-i,1≤n≤N-1,l≥0,UN(l+1)=UN(l)(Im+ψ-1D0)+ψ-1∑i=0N-1‍Ui(l)DN-i′,l≥0.
Now, substituting the values of P(n,t) from (18) in (8), we obtain
(20)An=∑l=0∞‍rlUn(l),0≤n≤N,
where rl=∫0∞‍e-ψt((ψt)l/l!)dS(t). Similarly, the matrix Vn,k can be found out for any arbitrary vacation time distribution function Vk(t). However, when the service (vacation) time distributions are of phase type (PH-distribution), these matrices can be evaluated without any numerical integration; see Neuts [30, pages 67–70]. It may be noted here that various service (vacation) time distributions arising in practical applications can be approximated by PH-distribution. The following theorem gives a procedure for the computation of the matrices An(Vn,k).Theorem 1.
IfS(x) follow PH-distribution with irreducible representation (β,U), where β and U are of dimension γ, then the matrices An are given by
(21)An=Bn(Im⊗U0),0≤n≤N,
where
(22)B0=-(Im⊗β)[D0⊗Iγ+Im⊗U]-1,Bn=-∑i=0n-1‍Bi(Dn-i⊗Iγ)[D0⊗Iγ+Im⊗U]-1,Bn=-∑i=0n-1‍Bi(Dn-i⊗Iγ)….1≤n≤N-1,BN=-∑i=0N-1‍Bi[DN-i′⊗Iγ](D⊗Iγ+Im⊗U)-1,
with U0=-Ueγ, and the symbol ⊗ denotes the Kronecker product of two matrices. Similarly, let Vk(x) follow a PH-distribution with irreducible representation (αk,Tk), where αk and Tk are of dimension μk, then the matrices Vn,k are given by
(23)Vn,k=Rn,k(Im⊗T0),0≤n≤N,0≤k≤n,
where
(24)R0,k=-(Im⊗αk)[D0⊗Iμk+Im⊗Tk]-1,Rn,k=-∑i=0n-1‍Ri,k(Dn-i⊗Iμk)[D0⊗Iμk+Im⊗Tk]-1,Rn,k=-∑i=0n-1‍Ri,k(Dn-i⊗Iμk)1≤n≤N-1,RN,k=-∑i=0N-1‍Ri,k[DN-i′⊗Iμk](D⊗Iμk+Im⊗Tk)-1,
with T0=-Teμk.Proof.
See Neuts [30, pages 67–70], Banik and Gupta [25], and so forth.The unknown probability vectorsgL[k](n) and fj(n) can be obtained by solving the system of equations: (gL[k](n),fj(n))=(gL[k](n),fj(n))𝒫 and (gL[k](n),fj(n))e=1. We use GTH algorithm, see Grassmann et al. [31], for solving the system of equations.Considering the departure of a customer as an embedded point excluding vacation termination epochs, one may obtain queue-length distributions at departure epoch. Distributions of number of customers in the queue at service completion and departure epochs are proportional. LetuL[k](n) denote a row vector whose ith element represents steady-state probability that there are n(0≤n≤N) customers in the queue and phase of the arrival process is i(1≤i≤m) at departure epoch of the kth (1≤k≤L) customer in the service period consisting of services of L(1≤L≤L^) or lesser number of customers. Since uL[k](n) is proportional to gL[k](n) and ∑n=0N‍∑L=1L^‍∑k=1L‍uL[k](n)e=1, we get
(25)uL[k](n)=gL[k](n)∑i=0N∑r=1L^∑s=1rgr[s](n)e,0≤n≤N,1≤L≤L^,1≤k≤L.


## 3.2. Queue-Length Distribution at Arbitrary Epoch

To determine queue-length distribution at arbitrary epoch, we will develop relations between distributions of number of customers in the queue at service completion (vacation termination) and arbitrary epochs. Supplementary variable method has been used, and for that we relate the states of the system at two consecutive time epochst and t+Δt, and using probabilistic arguments, we have a set of partial differential equations for each phase i, (1≤i≤m). Taking limit as t→∞ and using matrices and vector notations, we obtain
(26)-ddxπL[1](0,x)=πL[1](0,x)D0+pL∑j=01‍ωj(1,0)s(x),-ddxπL[1](0,x)1≤L≤L^,-ddxπL[k](0,x)=πL[k](0,x)D0+πL[k-1](1,0)s(x),-ddxπL[1](0,x)2≤L≤L^,2≤k≤L,-ddxπL[1](n,x)=πL[1](n,x)D0+∑i=1n‍πL[1](n-i,x)Di+pL∑j=0n+1‍ωj(n+1,0)s(x),1≤n≤N-2,1≤L≤L^,-ddxπL[1](n,x)=πL[1](n,x)D0+∑i=1n‍πL[1](n-i,x)Di+pL∑j=0n+1‍ωj(n+1,0)s(x),-ddxπL[1](n,x)n=N-1,1≤L≤L^,-ddxπL[1](n,x)=πL[1](n,x)D0+∑i=1n‍πL[1](n-i,x)Di+πL[k-1](n+1,0)s(x),1≤n≤N-2,1≤L≤L^,2≤k≤L,-ddxπL[k](N,x)=πL[k](N,x)D0′+∑i=1N‍πL[k](N-i,x)Di′,1≤L≤L^,1≤k≤L,-ddxωj(0,x)=ωj(0,x)D0+(∑L=1L^‍∑k=1LπL[k](0,0)‍+ωj(0,0))vj(x),j=0,-ddxωj(n,x)=ωj(n,x)D0+∑i=0n-j-1‍ωj(j+i,x)Dn-j-i-ddxωj(n,x)=+p0ωj(n,0)vj(x),1≤n≤N-1,0≤j<n,-ddxωj(n,x)=ωj(n,x)D0+(∑L=1L^‍πL[L](n,0)+p0ωj(n,0))vj(x),1≤n≤N-1,j=n,-ddxωj(N,x)=ωj(N,x)D0′+∑i=0N-j-1‍ωj(j+i,x)DN-j-i′-ddxωj(N,x)=+p0ωj(N,0)vj(x),0≤j<N,-ddxωj(N,x)=ωj(N,x)D0′-ddxωj(N,x)=+(∑L=1L^‍πL[L](N,0)+p0ωj(N,0))vj(x),j=N,
where πL[k](n,0)(ωj(n,0)) are the respective departure rates of customers (vacation termination rates of the server). Let us define the Laplace transform of πL[k](n,x) and ωj(n,x) as
(27)πL*[k](n,θ)=∫0∞‍e-θxπL[k](n,x)dx,20ωj*(n,θ)=∫0∞‍e-θxωj(n,x)dx,0≤n≤N,1≤L≤L^,1≤k≤L,0≤n≤N,1.0≤j≤n,Reθ≥0,
so that
(28)πL[k](n)≡πL*[k](n,0)=∫0∞‍πL[k](n,x)dx,ωj(n)≡ωj*(n,0)=∫0∞‍ωj(n,x)dx.
Multiplying (26) by e-θx and integrating with respect to. x over 0 to ∞, we obtain
(29)-θπL*[1](0,θ)+πL[1](0,0)=πL*[1](0,θ)D0+pL∑j=01‍ωj(1,0)S*(θ),1≤L≤L^,(30)-θπL*[k](0,θ)+πL[k](0,0)=πL*[k](0,θ)D0+πL[k-1](1,0)S*(θ),2≤L≤L^,2≤k≤L,(31)-θπL*[1](n,θ)+πL[1](n,0)=πL*[1](n,θ)D0+∑i=1n‍πL*[1](n-i,θ)Di+pL∑j=0n+1‍ωj(n+1,0)S*(θ),1≤n≤N-2,1≤L≤L^,(32)-θπL*[1](n,θ)+πL[1](n,0)=πL*[1](n,θ)D0+∑i=1n‍πL*[1](n-i,θ)Di+pL∑j=0n+1‍ωj(n+1,0)S*(θ),n=N-1,1≤L≤L^,(33)-θπL*[k](n,θ)+πL[k](n,0)=πL*[k](n,θ)D0+∑i=1n‍πL*[k](n-i,θ)Di+πL[k-1](n+1,0)S*(θ),1≤n≤N-1,2≤L≤L^,2≤k≤L,(34)-θπL*[k](N,θ)+πL[k](N,0)=πL*[k](N,θ)D0′+∑i=1N‍πL*[k](N-i,θ)Di′,1≤n≤N-1,,,,,,1≤L≤L^,1≤k≤L,(35)-θωj*(0,θ)+ωj(0,0)=ωj*(0,θ)D0+(∑L=1L^‍∑k=1L‍πL[k](0,0)+ωj(0,0))Vj*(θ),j=0,(36)-θωj*(n,θ)+ωj(n,0)=ωj*(n,θ)D0+∑i=0n-j-1‍ωj*(j+i,θ)Dn-j-i+p0ωj(n,0)Vj*(θ),1≤n≤N-1,0≤j<n,(37)-θωj*(n,θ)+ωj(n,0)=ωj*(n,θ)D0+(∑L=1L^‍πL[L](n,0)+p0ωj(n,0))Vj*(θ),1≤n≤N-1,j=n,(38)-θωj*(N,θ)+ωj(N,0)=ωj*(N,θ)D0'+∑i=0N-j-1ωj*(j+i,θ)DN-j-i',,+p0ωj(N,0)Vj*(θ),0≤j<N,(39)-θωj*(N,θ)+ωj(N,0)=ωj*(N,θ)D0'+(∑L=1L^‍πL[L](N,0)+p0ωj(N,0))Vj*(θ),ωj*(N,θ)D0'+(∑L=1L^‍πL[L](N,0)+p0ωj(N,0))….j=N.
Using equations (29)–(39), we will derive certain results in the form of lemmas and theorems.Lemma 2.
Consider the following:(40)∑L=2L^‍∑k=1L-1‍πL[L](0,0)e+∑n=0N‍∑L=1L^‍πL[L](n,0)e=∑n=1N‍∑L=1L^‍∑j=0n‍pLωj(n,0)e.
The left hand side is the mean number of entrances into the vacation states per unit of time, and the right hand side is the mean number of departure from the vacation states per unit of time.Proof.
Settingθ=0 in (29)–(34), using (28), and then post-multiplying all the equations by the vector e and adding them, using D0′e=0 after simplification, we obtain the result.Theorem 3.
Consider the following:(41)E(S)∑n=0N‍∑L=1L^‍∑k=1L‍πL[k](n,0)e=∑n=0N‍∑L=1L^‍∑k=1L‍πL[k](n)e=ρ′,(42)∑n=0N‍∑j=0n‍E(Vj)ωj(n,0)e=∑n=0N‍∑j=0n‍ωj(n)e=1-ρ′.∑n=0N‍∑L=1L^‍∑k=1L‍πL[k](n,0)e denotes the mean number of service completions per unit of time, and multiplying this by E(S) will give ρ′. Similarly, the other result can be interpreted.Proof.
Differentiating (29)–(34) w.r.t. θ, setting θ=0 in those equations and postmultiplying by e, adding them using D0′e=0 and Lemma 2, after simplification, we obtain (41). Similarly, post-multiplying (35)–(39) by e, differentiating these equations w.r.t θ, and setting θ=0, after some algebraic manipulation, we obtain ∑n=0N‍∑j=0n‍E(Vj)ωj(n,0)e=∑n=0N‍∑j=0n‍ωj(n)e.


### 3.2.1. Relation between Queue-Length Distributions at Arbitrary and Service Completion (Vacation Termination) Epochs

We first relate the service completion (vacation termination) epoch probabilities,gL[k](n) and fj(n), with the rates πL[k](n,0) and ωj(n,0) which are given by
(43)gi,L[k](n)=πi,L[k](n,0)∑n=0N∑r=1L^∑s=1rπr[s](n,0)e+∑n=0N∑r=0nωr(n,0)e=1σπi,L[k](n,0),0≤n≤N,1≤L≤L^,1≤k≤L,1≤i≤m,
and similarly,
(44)fi,j(n)=1σωi,j(n,0),0≤n≤N,0≤j≤n,1≤i≤m,
where σ=∑n=0N‍∑r=1L^‍∑s=1r‍πr[s](n,0)e+∑n=0N‍∑r=0n‍ωr(n,0)e. Employing the above relations, we will determine arbitrary epoch probabilities in terms of service completion or vacation termination epoch probabilities. Setting θ=0 in the (29)–(33) and (35)-(36), using (43) and (44), we obtain the following relations:
(45)πL[1](0)=(σ(pL∑j=01‍fj(1)-gL[1](0)))(-D0)-1,1≤L≤L^,πL[k](0)=σ(gL[k-1](1)-gL[k](0))(-D0)-1,2≤L≤L^,2≤k≤L,πL[1](n)=(∑i=1n‍πL[1](n-i)Di+σ(pL∑j=0n+1‍fj(n+1)-gL[1](n)))(-D0)-1,1≤n≤N-2,1≤L≤L^,πL[1](n)=(∑i=1n‍πL[1](n-i)Di+σ(pL∑j=0n+1‍fj(n+1)-gL[1](n)))(-D0)-1,fffffffffffffffffffffffffffffn=N-1,1≤L≤L^,πL[k](n)=(∑i=1n‍πL[k](n-i)Di∑i=1n‍+σ(gL[k-1](n+1)-gL[k](n)))(-D0)-1,gg1≤n≤N-1,2≤L≤L^,2≤k≤L,ωj(0)=σ(∑L=1L^‍∑k=1L‍gL[k](0))(-D0)-1,ωj(n)=(∑i=0n-j-1‍ωj(j+i)Dn-j-ik∑i=1n‍+σ(p0fj(n)-fj(n)))(-D0)-1,kkkkk1≤n≤N-1,0≤j<n,ωj(n)=(σ(∑L=1L^‍gL[L](n)+p0fj(n)-fj(n)))(-D0)-1,ωj(n)=σkkkkk(n)JJJJJJJJ1≤n≤N-1,j=n.
It may be noted here that we do not have such expression for πL[k](N) and ωj(N). However, one can compute ∑L=1L^‍∑k=1L‍πL[k](N)e and ∑j=0N‍ωj(N)e by using Theorem 1 and is given by ∑L=1L^‍∑k=1L‍πL[k](N)e=ρ′-∑n=0N-1‍∑L=1L^‍∑k=1L‍πL[k](n)e and ω(N)e=(1-ρ′)-∑n=0N-1‍∑j=0n‍ωj(n)e, respectively. Though the vectors πL[k](N) and ωj(N) are not obtained componentwise, ∑L=1L^‍∑k=1L‍πL[k](N)e and ∑j=0N‍ωj(N)e are sufficient to determine key performance measures (Section 4).Lemma 4.
ρ
′ (probability that the server is busy) is given by
(46)ρ′=E(S)∑n=0N∑L=1L^∑k=1LgL[k](n)e×(E(S)∑n=0N∑L=1L^∑k=1LgL[k](n)e+∑n=0N∑j=0NE(Vj)fj(n)e)-1.Proof.
LetΘb{Θi} be the random variable denoting the length of busy {idle} period and θb{θi} be the mean length of a busy {idle} period, then we have
(47)ρ′=θbθb+θi,θbθi=∑n=0N∑L=1L^∑k=1LπL[k](n)e∑n=0N∑j=0Nωj(n)e.
Applying Theorem 3, and then dividing numerator and denominator by σ, using (43) and (44), we can write the pervious ratio as
(48)θbθi=E(S)∑n=0N∑L=1L^∑k=1LgL[k](n)e∑n=0N∑j=0NE(Vj)fj(n)e.
The above ratio yields the result.Remark 5.
One may note here thatσ is frequently needed for calculation of the state probabilities, and it can be obtained by using ρ′ and (43) in (41).
Letq(n) denote the row vector of order 1×m whose ith component is the probability of n(0≤n≤N) customers in the queue at arbitrary epoch, and state of the arrival process is i(1≤i≤m). q(n) is given by
(49)q(0)=∑L=1L^‍∑k=1L‍πL[k](0)+ω0(0),q(n)=∑L=1L^‍∑k=1L‍πL[k](n)+∑j=0n‍ωj(n),1≤n≤N-1,q(N)=π--∑n=0N-1‍(∑L=1L^‍∑k=1L‍πL[k](n)+∑j=0n‍ωj(n)).


## 3.2.1. Relation between Queue-Length Distributions at Arbitrary and Service Completion (Vacation Termination) Epochs

We first relate the service completion (vacation termination) epoch probabilities,gL[k](n) and fj(n), with the rates πL[k](n,0) and ωj(n,0) which are given by
(43)gi,L[k](n)=πi,L[k](n,0)∑n=0N∑r=1L^∑s=1rπr[s](n,0)e+∑n=0N∑r=0nωr(n,0)e=1σπi,L[k](n,0),0≤n≤N,1≤L≤L^,1≤k≤L,1≤i≤m,
and similarly,
(44)fi,j(n)=1σωi,j(n,0),0≤n≤N,0≤j≤n,1≤i≤m,
where σ=∑n=0N‍∑r=1L^‍∑s=1r‍πr[s](n,0)e+∑n=0N‍∑r=0n‍ωr(n,0)e. Employing the above relations, we will determine arbitrary epoch probabilities in terms of service completion or vacation termination epoch probabilities. Setting θ=0 in the (29)–(33) and (35)-(36), using (43) and (44), we obtain the following relations:
(45)πL[1](0)=(σ(pL∑j=01‍fj(1)-gL[1](0)))(-D0)-1,1≤L≤L^,πL[k](0)=σ(gL[k-1](1)-gL[k](0))(-D0)-1,2≤L≤L^,2≤k≤L,πL[1](n)=(∑i=1n‍πL[1](n-i)Di+σ(pL∑j=0n+1‍fj(n+1)-gL[1](n)))(-D0)-1,1≤n≤N-2,1≤L≤L^,πL[1](n)=(∑i=1n‍πL[1](n-i)Di+σ(pL∑j=0n+1‍fj(n+1)-gL[1](n)))(-D0)-1,fffffffffffffffffffffffffffffn=N-1,1≤L≤L^,πL[k](n)=(∑i=1n‍πL[k](n-i)Di∑i=1n‍+σ(gL[k-1](n+1)-gL[k](n)))(-D0)-1,gg1≤n≤N-1,2≤L≤L^,2≤k≤L,ωj(0)=σ(∑L=1L^‍∑k=1L‍gL[k](0))(-D0)-1,ωj(n)=(∑i=0n-j-1‍ωj(j+i)Dn-j-ik∑i=1n‍+σ(p0fj(n)-fj(n)))(-D0)-1,kkkkk1≤n≤N-1,0≤j<n,ωj(n)=(σ(∑L=1L^‍gL[L](n)+p0fj(n)-fj(n)))(-D0)-1,ωj(n)=σkkkkk(n)JJJJJJJJ1≤n≤N-1,j=n.
It may be noted here that we do not have such expression for πL[k](N) and ωj(N). However, one can compute ∑L=1L^‍∑k=1L‍πL[k](N)e and ∑j=0N‍ωj(N)e by using Theorem 1 and is given by ∑L=1L^‍∑k=1L‍πL[k](N)e=ρ′-∑n=0N-1‍∑L=1L^‍∑k=1L‍πL[k](n)e and ω(N)e=(1-ρ′)-∑n=0N-1‍∑j=0n‍ωj(n)e, respectively. Though the vectors πL[k](N) and ωj(N) are not obtained componentwise, ∑L=1L^‍∑k=1L‍πL[k](N)e and ∑j=0N‍ωj(N)e are sufficient to determine key performance measures (Section 4).Lemma 4.
ρ
′ (probability that the server is busy) is given by
(46)ρ′=E(S)∑n=0N∑L=1L^∑k=1LgL[k](n)e×(E(S)∑n=0N∑L=1L^∑k=1LgL[k](n)e+∑n=0N∑j=0NE(Vj)fj(n)e)-1.Proof.
LetΘb{Θi} be the random variable denoting the length of busy {idle} period and θb{θi} be the mean length of a busy {idle} period, then we have
(47)ρ′=θbθb+θi,θbθi=∑n=0N∑L=1L^∑k=1LπL[k](n)e∑n=0N∑j=0Nωj(n)e.
Applying Theorem 3, and then dividing numerator and denominator by σ, using (43) and (44), we can write the pervious ratio as
(48)θbθi=E(S)∑n=0N∑L=1L^∑k=1LgL[k](n)e∑n=0N∑j=0NE(Vj)fj(n)e.
The above ratio yields the result.Remark 5.
One may note here thatσ is frequently needed for calculation of the state probabilities, and it can be obtained by using ρ′ and (43) in (41).
Letq(n) denote the row vector of order 1×m whose ith component is the probability of n(0≤n≤N) customers in the queue at arbitrary epoch, and state of the arrival process is i(1≤i≤m). q(n) is given by
(49)q(0)=∑L=1L^‍∑k=1L‍πL[k](0)+ω0(0),q(n)=∑L=1L^‍∑k=1L‍πL[k](n)+∑j=0n‍ωj(n),1≤n≤N-1,q(N)=π--∑n=0N-1‍(∑L=1L^‍∑k=1L‍πL[k](n)+∑j=0n‍ωj(n)).


## 3.3. Queue-Length Distributions at Prearrival Epoch

Letp-(n) be the 1×m vectors whose jth components are given by pj-(n) which gives the probability that an arrival finds n(0≤n≤N) customers in the queue, and the arrival process is in state j at the postarrival instant. The vectors p-(n) is given by
(50)p-(n)=q(n)∑i=1∞Diλg=q(n)D1′λg,0≤n≤N.


## 4. Performance Measures

In this section, we discuss the various performance measures which are often needed for investigating the behavior of a queueing system. As the state probabilities at which departure, arbitrary and prearrival epochs are known, the corresponding mean queue-lengths can be easily obtained. For example, the average number in the queue at any arbitrary epoch isLq=∑i=0N‍iq(i)e, the average number in the queue when the server is busy is Lq1=∑i=0N‍i[∑L=1L^‍∑k=1L‍πL[k](i)]e, and the average number in the queue when the server is on vacation is Lq2=∑i=0N‍i∑j=0i‍ωj(i)e. It may be remarked here that for large values of N, the computation of Lq may pose some problems because of the storage of large number of probability vectors πL[k](n). The problem can be resolved by using main frame computer and applying efficient memory management technique. One useful performance measure is the blocking probability which is discussed below.


### 4.1. Blocking Probabilities

Since prearrival epoch probabilities are known, the blocking probability of the first customer of an arriving batch is given by(51)PBLF=p-(N)e=q(N)D1'eλg.
Let Fk be the matrix of order m×m whose element [Fk]ij is the probability that the position of an arbitrary customer in an arriving batch is k with phase changes from i to j. The probability that an arbitrary customer belongs to a batch of size n is given by π¯nDne/λ*. Hence, the position of an arbitrary customer in a batch of size n is k with corresponding phase changes is equal to (1/n)·(Dn/π¯Dne), k=1,2,3,…,n, where 1/n denotes the probability that an arbitrary customer belongs to a batch of size n. Therefore,
(52)Fk=π¯nDneλ*·1n·Dnπ-Dne=∑n=k∞‍Dnλ*,k=1,2,3,….
Hence, the blocking probability of an arbitrary customer (PBLA) is given by
(53)PBLA=∑n=0N‍q(n)∑k=N-n+1∞‍Fke.
Finally, the blocking probability of the last customer of a batch (PBLE) is given by
(54)PBLE=∑i=0N‍∑j=N-i+1∞‍q(i)Djeλg.
One may note that mean waiting time Wq (in queue) of an arbitrary customer can be obtained using Little’s law, and it is given by Wq=Lq/λ′, where λ′ is the mean effective arrival rate and is given by
(55)λ′=λ*(1-PBLA).Remark 6.
One may note here thatλ′ can be obtained another way as described below. In the steady-state mean effective arrival rate of customers should be equal to the total mean departure rate of customers. From this argument, we obtain
(56)λ′=∑n=0N‍∑L=1L^‍∑k=1L‍πL[k](n,0)e.
Now, using (41) and (46) in (56), we have
(57)λ′=∑n=0N∑L=1L^∑k=1LgL[k](n)e×(E(S)∑n=0N∑L=1L^∑k=1LgL[k](n)e1+∑n=0N∑j=0NE(Vj)fj(n)e)-1.
Equations (55) and (57) can be used for comparison while performing numerical experiments.


### 4.2. Optimal Policy

In this subsection, we develop the total expected cost function per unit time for this queueing system in whichN and L^ are decision variables. We construct a similar cost structure that has been widely used in many works; see Lee and Srinivasan [27], Lee and Park [28], Wang and Ke [29], and so forth. For this we need explicit expression for expected length of busy and idle period. Let us assume that Φ is the random variable denoting the length of a busy cycle and ϑ is the mean length of busy cycle; then ϑ=θi+θb. From the definition of the carried load ρ′ (the fraction of time that the server is busy), it can be written as
(58)θbθi=ρ′1-ρ′.
We first discuss the expected busy period which is comparatively easy to evaluate. Let Nq(t) denote the number of customers in the queue at time t,  let ξq(t) be the state of the server, that is, busy (=1) or idle (=0), and let Γq(t)=(k,L)(1≤L≤L^,1≤k≤L) represent the kth customer in service in the service period consisting of L or lesser number of customers. Then, {Nq(t),ξq(t),Γq(t)} enters the set of busy states, Υ≡{(0,1,(k,L)),(1,1,(k,L)),(2,1,(k,L)),…,(N,1,(k,L))} at the termination of an idle (vacations) period. The conditional probability that {Nq(t),ξq(t),Γq(t)} enters (n,1)0≤n≤N, given that {Nq(t),ξq(t)} enters (0,1,(k,L)) or (n,1,(L,L)) is therefore C[∑L=1L^‍∑k=1L‍uL[k](0)e+∑n=1N‍uL[L](n)e] where C=1/(∑L=1L^‍∑k=1L‍uL[k](0)e+∑n=1N‍uL[L](n)e). Now, {Nq(t),ξq(t),Γq(t)} enters (n,1,(k,L))(0≤n≤N,1≤L≤L^,1≤k≤L) irrespective of customers’ arrival during a service time, which may happen in expected time E(S). Thus, we have
(59)θb=E(S)∑n=0N∑L=1L^∑k=1LuL[k](n)e∑L=1L^∑k=1LuL[k](0)e+∑n=1NuL[L](n)eθb=E(S)∑L=1L^∑k=1LuL[k](0)e+∑n=1NuL[L](n)e.
Using (59) in (58), we obtain
(60)θi=(1-ρ′ρ′)·E(S)∑L=1L^∑k=1LuL[k](0)e+∑n=1NuL[L](n)e.


#### 4.2.1. Total Expected Cost Function

We consider a cost function per unit time for this BMAP/G/1/N queueing system under P-limited service disciplines with queue-length dependent vacations, in which N and L^ are decision variables. Our objective is to determine the optimum value of the control parameter, say N* and L^*, so as to minimize the expected value of this cost function. Let us define the following costs: Ch = holding cost per unit time per customer present in the system;Cf = cost incurred per unit time for keeping the server off;Co = cost incurred per unit time for keeping the server on;Cs = start-up cost per unit time for turning the server on;Cd = shut-down cost per unit time for turning the server off;Cl = a fixed cost incurred per unit time for every lost customer.Using the definitions of each cost element listed above, the total expected cost function per unit time is given by(61)F(N,L^)=ChLq+Cfθiϑ+Coθbϑ(N,L^)=,,+(Cs+Cd)1ϑ+λ*ClPBLAF(N,L^)=ChLq+Cf(1-ρ′)+Coρ′F(N,L^)=+(Cs+Cd)1ϑ+λ*ClPBLA.
From the pervious formula, locally optimal values N* may be selected for a fixed value of L^ as follows. For each selection of L^, the local optimum value of N, N*, is determined by satisfying the following inequality:
(62)F(N*+1,L^)≥F(N*,L^)≤F(N*-1,L^).
One may be interested to obtain locally optimal values N* and L^* using following procedure. We first select an interval [N1,N2] for buffer capacity (N) and a set of limit distributions; therefore, we can evaluate F(N,L^) for every possible ordered pairs (N,L^), N∈[N1,N2] and L^∈[L^1,L^2]. Finally, comparing each of them, we can determine locally optimal values N* and L^* for which F(N,L^) is a minimal one. This completes analytical analysis of the queueing model under consideration. Now, we present discussion of numerical results in Section 5.


## 4.1. Blocking Probabilities

Since prearrival epoch probabilities are known, the blocking probability of the first customer of an arriving batch is given by(51)PBLF=p-(N)e=q(N)D1'eλg.
Let Fk be the matrix of order m×m whose element [Fk]ij is the probability that the position of an arbitrary customer in an arriving batch is k with phase changes from i to j. The probability that an arbitrary customer belongs to a batch of size n is given by π¯nDne/λ*. Hence, the position of an arbitrary customer in a batch of size n is k with corresponding phase changes is equal to (1/n)·(Dn/π¯Dne), k=1,2,3,…,n, where 1/n denotes the probability that an arbitrary customer belongs to a batch of size n. Therefore,
(52)Fk=π¯nDneλ*·1n·Dnπ-Dne=∑n=k∞‍Dnλ*,k=1,2,3,….
Hence, the blocking probability of an arbitrary customer (PBLA) is given by
(53)PBLA=∑n=0N‍q(n)∑k=N-n+1∞‍Fke.
Finally, the blocking probability of the last customer of a batch (PBLE) is given by
(54)PBLE=∑i=0N‍∑j=N-i+1∞‍q(i)Djeλg.
One may note that mean waiting time Wq (in queue) of an arbitrary customer can be obtained using Little’s law, and it is given by Wq=Lq/λ′, where λ′ is the mean effective arrival rate and is given by
(55)λ′=λ*(1-PBLA).Remark 6.
One may note here thatλ′ can be obtained another way as described below. In the steady-state mean effective arrival rate of customers should be equal to the total mean departure rate of customers. From this argument, we obtain
(56)λ′=∑n=0N‍∑L=1L^‍∑k=1L‍πL[k](n,0)e.
Now, using (41) and (46) in (56), we have
(57)λ′=∑n=0N∑L=1L^∑k=1LgL[k](n)e×(E(S)∑n=0N∑L=1L^∑k=1LgL[k](n)e1+∑n=0N∑j=0NE(Vj)fj(n)e)-1.
Equations (55) and (57) can be used for comparison while performing numerical experiments.


## 4.2. Optimal Policy

In this subsection, we develop the total expected cost function per unit time for this queueing system in whichN and L^ are decision variables. We construct a similar cost structure that has been widely used in many works; see Lee and Srinivasan [27], Lee and Park [28], Wang and Ke [29], and so forth. For this we need explicit expression for expected length of busy and idle period. Let us assume that Φ is the random variable denoting the length of a busy cycle and ϑ is the mean length of busy cycle; then ϑ=θi+θb. From the definition of the carried load ρ′ (the fraction of time that the server is busy), it can be written as
(58)θbθi=ρ′1-ρ′.
We first discuss the expected busy period which is comparatively easy to evaluate. Let Nq(t) denote the number of customers in the queue at time t,  let ξq(t) be the state of the server, that is, busy (=1) or idle (=0), and let Γq(t)=(k,L)(1≤L≤L^,1≤k≤L) represent the kth customer in service in the service period consisting of L or lesser number of customers. Then, {Nq(t),ξq(t),Γq(t)} enters the set of busy states, Υ≡{(0,1,(k,L)),(1,1,(k,L)),(2,1,(k,L)),…,(N,1,(k,L))} at the termination of an idle (vacations) period. The conditional probability that {Nq(t),ξq(t),Γq(t)} enters (n,1)0≤n≤N, given that {Nq(t),ξq(t)} enters (0,1,(k,L)) or (n,1,(L,L)) is therefore C[∑L=1L^‍∑k=1L‍uL[k](0)e+∑n=1N‍uL[L](n)e] where C=1/(∑L=1L^‍∑k=1L‍uL[k](0)e+∑n=1N‍uL[L](n)e). Now, {Nq(t),ξq(t),Γq(t)} enters (n,1,(k,L))(0≤n≤N,1≤L≤L^,1≤k≤L) irrespective of customers’ arrival during a service time, which may happen in expected time E(S). Thus, we have
(59)θb=E(S)∑n=0N∑L=1L^∑k=1LuL[k](n)e∑L=1L^∑k=1LuL[k](0)e+∑n=1NuL[L](n)eθb=E(S)∑L=1L^∑k=1LuL[k](0)e+∑n=1NuL[L](n)e.
Using (59) in (58), we obtain
(60)θi=(1-ρ′ρ′)·E(S)∑L=1L^∑k=1LuL[k](0)e+∑n=1NuL[L](n)e.


### 4.2.1. Total Expected Cost Function

We consider a cost function per unit time for this BMAP/G/1/N queueing system under P-limited service disciplines with queue-length dependent vacations, in which N and L^ are decision variables. Our objective is to determine the optimum value of the control parameter, say N* and L^*, so as to minimize the expected value of this cost function. Let us define the following costs: Ch = holding cost per unit time per customer present in the system;Cf = cost incurred per unit time for keeping the server off;Co = cost incurred per unit time for keeping the server on;Cs = start-up cost per unit time for turning the server on;Cd = shut-down cost per unit time for turning the server off;Cl = a fixed cost incurred per unit time for every lost customer.Using the definitions of each cost element listed above, the total expected cost function per unit time is given by(61)F(N,L^)=ChLq+Cfθiϑ+Coθbϑ(N,L^)=,,+(Cs+Cd)1ϑ+λ*ClPBLAF(N,L^)=ChLq+Cf(1-ρ′)+Coρ′F(N,L^)=+(Cs+Cd)1ϑ+λ*ClPBLA.
From the pervious formula, locally optimal values N* may be selected for a fixed value of L^ as follows. For each selection of L^, the local optimum value of N, N*, is determined by satisfying the following inequality:
(62)F(N*+1,L^)≥F(N*,L^)≤F(N*-1,L^).
One may be interested to obtain locally optimal values N* and L^* using following procedure. We first select an interval [N1,N2] for buffer capacity (N) and a set of limit distributions; therefore, we can evaluate F(N,L^) for every possible ordered pairs (N,L^), N∈[N1,N2] and L^∈[L^1,L^2]. Finally, comparing each of them, we can determine locally optimal values N* and L^* for which F(N,L^) is a minimal one. This completes analytical analysis of the queueing model under consideration. Now, we present discussion of numerical results in Section 5.


## 4.2.1. Total Expected Cost Function

We consider a cost function per unit time for this BMAP/G/1/N queueing system under P-limited service disciplines with queue-length dependent vacations, in which N and L^ are decision variables. Our objective is to determine the optimum value of the control parameter, say N* and L^*, so as to minimize the expected value of this cost function. Let us define the following costs: Ch = holding cost per unit time per customer present in the system;Cf = cost incurred per unit time for keeping the server off;Co = cost incurred per unit time for keeping the server on;Cs = start-up cost per unit time for turning the server on;Cd = shut-down cost per unit time for turning the server off;Cl = a fixed cost incurred per unit time for every lost customer.Using the definitions of each cost element listed above, the total expected cost function per unit time is given by(61)F(N,L^)=ChLq+Cfθiϑ+Coθbϑ(N,L^)=,,+(Cs+Cd)1ϑ+λ*ClPBLAF(N,L^)=ChLq+Cf(1-ρ′)+Coρ′F(N,L^)=+(Cs+Cd)1ϑ+λ*ClPBLA.
From the pervious formula, locally optimal values N* may be selected for a fixed value of L^ as follows. For each selection of L^, the local optimum value of N, N*, is determined by satisfying the following inequality:
(62)F(N*+1,L^)≥F(N*,L^)≤F(N*-1,L^).
One may be interested to obtain locally optimal values N* and L^* using following procedure. We first select an interval [N1,N2] for buffer capacity (N) and a set of limit distributions; therefore, we can evaluate F(N,L^) for every possible ordered pairs (N,L^), N∈[N1,N2] and L^∈[L^1,L^2]. Finally, comparing each of them, we can determine locally optimal values N* and L^* for which F(N,L^) is a minimal one. This completes analytical analysis of the queueing model under consideration. Now, we present discussion of numerical results in Section 5.


## 5. Numerical Results

To demonstrate the applicability of the results obtained in the previous sections, some numerical results have been presented in the form of graphs showing the nature of some performance measures against the variation of some critical model parameters. We have conducted an experiment on the BMAP/PH/1/N queue with queue-length dependent multiple vacations (vacation time follows PH-distribution) for the following input parameters.The 2-state BMAP representation is taken asD0=[-1.512500.7500.875-1.025], D1=[0.3812500.0000000.0625000.012500], D3=[0.2287500.0000000.0375000.007500], D5=[0.1525000.0000000.0250000.005000], where λ*=1.2, λg=0.5, and D2, D4 and Dj(i≥6) are null matrices of order 2. The PH-type representation of a vacation time is taken as α0=[0.70.3], T0=[-1.0981.0990.071-1.832] with E(V0)=1.242509. PH-type representation of service time is taken as β=[0.40.6], S=[-6.6832.4531.367-7.986] with E(S)=0.180050, ρ=λ*E(S)=0.216060. We take the maximum value of the limit L^=5, and the limit mass function is taken as uniform: pL=1/6, for L=0,1,2,…,5. Figure 1 shows the effect of N on ρ′ for the above described BMAP/PH/1/N queue where N varies from 2 to 28. We have conducted this experiment two times to judge the effect of queue-length dependent multiple vacations over normal multiple vacations. Firstly, we assume that the rest of the vacation time distributions Vi(1≤i≤N), which are not given above, are the same as service time distribution given above. Secondly, we consider Vi=V0(1≤i≤N). The reason behind the above assumption is that for the case of queue-length dependent multiple vacation when the system is empty, server stays longer time in vacation, whereas vacation duration is much smaller when any customer presents at the starting point of a vacation.Figure 1
Nversus ρ′.In Figure1, for the case of queue-length dependent multiple vacation queue, as buffer space increases, the model behaves as infinite-buffer queue. It is obvious that a finite-buffer queue behaves like the corresponding infinite-buffer queue as the buffer size increases. Consequently, ρ′ asymptotically approaches towards ρ. We have used our method described in Section 3.1 to evaluate service completion and vacation termination epoch probabilities for BMAP/PH/1/N model. After that we have evaluated the quantity ρ′=0.216029 which closely matches with ρ (upto four decimal places) when N=28. Moreover, one may note that for the case of normal multiple vacation model as N increases, ρ′ also approaches towards ρ with taking lesser value than queue-length dependent multiple vacation queue.In Figure2, we have plotted the blocking probability of an arbitrary customer against N in the above described BMAP/PH/1/N for above described queue-length dependent vacation policy as stated in Figure 1. It is observed that as N, increase blocking probabilities asymptotically approach towards zero for both the cases of queue-length dependent multiple vacations and normal multiple vacations. PBLA is slightly higher for the case of normal multiple vacations than queue-length dependent multiple vacations for any N. One may observe from these experiments that queueing system behaves quite differently for the case of queue-length dependent multiple vacations.Figure 2
N versus PBLA.In Figure3, we have plotted the total expected cost per unit of time against different values of N and the maximum limit (L^) for the number of customers to be served in a busy period for the above described BMAP/PH/1/N queue in Figure 1. N varies from 5 to 30, and L^ is taking values 3, 4 and 5. The limit mass function is taken as uniform, that is, pL=1/(L^+1), for L=0,1,2,…,L^. Various associated costs are defined as Ch=10.3, Cf=20.4, Co=50.6, Cs=20.3, Cd=10.9, and CL=20.1. One can observe from the figure that as N increases, the total expected cost also increases irrespective of different values of L^.Figure 3
N versus L^ versus F(N,L^).In Figures4 and 5, we have plotted the blocking probability of an arbitrary customer and the total expected cost per unit of time against different values of N and L^ in a BMAP/PH/1/N queue with queue-length dependent multiple vacations as described in Figure 3. For both Figures 4 and 5, L^ is taking values 3, 4, and 5 as described in Figure 3. Here, N varies from 5 to 50. The BMAP representation is taken as D0=[-1.51250.7500.875-1.025], D3=D5=[0.0762500.00000.0125000.002500], and D18=[0.6100000.0000000.1000000.020000] where λ*=7.6, λg=0.5, and D1, D2, and Dj(6≤i≤17,i≥19) are null matrices of order 2. The service and queue-length dependent vacation time distributions are the same as described in Figure 1. As a result, traffic intensity (ρ) is equal to 1.368381. The associated costs for Figure 5 are defined the same as Figure 3. From Figure 4, it can be observed that as N increases from 5 to 30, the blocking probabilities of an arbitrary customer decrease for any value of L^. But as N, increases further PBLA also relatively increase. On the other, hand in Figure 5, N increases and the total expected cost also linearly increase for any value of L^. Therefore, one may conclude that the queueing system studied in this paper shows locally interesting behaviour with variations of its model parameters.Figure 4
N versus L^ versus blocking probability of an arbitrary customer.Figure 5
N versus L^ versus F(N,L^).Finally, in Figure6, we have conducted experiments on BMAP/D/1/N queues under queue-length dependent multiple vacations as described in Figure 1. BMAP arrival is taken exactly same as we have taken in Figure 1. Here the service as well as vacation time distributions are taken as non-PH distributions. We have conducted this experiment with two service time distributions. The first service time is taken as deterministic with E(S1)=0.180050 and S1*(θ)=e-0.180050θ. The second service time is also deterministic with E(S2)=0.100757 and S2*(θ)=e-0.100757θ. Therefore, the corresponding traffic intensities are ρ=λ*E(S1)=0.216060 and ρ=λ*E(S2)=0.120908. The vacation time is taken as Gamma distribution with E(V0)=1.242509 and V0*(θ)=(μ/μ+θ)α, where α=3.7 and μ=α/E(V0)=2.977845. We take the maximum value of the limit L^=5 and the limit mass function is taken as uniform: pL=1/6, for L=0,1,2,…,5. Figure 6 shows the effect of N on ρ′ for the above described BMAP/D1/1/N and BMAP/D2/1/N queue where N varies from 2 to 25. We have conducted this experiments for queue-length dependent multiple vacations. We assume that the rest of the vacation time distributions Vi(1≤i≤N), which are not given above, are the same as service time distributions as given above. Since service and vacation time distributions are non-PH they cannot be represented as phase-type (PH) distribution. Therefore, An may be calculated using (20). Using similar method, Vn,k’s may be obtained. After that using these An and Vn,k various state probabilities are calculated using the procedure described in Section 3. Figure 6 shows exactly similar behaviour as Figure 1. That is, as N increases, ρ′ asymptotically approaches toward ρ. The above facts to some extent support our analytical as well as numerical results.Figure 6
N versus ρ′.


## 6. Conclusions and Future Scope

In this paper, we have successfully analyzed the BMAP/G/1/N queue with state-dependent vacations and P-limited service. We have suggested a procedure to obtain the steady-state distributions of the number of customers in the system at various epochs. However, the analysis of the corresponding infinite-buffer queue is an interesting as well as complex problem as it appears tedious to apply matrix-analytic formalism for solving this problem. One may be interested in other kinds of vacation policies, for example, gated or gated limited (G-limited) or G-limited with limit variations and so forth. These problems are left for future investigations.



---

*Source: 196372-2013-11-10.xml*