# Analysis of MAP/PH(1), PH(2)/2 Queue with Bernoulli Vacations

Authors: B. Krishna Kumar; R. Rukmani; V. Thangaraj
Journal: Journal of Applied Mathematics and Stochastic Analysis
 (2008)

---

## Abstract

We consider a
two-heterogeneous-server queueing system with
Bernoulli vacation in which customers arrive according to a Markovian arrival
process (MAP). Servers returning from vacation immediately take another vacation
if no customer is waiting. Using matrix-geometric method, the steady-state
probability of the number of customers in the system is investigated. Some important
performance measures are obtained. The waiting time distribution and
the mean waiting time are also discussed. Finally, some numerical illustrations
are provided.


---

## Body

## 1. Introduction

Queueing  systems that
allow servers to take vacation
have a wide range of applications in many engineering systems such as flexible
manufacturing environments, production, computers, communication networks, and
telecommunication systems. Servers' vacations are useful for the systems in
which the servers want to utilize their idle times for different purposes. For
instance, servers' vacations may be due to lack of work, servers' failure, or
some other tasks being assigned to the servers
which occur in applications like computer maintenance and testing, preventive
maintenance job in a production system, priority queue, and so forth (see [1]).In general, queueing systems with vacations can be
classified as systems with a single server or multiple servers involving single
vacation or multiple vacations. The servers may take vacations at a random
time, after serving utmostk customers (k-limited) or after all the customers in the
queue are served (exhaustive). Also, depending on the applications, when the
server finishes a vacation and there is no customer to be served, the server
may take another vacation (multiple vacation model) or it may wait ready to
serve until a new customer arrives (single vacation model). The queueing
systems with single and multiple vacations have been first investigated by
Levy and Yechiali [2].Another interesting and important vacation model is
Bernoulli vacation scheduling service. The Bernoulli vacation scheduling
service discipline has been proposed by Keilson and Servi [3]. In this
service discipline, when the server visits a queue, at least one customer, if
any, is served. After the completion of its service, the server switches to the
next vacation if there are no customers. If customers remain, however, in the
queue, the next customer is served with probability q,
and the server repeats this procedure, or the server switches to the next vacation
with probability p(=1−q). The important merit of the Bernoulli vacation
scheduling service discipline is the existence of a control parameter q. By adjusting the value of q, we can control the congestion of the system.
We note that when q=1,
the Bernoulli vacation scheduling service discipline is equivalent to the
exhaustive service discipline, and q=0 corresponds to the 1-limited service
discipline. Servi [4] has proposed an approximate procedure to calculate the
average waiting time of an asymmetric polling system under the Bernoulli
scheduling service discipline. Further, Tedijanto [5] has investigated in
detail the stochastic behavior of a polling system under the Bernoulli vacation
scheduling service discipline and has obtained the average waiting time of a
symmetric system. For comprehensive and excellent surveys/monographs on
queueing systems with server vacations, see [1, 6–8], and the references therein.In the literature, there are only a limited number of
studies on multiple server vacation models. The multiserver queue with
exponentially distributed vacations is first studied by Levy and Yechiali
[9]. Using partial generating function technique, the system size has been
obtained. Vinod [10] and
Kao and  Narayanan [11] have discussed the M/M/c queue with multiple vacation of the servers
using matrix geometric approach. Further, Chao and Zhao [12] have
investigated the multiserver vacation models of both synchronous (servers
taking the same vacation together) and asynchronous
types and provided some algorithms for computing
the stationary probability distributions and expected performance measures. The M/M/c queue with phase-type synchronous vacations
has been analyzed by Tian and Li [13]. An M/M/c queue with multiple vacations and 1-limited
service has been discussed by Tyagi et al. [14]. Recently,
Krishna Kumar and Pavai Madheswari [15] have analyzed an M/M/c queue with Bernoulli vacation scheduling
service.The study on multiserver queueing system generally
assumes the servers to be homogeneous in which the individual service rates are
the same for all the servers in the system. This assumption may be valid only
when the service process is mechanically or electronically controlled. In a
queueing system with human servers, the above assumptions can hardly be
realized. It is common to observe servers rendering service to identical jobs
at different service rates, that is, the service time distributions may be
different for different servers. As noted earlier, the study of vacation
queueing system incorporates the secondary jobs in the modelling. The analysis
of queueing systems with heterogeneous servers and related vacation models
helps to study the impact of secondary jobs on system performance.Neuts and Takahashi [16] have pointed out that for
the queueing systems with more than two heterogeneous servers, analytical
results are intractable and one may have to use algorithmic approach to study
even the asymptotic behavior of the performance measures like stationary
distribution of system size and tail probability of waiting time of a customer
in the system.Based on the above observations, in this paper, we
consider a vacation queueing system in which customers arrive according to a
Markovian arrival process (MAP) involving only two heterogeneous servers
availing Bernoulli vacations. The service times follow phase-type distributions
(PH distributions), and vacation times of servers follow exponential
distributions with heterogeneous vacation rates.The organization of the paper is as follows. In Section2, after recalling the definition of the MAP used as input process, we describe
the model under investigation. We also study the steady-state probability of
system size and some important and interesting performance measures of the
system in this section. Next, the waiting time distribution and its related
characterizations are discussed in Section 3. Section 4 presents some
illustrative numerical examples of the system performance measures. Conclusions
are given in Section 5.


## 2. Source Characterization and Model Description

In this section, we provide information about the
Markovian arrival process (MAP) which has been assumed for the customers
arrival process. We also describe the model under study.


### 2.1. Markovian Arrival Process

In order to allow bursty type traffic in our system,
we have chosen the input process as the MAP. The MAP is particularly a
tractable point process which is in general nonrenewal and which lends itself
very well to modelling bursty arrival processes commonly arising in
communications (see [17]). Further, the MAP has made it
much easier to develop numerically tractable queueing models which take
correlation into account (see [18, 19]). The
MAP is a rich class of processes which includes the phase-type renewal process
and the Markov-modulated Poisson process as special cases.An MAP can be considered
as a Markov process{N(t),J(t)} on the state space {(i,j);i≥0,1≤j≤l} with an infinitesimal generator Q∗ having the structure(2.1)Q∗=[D0D100⋯0D0D10⋯00D0D1⋯⋮⋮⋮⋮⋱],where D0 and D1 are l×l matrices, D0 has negative diagonal elements and nonnegative
off-diagonal elements, D1 is nonnegative, and (D0+D1)el=0,
where el is an l-dimensional column vector of ones. An arrival
process can be associated with this Markov process as follows. An arrival
occurs whenever there is a state transition into a state corresponding to a D1 block, and there is no arrival otherwise.
Here, N(t)=i represents the number of arrivals in (0,t),
and J(t)=j represents an axillary state or phase
variable. Let η be the stationary probability vector of the
generator D=D0+D1.
That is, η is the unique vector satisfying η(D0+D1)=0 and ηel=1. The fundamental arrival rate of this process
is given by δ=ηD1el. The constant δ is the expected number of arrivals per unit
time in the stationary version of the MAP.


### 2.2. Model Description and Analysis

Consider a two-server vacation queueing system in
which the service time distributions of the servers are not identical.
Customers arrive singly, according to MAP, to an infinite waiting space and
form a single waiting line. Customers are served under the
first-come-first-served (FCFS) discipline. There are two heterogeneous servers.
The service times of server-1 and server-2 are assumed to be phase-type
distributions (PH-distributions) PH(1) and PH(2) with representations(α,S) of order m with Sem=−S0 and (β,T) of order n with Ten=−T0,
respectively. We follow matrix formalism of PH-distributions as represented by
Neuts [20]. The servers take Bernoulli vacation scheduling service as
described by Keilson and Servi [3], that is, after each service completion,
the server-i(i=1,2)   takes a vacation with probability pi and with probability qi=1−pi,
it starts serving the next customer, if any, in the system. If the system is
empty, the servers always take vacations. At the end of a vacation period,
service commences if a customer is present in the queue. Otherwise, the server
takes another vacation immediately and continues in the same manner until it
finds at least one customer waiting upon returning from a vacation (multiple
vacations). This process holds good for both servers 1 and 2.The length of vacations' duration{Vi,r;r=1,2,3,…} of the two servers is assumed to be
independent and identically distributed exponential random variables with
parameters, θi for i=1,2,
and is independent of the length of the service times and the arrival process.
The Bernoulli vacation scheduling service queueing model with heterogeneous
servers under consideration can be formulated as a continuous time Markov chain
(CTMC). By appropriately keeping track of the various states, such as the
number of customers in the system, the phase of the arrival process, the phases
of the service processes of server-1 and server-2, and the status of the
server-1 and server-2, the state space of the Markov chain describing the model
is given as follows.The set of states{(k,0,j0);k≥0;1≤j0≤l} represents that there are k customers in the system, both servers are on
vacation and the phase of the arrival process is j0; the set of states {(k,1,j0,j1);k≥1;1≤j0≤l;1≤j1≤m}  indicates that there are k customers in the system, server-1 is busy in
the system serving a customer in phase j1 while server-2 is on vacation, and j0 represents the phase of the arrival process;
the set of states {(k,2,j0,j2);k≥1;1≤j0≤l;1≤j2≤n}  indicates that there are k customers in the system, server-2 is busy in
the system serving a customer in phase j2 while server-1 is on vacation, and the arrival
process is in phase j0; the set of states {(k,3,j0,j1,j2);k≥2;1≤j0≤l;1≤j1≤m;1≤j2≤n} represents that there are k customers in the system, both servers 1 and 2
are busy in the system serving the customers in phases j1 and j2,
respectively, and the arrival process is in phase j0.We define levels0,1,2,…,k,… as the set of states:(2.2)0={(0,j0);1≤j0≤l},1={(1,0,j0)∪(1,1,j0,j1)∪(1,2,j0,j2);1≤j0≤l;1≤j1≤m;1≤j2≤n},k={(k,0,j0)∪(k,1,j0,j1)∪(k,2,j0,j2)∪(k,3,j0,j1,j2);k≥2;1≤j0≤l;1≤j1≤m;1≤j2≤n},where the elements of the sets
are arranged in lexicographical order.In the sequel, we use the following notations.en: a column
vector of order n×1 with all its elements equal to 1.e=el+lm+ln+lmn: a column
vector of order (l+lm+ln+lmn)×1 with all its elements equal to 1.el+lm+ln(l): a column
vector of order (l+lm+ln)×1 with the 1st l elements equal to 1, and other elements are
zeros.el+lm+ln(lm): a column
vector of order (l+lm+ln)×1 with the (l+1)st to (l+lm)th elements equal to 1, and other elements are
zeros.el+lm+ln(ln): a column
vector of order (l+lm+ln)×1 with (l+lm+1)st to (l+lm+ln)th elements equal to 1, and other elements are
zeros.el+lm+ln+lmn(l): a column
vector of order (l+lm+ln+lmn)×1 with the 1st to l elements equal to 1, and other elements are
zeros.el+lm+ln+lmn(lm): a column
vector of order (l+lm+ln+lmn)×1 with the (l+1)st to (l+lm)th elements equal to 1, and other elements are
zeros.el+lm+ln+lmn(ln): a column
vector of order (l+lm+ln+lmn)×1 with (l+lm+1)st to (l+lm+ln)th elements equal to 1, and other elements are
zeros.el+lm+ln+lmn(lmn): a column
vector of order (l+lm+ln+lmn)×1 with (l+lm+ln+1)st to (l+lm+ln+lmn)th elements equal to 1, and other elements are
zeros.Using
elementary arguments, the infinite-state Markov chain for the model under study
has a transition rate matrixQ which has a block-tridiagonal structure given
by(2.3)Q=[B00B01B10B11B12B21A1A0A2A1A0A2A1A0⋱⋱⋱].The entries of Q are given by the following block matrices. The
boundary matrices are defined by(2.4)B00=D0,B01=[D1,0,0],B10=[0,S0⊗Il,T0⊗Il]T,B11=[D0−(θ1+θ2)Ilθ1α⊗Ilθ2β⊗Il0S⊕D0000T⊕D0],B12=[D10000Im⊗D10000In⊗D10],B21=[000p1S0⊗Ilq1S0α⊗Il0p2T0⊗Il0q2T0β⊗Il0T0⊗(Im⊗Il)In⊗(S0⊗Il)].The square matrices A0,A1,
and A2 are of order l+lm+ln+lmn and are given by(2.5)A0=[D10000Im⊗D10000In⊗D10000In⊗Im⊗D1],A1=[D0−(θ1+θ2)Ilθ1α⊗Ilθ2β⊗Il00(S−θ2Im)⊕D00θ2β⊗(Im⊗Il)00(T−θ1In)⊕D0In⊗(θ1α⊗Il)000(T⊕S)⊕D0],A2=[0000p1S0⊗Ilq1S0α⊗Il00p2T0⊗Il0q2T0β⊗Il00p2T0⊗(Im⊗Il)In⊗(p1S0⊗Il)(q2T0β⊕q1S0α)⊗Il],where ⊗ and ⊕ are the Kronecker product and Kronecker sum,
respectively (see [21]).We now derive the condition for the system to reach
steady state. To accomplish this, we defineA=A0+A1+A2. Then, the matrix A can be written as (2.6)A=[D−(θ1+θ2)Ilθ1α⊗Ilθ2β⊗Il0p1S0⊗Il(S+q1S0α−θ2Im)⊕D0θ2β⊗(Im⊗Il)p2T0⊗Il0(T+q2T0β−θ1In)⊕DIn⊗(θ1α⊗Il)0p2T0⊗(Im⊗Il)In⊗(p1S0⊗Il)(T+q2T0β)⊕(S+q1S0α)⊕D], where D=D0+D1.It is clear that the order of the square matrixA is l+lm+ln+lmn,
and it is an irreducible infinitesimal generator matrix  [20,
page 82],
and so there exists 1×(l+lm+ln+lmn) stationary probability vector π of A satisfying πA=0 and πe=1. The vector π is denoted by π=(π(0),π(1),π(2),π(3)) whose components are(2.7)π(0)=(π(k,0,1),π(k,0,2),…,π(k,0,j0),…,π(k,0,l))fork≥0,π(1)=(π(k,1,1),π(k,2,1),…,π(k,j0,j1),…,π(k,l,m))fork≥1,π(2)=(π(k,1,1),π(k,2,1),…,π(k,j0,j2),…,π(k,l,n))fork≥1,π(3)=π(k,1,1,1),π(k,2,1,1),…,π(k,j0,j1,j2),…,π(k,l,m,n)fork≥2.Here, π(0) is the stationary probability vector when both
servers are on vacation, π(1) is the stationary probability vector when
server-1 is busy and server-2 is on vacation, π(2) is the stationary probability vector when
server-2 is busy and server-1 is on vacation and π(3) is the stationary probability vector when both
servers are busy. Further, π(k,0,j0) is the stationary probability that there are k(k≥0) customers in the system, both servers are on
vacation, and the underlying arrival process MAP is in phase j0(1≤j0≤l);π(k,j0,j1)   is the stationary probability that there are k(k≥1) customers in the system with the underlying
arrival process MAP in phase j0(1≤j0≤l), the server-1 is busy serving a customer with
the underlying service process PH(1) in phase j1(1≤j1≤m),
and server-2 is on vacation; π(k,j0,j2) is the stationary probability that there are k(k≥1) customers in the system with the underlying
arrival process MAP in phase j0(1≤j0≤l),
server-2 is busy serving a customer with the underlying service process PH(2)
in phase j2(1≤j2≤n),
and server-1 is on vacation. Finally, π(k,j0,j1,j2) is the stationary probability that there are k(k≥2) customers in the system with the underlying
arrival process MAP in phase j0(1≤j0≤l), both server-1 and server-2 are busy serving
customers with the underlying service processes PH(1) in phase j1(1≤j1≤m) and PH(2) in phase j2(1≤j2≤n), respectively.As the Markov process has the QBD structure, it is
well known [20, page 83] that the standard drift condition(2.8)πA0e<πA2eis the necessary and sufficient
condition for the stability of a QBD process.After some
algebraic manipulation, the stability condition turns out to be(2.9)π(0)D1el+π(1)(em⊗D1el)+π(2)(en⊗D1el)+π(3)(enm⊗D1el)<π(1)(S0⊗el)+π(2)(T0⊗el)+π(3)[(T0⊗em)⊕(en⊗S0)]⊗el.Remark 2.1.
As the LHS of (2.9) is the rate
of flow into the system, and RHS of (2.9) is the maximum rate of flow out of
the system, (2.9) should be a necessary and sufficient condition for positive
recurrence.Under stability condition (2.9) of the system, there
exists the steady-state probability vector X satisfying
XQ=0,Xe∞=1. The stationary probability vector X, partitioned as X=(X(0),X(1),X(2),…),
is given by(2.10)X(0)B00+X(1)B10=0,(2.11)X(0)B01+X(1)B11+X(2)B21=0,(2.12)X(1)B12+X(2)(A1+RA2)=0,(2.13)X(k)=X(2)Rk−2,k=3,4,5,…and by the normalizing equation(2.14)X(0)el+X(1)el+lm+ln+X(2)(I−R)−1el+lm+ln+lmn=1,where(2.15)X(0)=(x(0,0,1),x(0,0,2),…,x(0,0,j0),…,x(0,0,l)),X(1)=(x(1,0,1),x(1,0,2),…,x(1,0,j0),…,x(1,0,l),x(1,1,1,1),x(1,1,2,1),…,x(1,1,j0,j1),…,x(1,1,l,m),x(1,2,1,1),x(1,2,2,1),…,x(1,2,j0,j2),…,x(1,2,l,n)),and for k≥2,(2.16)X(k)=(x(k,0,1),x(k,0,2),…,x(k,0,j0),…,x(k,0,l),x(k,1,1,1),x(k,1,2,1),…,x(k,1,j0,j1),…,x(k,1,l,m),x(k,2,1,1),x(k,2,2,1),…,x(k,2,j0,j2),…,x(k,2,l,n),x(k,3,1,1,1),x(k,3,2,1,1),…,x(k,3,j0,j1,j2),…,x(k,3,l,m,n)).Here, x(k,0,j0) refers to the joint probability that there are k(k≥0) customers in the system, both servers are on
vacation and j0(1≤j0≤l) corresponds to the phase of the arrival
process; x(k,1,j0,j1) refers to the joint probability that there are k(k≥1) customers in the system, server-1 is busy
serving a customer, server-2 is on vacation, j0(1≤j0≤l) corresponds to the phase of the arrival
process, and j1(1≤j1≤m) corresponds to the phase of the service
process PH(1) provided by server-1; x(k,2,j0,j2) refers to the joint probability that there are k(k≥1) customers in the system, server-2 is busy
serving a customer, server-1 is on vacation, j0(1≤j0≤l) corresponds to the phase of the arrival
process, and j2(1≤j2≤n) corresponds to the phase of the service
process PH(2) provided by server-2; x(k,3,j0,j1,j2) refers to the joint probability that there are k(k≥2) customers in the system, both servers are busy
serving customers, j0(1≤j0≤l) corresponds to the phase of the arrival
process, j1(1≤j1≤m) and j2(1≤j2≤n) correspond to phases of the underlying service
processes PH(1) and PH(2) provided by server-1 and server-2, respectively. I is the identity matrix of order l+lm+ln+lmn,
and the matrix R is the minimal nonnegative solution with
spectral radius less than 1, that is, Sp(R)<1 of the matrix quadratic equation  [20,
pages 82-83]:(2.17)R2A2+RA1+A0=0.Since the system is stable, and
the square matrices
A0,A1,
and A2 are of order l+lm+ln+lmn,R is also a square matrix of order l+lm+ln+lmn and is obtained from the above matrix
quadratic equation and from the following relation:(2.18)RA2e=A0e.
Equation
(2.18) implies that the rate of transition from a state with k customers to a state with k+1 matches the transition rate from k to k−1.The matrixR is approximated by the following
iterations: (2.19)R(0)=0,R(n+1)=−A0A1−1−R2(n)A2A1−1,forn≥0.The values ofR will converge, since −A1−1 and (A0+R2A2) are positive. Hence, after each iteration, the
elements of R will increase monotonically. Iteration will be
continued until maxi,j[Rij(n+1)−Rij(n)]<ϵ is satisfied, where R(n) is the value of R in the nth iteration, and ϵ is the degree of accuracy required. The
accuracy may be checked by (2.18) with ϵ=10−12 [20].The boundary probability vectorsX(0),X(1),X(2) and the probability vectors X(k),k≥3,
can be obtained form (2.10) to (2.14). These steady-state joint probability
vectors are then used to find the following system performance measures.


### 2.3. Performance Measures

We will list some important performance measures which
are used to bring out the qualitative behavior of the queueing model under
study.(1)
The mean and second
moments of the number of customers in the system
can be obtained exactly as(2.20)E(N)=X(1)el+lm+ln+X(2)[2(I−R)−1+R(I−R)−2]e,E(N2)=X(1)el+lm+ln+4X(2)e−X(2)[(I−R)−1+(I−R)−2+2(I−R)−3−4I]e,where N is the system size at an arbitrary time. The
variance of the system can also be found.(2)
The probability that no customer in the system
and both servers are on vacation is given by(2.21)P0=X(0)el.(3)
The probability that both the servers are on
vacation is given as(2.22)V0=X(0)el+X(1)el+lm+ln(l)+X2(I−R)−1el+lm+ln+lmn(l).(4)
The probability that server-1 is busy serving
a customer and server-2 on vacation is given by(2.23)P1=X(1)el+lm+ln(lm)+X(2)(I−R)−1el+lm+ln+lmn(lm).(5)
The probability that server-2 is busy serving
a customer and server-1 on vacation is given as(2.24)P2=X(1)el+lm+ln(ln)+X(2)(I−R)−1el+lm+ln+lmn(ln).(6)
The probability that both servers are busy is
obtained as(2.25)P12=X(2)(I−R)−1el+lm+ln+lmn(lmn).(7)
The mean number of customersE(NV) present in the system when both the servers
are on vacation is given as(2.26)E(NV)=X(1)el+lm+ln(l)+X(2)[2(I−R)−1+R(I−R)−2]el+lm+ln+lmn(l).(8)
The mean number of customersE(NB) present in the system when both the servers
are busy serving customers is given as(2.27)E(NB)=X(2)[2(I−R)−1+R(I−R)−2]el+lm+ln+lmn(lmn).(9)
The mean number of customersE(N1) present in the system when server-1 is busy
and server-2 on vacation is given as(2.28)E(N1)=X(1)el+lm+ln(lm)+X(2)[2(I−R)−1+R(I−R)−2]el+lm+ln+lmn(lm).(10)
The mean number of customersE(N2) present in the system when server-1 on
vacation and server-2 being busy is obtained as(2.29)E(N2)=X(1)el+lm+ln(ln)+X(2)[(I−R)−1+2(I−R)−2]el+lm+ln+lmn(ln).


## 2.1. Markovian Arrival Process

In order to allow bursty type traffic in our system,
we have chosen the input process as the MAP. The MAP is particularly a
tractable point process which is in general nonrenewal and which lends itself
very well to modelling bursty arrival processes commonly arising in
communications (see [17]). Further, the MAP has made it
much easier to develop numerically tractable queueing models which take
correlation into account (see [18, 19]). The
MAP is a rich class of processes which includes the phase-type renewal process
and the Markov-modulated Poisson process as special cases.An MAP can be considered
as a Markov process{N(t),J(t)} on the state space {(i,j);i≥0,1≤j≤l} with an infinitesimal generator Q∗ having the structure(2.1)Q∗=[D0D100⋯0D0D10⋯00D0D1⋯⋮⋮⋮⋮⋱],where D0 and D1 are l×l matrices, D0 has negative diagonal elements and nonnegative
off-diagonal elements, D1 is nonnegative, and (D0+D1)el=0,
where el is an l-dimensional column vector of ones. An arrival
process can be associated with this Markov process as follows. An arrival
occurs whenever there is a state transition into a state corresponding to a D1 block, and there is no arrival otherwise.
Here, N(t)=i represents the number of arrivals in (0,t),
and J(t)=j represents an axillary state or phase
variable. Let η be the stationary probability vector of the
generator D=D0+D1.
That is, η is the unique vector satisfying η(D0+D1)=0 and ηel=1. The fundamental arrival rate of this process
is given by δ=ηD1el. The constant δ is the expected number of arrivals per unit
time in the stationary version of the MAP.


## 2.2. Model Description and Analysis

Consider a two-server vacation queueing system in
which the service time distributions of the servers are not identical.
Customers arrive singly, according to MAP, to an infinite waiting space and
form a single waiting line. Customers are served under the
first-come-first-served (FCFS) discipline. There are two heterogeneous servers.
The service times of server-1 and server-2 are assumed to be phase-type
distributions (PH-distributions) PH(1) and PH(2) with representations(α,S) of order m with Sem=−S0 and (β,T) of order n with Ten=−T0,
respectively. We follow matrix formalism of PH-distributions as represented by
Neuts [20]. The servers take Bernoulli vacation scheduling service as
described by Keilson and Servi [3], that is, after each service completion,
the server-i(i=1,2)   takes a vacation with probability pi and with probability qi=1−pi,
it starts serving the next customer, if any, in the system. If the system is
empty, the servers always take vacations. At the end of a vacation period,
service commences if a customer is present in the queue. Otherwise, the server
takes another vacation immediately and continues in the same manner until it
finds at least one customer waiting upon returning from a vacation (multiple
vacations). This process holds good for both servers 1 and 2.The length of vacations' duration{Vi,r;r=1,2,3,…} of the two servers is assumed to be
independent and identically distributed exponential random variables with
parameters, θi for i=1,2,
and is independent of the length of the service times and the arrival process.
The Bernoulli vacation scheduling service queueing model with heterogeneous
servers under consideration can be formulated as a continuous time Markov chain
(CTMC). By appropriately keeping track of the various states, such as the
number of customers in the system, the phase of the arrival process, the phases
of the service processes of server-1 and server-2, and the status of the
server-1 and server-2, the state space of the Markov chain describing the model
is given as follows.The set of states{(k,0,j0);k≥0;1≤j0≤l} represents that there are k customers in the system, both servers are on
vacation and the phase of the arrival process is j0; the set of states {(k,1,j0,j1);k≥1;1≤j0≤l;1≤j1≤m}  indicates that there are k customers in the system, server-1 is busy in
the system serving a customer in phase j1 while server-2 is on vacation, and j0 represents the phase of the arrival process;
the set of states {(k,2,j0,j2);k≥1;1≤j0≤l;1≤j2≤n}  indicates that there are k customers in the system, server-2 is busy in
the system serving a customer in phase j2 while server-1 is on vacation, and the arrival
process is in phase j0; the set of states {(k,3,j0,j1,j2);k≥2;1≤j0≤l;1≤j1≤m;1≤j2≤n} represents that there are k customers in the system, both servers 1 and 2
are busy in the system serving the customers in phases j1 and j2,
respectively, and the arrival process is in phase j0.We define levels0,1,2,…,k,… as the set of states:(2.2)0={(0,j0);1≤j0≤l},1={(1,0,j0)∪(1,1,j0,j1)∪(1,2,j0,j2);1≤j0≤l;1≤j1≤m;1≤j2≤n},k={(k,0,j0)∪(k,1,j0,j1)∪(k,2,j0,j2)∪(k,3,j0,j1,j2);k≥2;1≤j0≤l;1≤j1≤m;1≤j2≤n},where the elements of the sets
are arranged in lexicographical order.In the sequel, we use the following notations.en: a column
vector of order n×1 with all its elements equal to 1.e=el+lm+ln+lmn: a column
vector of order (l+lm+ln+lmn)×1 with all its elements equal to 1.el+lm+ln(l): a column
vector of order (l+lm+ln)×1 with the 1st l elements equal to 1, and other elements are
zeros.el+lm+ln(lm): a column
vector of order (l+lm+ln)×1 with the (l+1)st to (l+lm)th elements equal to 1, and other elements are
zeros.el+lm+ln(ln): a column
vector of order (l+lm+ln)×1 with (l+lm+1)st to (l+lm+ln)th elements equal to 1, and other elements are
zeros.el+lm+ln+lmn(l): a column
vector of order (l+lm+ln+lmn)×1 with the 1st to l elements equal to 1, and other elements are
zeros.el+lm+ln+lmn(lm): a column
vector of order (l+lm+ln+lmn)×1 with the (l+1)st to (l+lm)th elements equal to 1, and other elements are
zeros.el+lm+ln+lmn(ln): a column
vector of order (l+lm+ln+lmn)×1 with (l+lm+1)st to (l+lm+ln)th elements equal to 1, and other elements are
zeros.el+lm+ln+lmn(lmn): a column
vector of order (l+lm+ln+lmn)×1 with (l+lm+ln+1)st to (l+lm+ln+lmn)th elements equal to 1, and other elements are
zeros.Using
elementary arguments, the infinite-state Markov chain for the model under study
has a transition rate matrixQ which has a block-tridiagonal structure given
by(2.3)Q=[B00B01B10B11B12B21A1A0A2A1A0A2A1A0⋱⋱⋱].The entries of Q are given by the following block matrices. The
boundary matrices are defined by(2.4)B00=D0,B01=[D1,0,0],B10=[0,S0⊗Il,T0⊗Il]T,B11=[D0−(θ1+θ2)Ilθ1α⊗Ilθ2β⊗Il0S⊕D0000T⊕D0],B12=[D10000Im⊗D10000In⊗D10],B21=[000p1S0⊗Ilq1S0α⊗Il0p2T0⊗Il0q2T0β⊗Il0T0⊗(Im⊗Il)In⊗(S0⊗Il)].The square matrices A0,A1,
and A2 are of order l+lm+ln+lmn and are given by(2.5)A0=[D10000Im⊗D10000In⊗D10000In⊗Im⊗D1],A1=[D0−(θ1+θ2)Ilθ1α⊗Ilθ2β⊗Il00(S−θ2Im)⊕D00θ2β⊗(Im⊗Il)00(T−θ1In)⊕D0In⊗(θ1α⊗Il)000(T⊕S)⊕D0],A2=[0000p1S0⊗Ilq1S0α⊗Il00p2T0⊗Il0q2T0β⊗Il00p2T0⊗(Im⊗Il)In⊗(p1S0⊗Il)(q2T0β⊕q1S0α)⊗Il],where ⊗ and ⊕ are the Kronecker product and Kronecker sum,
respectively (see [21]).We now derive the condition for the system to reach
steady state. To accomplish this, we defineA=A0+A1+A2. Then, the matrix A can be written as (2.6)A=[D−(θ1+θ2)Ilθ1α⊗Ilθ2β⊗Il0p1S0⊗Il(S+q1S0α−θ2Im)⊕D0θ2β⊗(Im⊗Il)p2T0⊗Il0(T+q2T0β−θ1In)⊕DIn⊗(θ1α⊗Il)0p2T0⊗(Im⊗Il)In⊗(p1S0⊗Il)(T+q2T0β)⊕(S+q1S0α)⊕D], where D=D0+D1.It is clear that the order of the square matrixA is l+lm+ln+lmn,
and it is an irreducible infinitesimal generator matrix  [20,
page 82],
and so there exists 1×(l+lm+ln+lmn) stationary probability vector π of A satisfying πA=0 and πe=1. The vector π is denoted by π=(π(0),π(1),π(2),π(3)) whose components are(2.7)π(0)=(π(k,0,1),π(k,0,2),…,π(k,0,j0),…,π(k,0,l))fork≥0,π(1)=(π(k,1,1),π(k,2,1),…,π(k,j0,j1),…,π(k,l,m))fork≥1,π(2)=(π(k,1,1),π(k,2,1),…,π(k,j0,j2),…,π(k,l,n))fork≥1,π(3)=π(k,1,1,1),π(k,2,1,1),…,π(k,j0,j1,j2),…,π(k,l,m,n)fork≥2.Here, π(0) is the stationary probability vector when both
servers are on vacation, π(1) is the stationary probability vector when
server-1 is busy and server-2 is on vacation, π(2) is the stationary probability vector when
server-2 is busy and server-1 is on vacation and π(3) is the stationary probability vector when both
servers are busy. Further, π(k,0,j0) is the stationary probability that there are k(k≥0) customers in the system, both servers are on
vacation, and the underlying arrival process MAP is in phase j0(1≤j0≤l);π(k,j0,j1)   is the stationary probability that there are k(k≥1) customers in the system with the underlying
arrival process MAP in phase j0(1≤j0≤l), the server-1 is busy serving a customer with
the underlying service process PH(1) in phase j1(1≤j1≤m),
and server-2 is on vacation; π(k,j0,j2) is the stationary probability that there are k(k≥1) customers in the system with the underlying
arrival process MAP in phase j0(1≤j0≤l),
server-2 is busy serving a customer with the underlying service process PH(2)
in phase j2(1≤j2≤n),
and server-1 is on vacation. Finally, π(k,j0,j1,j2) is the stationary probability that there are k(k≥2) customers in the system with the underlying
arrival process MAP in phase j0(1≤j0≤l), both server-1 and server-2 are busy serving
customers with the underlying service processes PH(1) in phase j1(1≤j1≤m) and PH(2) in phase j2(1≤j2≤n), respectively.As the Markov process has the QBD structure, it is
well known [20, page 83] that the standard drift condition(2.8)πA0e<πA2eis the necessary and sufficient
condition for the stability of a QBD process.After some
algebraic manipulation, the stability condition turns out to be(2.9)π(0)D1el+π(1)(em⊗D1el)+π(2)(en⊗D1el)+π(3)(enm⊗D1el)<π(1)(S0⊗el)+π(2)(T0⊗el)+π(3)[(T0⊗em)⊕(en⊗S0)]⊗el.Remark 2.1.
As the LHS of (2.9) is the rate
of flow into the system, and RHS of (2.9) is the maximum rate of flow out of
the system, (2.9) should be a necessary and sufficient condition for positive
recurrence.Under stability condition (2.9) of the system, there
exists the steady-state probability vector X satisfying
XQ=0,Xe∞=1. The stationary probability vector X, partitioned as X=(X(0),X(1),X(2),…),
is given by(2.10)X(0)B00+X(1)B10=0,(2.11)X(0)B01+X(1)B11+X(2)B21=0,(2.12)X(1)B12+X(2)(A1+RA2)=0,(2.13)X(k)=X(2)Rk−2,k=3,4,5,…and by the normalizing equation(2.14)X(0)el+X(1)el+lm+ln+X(2)(I−R)−1el+lm+ln+lmn=1,where(2.15)X(0)=(x(0,0,1),x(0,0,2),…,x(0,0,j0),…,x(0,0,l)),X(1)=(x(1,0,1),x(1,0,2),…,x(1,0,j0),…,x(1,0,l),x(1,1,1,1),x(1,1,2,1),…,x(1,1,j0,j1),…,x(1,1,l,m),x(1,2,1,1),x(1,2,2,1),…,x(1,2,j0,j2),…,x(1,2,l,n)),and for k≥2,(2.16)X(k)=(x(k,0,1),x(k,0,2),…,x(k,0,j0),…,x(k,0,l),x(k,1,1,1),x(k,1,2,1),…,x(k,1,j0,j1),…,x(k,1,l,m),x(k,2,1,1),x(k,2,2,1),…,x(k,2,j0,j2),…,x(k,2,l,n),x(k,3,1,1,1),x(k,3,2,1,1),…,x(k,3,j0,j1,j2),…,x(k,3,l,m,n)).Here, x(k,0,j0) refers to the joint probability that there are k(k≥0) customers in the system, both servers are on
vacation and j0(1≤j0≤l) corresponds to the phase of the arrival
process; x(k,1,j0,j1) refers to the joint probability that there are k(k≥1) customers in the system, server-1 is busy
serving a customer, server-2 is on vacation, j0(1≤j0≤l) corresponds to the phase of the arrival
process, and j1(1≤j1≤m) corresponds to the phase of the service
process PH(1) provided by server-1; x(k,2,j0,j2) refers to the joint probability that there are k(k≥1) customers in the system, server-2 is busy
serving a customer, server-1 is on vacation, j0(1≤j0≤l) corresponds to the phase of the arrival
process, and j2(1≤j2≤n) corresponds to the phase of the service
process PH(2) provided by server-2; x(k,3,j0,j1,j2) refers to the joint probability that there are k(k≥2) customers in the system, both servers are busy
serving customers, j0(1≤j0≤l) corresponds to the phase of the arrival
process, j1(1≤j1≤m) and j2(1≤j2≤n) correspond to phases of the underlying service
processes PH(1) and PH(2) provided by server-1 and server-2, respectively. I is the identity matrix of order l+lm+ln+lmn,
and the matrix R is the minimal nonnegative solution with
spectral radius less than 1, that is, Sp(R)<1 of the matrix quadratic equation  [20,
pages 82-83]:(2.17)R2A2+RA1+A0=0.Since the system is stable, and
the square matrices
A0,A1,
and A2 are of order l+lm+ln+lmn,R is also a square matrix of order l+lm+ln+lmn and is obtained from the above matrix
quadratic equation and from the following relation:(2.18)RA2e=A0e.
Equation
(2.18) implies that the rate of transition from a state with k customers to a state with k+1 matches the transition rate from k to k−1.The matrixR is approximated by the following
iterations: (2.19)R(0)=0,R(n+1)=−A0A1−1−R2(n)A2A1−1,forn≥0.The values ofR will converge, since −A1−1 and (A0+R2A2) are positive. Hence, after each iteration, the
elements of R will increase monotonically. Iteration will be
continued until maxi,j[Rij(n+1)−Rij(n)]<ϵ is satisfied, where R(n) is the value of R in the nth iteration, and ϵ is the degree of accuracy required. The
accuracy may be checked by (2.18) with ϵ=10−12 [20].The boundary probability vectorsX(0),X(1),X(2) and the probability vectors X(k),k≥3,
can be obtained form (2.10) to (2.14). These steady-state joint probability
vectors are then used to find the following system performance measures.


## 2.3. Performance Measures

We will list some important performance measures which
are used to bring out the qualitative behavior of the queueing model under
study.(1)
The mean and second
moments of the number of customers in the system
can be obtained exactly as(2.20)E(N)=X(1)el+lm+ln+X(2)[2(I−R)−1+R(I−R)−2]e,E(N2)=X(1)el+lm+ln+4X(2)e−X(2)[(I−R)−1+(I−R)−2+2(I−R)−3−4I]e,where N is the system size at an arbitrary time. The
variance of the system can also be found.(2)
The probability that no customer in the system
and both servers are on vacation is given by(2.21)P0=X(0)el.(3)
The probability that both the servers are on
vacation is given as(2.22)V0=X(0)el+X(1)el+lm+ln(l)+X2(I−R)−1el+lm+ln+lmn(l).(4)
The probability that server-1 is busy serving
a customer and server-2 on vacation is given by(2.23)P1=X(1)el+lm+ln(lm)+X(2)(I−R)−1el+lm+ln+lmn(lm).(5)
The probability that server-2 is busy serving
a customer and server-1 on vacation is given as(2.24)P2=X(1)el+lm+ln(ln)+X(2)(I−R)−1el+lm+ln+lmn(ln).(6)
The probability that both servers are busy is
obtained as(2.25)P12=X(2)(I−R)−1el+lm+ln+lmn(lmn).(7)
The mean number of customersE(NV) present in the system when both the servers
are on vacation is given as(2.26)E(NV)=X(1)el+lm+ln(l)+X(2)[2(I−R)−1+R(I−R)−2]el+lm+ln+lmn(l).(8)
The mean number of customersE(NB) present in the system when both the servers
are busy serving customers is given as(2.27)E(NB)=X(2)[2(I−R)−1+R(I−R)−2]el+lm+ln+lmn(lmn).(9)
The mean number of customersE(N1) present in the system when server-1 is busy
and server-2 on vacation is given as(2.28)E(N1)=X(1)el+lm+ln(lm)+X(2)[2(I−R)−1+R(I−R)−2]el+lm+ln+lmn(lm).(10)
The mean number of customersE(N2) present in the system when server-1 on
vacation and server-2 being busy is obtained as(2.29)E(N2)=X(1)el+lm+ln(ln)+X(2)[(I−R)−1+2(I−R)−2]el+lm+ln+lmn(ln).


## 3. Waiting Time Distribution

We now analyze the waiting time of an arriving customer
in the queue by first-passage time analysis. We
then show how the mean waiting time can be determined.LetW(t),t≥0,
be the distribution function for the waiting time in the queue of an arriving
(tagged) customer, that is, W(t) denotes the probability vector of order 1×mn that an arriving tagged customer has to wait
utmost
t time units until it is served. For the
multiserver queue with Bernoulli vacation scheduling service, we have W(0+)=0,
because an arrival must either wait for a service completion or a vacation
termination of servers. States corresponding to the number of customers
are present in the system {0,1,2,…},
and an absorbing state {∗}
forms the state
space of the CTMC. Thus, the state space of the CTMC is {∗}∪{0,1,2,3,…}.
Note that the customer arrival process is not required, since we are discussing
an FCFS queue discipline, and hence, customers that arrive after the tagged
customer do not have any impact on the waiting time of the tagged customer.
Therefore, the absorbing state {∗} is a vector of order 1×mn given by ∗=((∗,1,1),(∗,2,1),…,(∗,j1,j2),…(∗,m,n)), level 0 has the single component (0,0), level 1 is a vector of order 1×(1+m+n) given by(3.1)1={(1,0),(1,1,1),(1,1,2),…,(1,1,j1),…,(1,1,m),(1,2,1),(1,2,2),…,(1,2,j2),…,(1,2,n)},and levels i≥2 are vectors of order 1×(1+m+n+mn) given by(3.2)i={(i,0),(i,1,1),(i,1,2),…,(i,1,j1),…,(i,1,m),(i,2,1),(i,2,2),…,(i,2,j2),…,(i,2,n),(i,3,1,1),(i,3,2,1),…,(i,3,j1,j2),…,(i,3,m,n)},where j1 and j2 are the phases of  the service time
distributions PH(1) and PH(2),
respectively.On entering the absorbing state∗,
a tagged customer starts receiving service. Clearly, this happens at the
arrival of a server either from vacation or after the completion of a service
when the customer is at the head of the queue. The transition rate matrix Q1 for this absorbing Markov chain is given by(3.3)Q1=0*.01C1C2.03□4…*01234⋮[000000…C0E00000…C1E10E1000…C20E21E00…000E2E0…0000E2E⋮⋮⋮⋮⋱⋱],where(3.4)C0=en′⊗θ1α+θ2β⊗em′,C1=[0,en′⊗q1S0α+θ2β⊗emem′,enen′⊗θ1α+q2T0β⊗em′]T,C2=[0,0,0,enen′⊗q1S0α+q2T0β⊗emem′]T,E0=−(θ1+θ2),E10=[0,p1S0,p2T0]T,E1=[−(θ1+θ2)θ1αθ2β0S−θ2Im000T−θ1In],E21=[000p1S0q1S0α0p2T00q2T0β0p2T0⊗ImIn⊗p1S0],E2=[0000p1S0q1S0α00p2T00q2T0β00p2T0⊗ImIn⊗p1S0q2T0β⊕q1S0α],E=[−(θ1+θ2)θ1αθ2β00(S−θ2Im)0θ2β⊗Im00(T−θ1In)In⊗θ1α000T⊕S].It is observed that the customer
arrival rates have not appeared in matrix Q1.To obtain the distribution of waiting timeW(t),t≥0, of the tagged customer, the first step is to
determine the stationary probability distribution of the system's state
immediately after its arrival. This is actually the stationary distribution of
the number of customers in the system as seen by this tagged customer at its
arrival time. Denote by Y(0)=(Y0(0),Y1(0),Y2(0),…) the probability distribution which can be
obtained from X=(X(0),X(1),X(2),…) by a standard method, that is, Y(0) can be interpreted as a conditional
probability distribution of the system's state conditioned on the occurrence of
the tagged customer arrival. Due to the Markovian property of the arrival process,
it is seen that the arrival-stationary probability distribution of the number
of customers in the system is given by(3.5)Y0(0)=X(0)D1elδ,Y1(0)=X(1)(Il+lm+ln⊗D1elδ),Yk(0)=X(k)(Il+lm+ln+lmn⊗D1elδ)fork≥2,where δ is the fundamental arrival rate of the MAP as
given in Section 2.1.Now we defineY(t)=(Y∗(t),Y0(t),Y1(t),…), where Yi(t) is a row vector of order 1×(1+m+n+mn),
when   i≥2,Y0(t) is of order 1×1 and Y1(t) is a row vector of order 1×(1+m+n),
and its elements represent the probability that at time t, the CTMC with generator Q1 is in the respective state of level i. Clearly, Y∗(t) gives the probability that the tagged customer
is in the absorbing state at time t. Hence, the vector waiting time distribution is W(t)=Y∗(t) for t≥0. In finding the waiting time distribution of
the tagged customer at arrival time, it is assumed that the process starts with
initial probability vector Y(0)=(Y0(0),Y1(0),Y2(0),…).The differential equationY′(t)=Y(t)Q1 for t≥0 reduces to(3.6)Y∗′(t)=∑k=02Yk(t)Ck,Y0′(t)=Y0(t)E0+Y1(t)E10,Y1′(t)=Y1(t)E1+Y2(t)E21,Yk′(t)=Yk(t)E+Yk+1(t)E2,k≥2,where the prime denotes the
derivative of the function concerned with respect to t.The tagged customer at arrival time finds the system
in levelk with probability Yk(0),
for k≥2, the Laplace-Stieltjes transform (LST) of the
first passage time to level 2 is given by the row vector χ(s).As in [20], we get(3.7)χ(s)=∑i=2∞Yi(0)[(sI−E)−1E2]i−2.LetΦ(i,s) be the LST of the absorbing time to the state {∗} given that the process starts from level i=0,1,2. On the basis of Q1, we can write the following relations for the
matrices Φ(i,s):  (3.8)Φ1×mn(0,s)=(sI−E0)−1C0,(3.9)Φ(1+m+n)×mn(1,s)=(sI−E1)−1E10Φ(0,s)+(sI−E1)−1C1,(3.10)Φ(1+m+n+mn)×mn(2,s)=(sI−E)−1E21Φ(1,s)+(sI−E)−1C2.Finally, it can be seen that the
LST W(s) for the waiting time distribution is given by(3.11)W(s)=Y0(0)Φ(0,s)+Y1(0)Φ(1,s)+χ(s)Φ(2,s).


### 3.1. Mean Waiting Time

The mean waiting time of an arriving customer is
computed fromW(s)(3.12)E(W)=−Y0(0)Φ′(0,0)emn−Y1(0)Φ′(1,0)emn−χ′(0)e1+m+n+mn−χ(0)Φ(2,0)emn.The first two terms give the
mean time to reach an absorbing state {∗} by the tagged customer if the system is in a
level ≤1. On its arrival, the third and fourth terms
represent the time to reach the absorbing state {∗} if the system is in a level ≥2.To compute the mean waiting time of the tagged
customer, we must calculate the value of each term in (3.12). Differentiating
(3.8) with respect to s and setting s=0, we get(3.13)Φ(0,0)=(−1)(−E0)−1C0.Similarly, differentiating (3.9)
and (3.10) with respect to s and setting s=0,
we obtain(3.14)Φ′(1,0)=(−1)(−E1)−2E10Φ(0,0)+(−E1)−1E10Φ′(0,0)+(−1)(−E1)−2C1,(3.15)Φ′(2,0)=(−1)(−E)−2E21Φ(1,0)+(−E)−1E21Φ′(1,0)+(−1)(−E)−2C2.Thus, formulae (3.13)–(3.15)
permit the recursive computation of the matrices Φ′(i,0),0≤i≤2. Using (3.13) to (3.15) and absorbing the
initial condition Y(0)=(Y0(0),Y1(0),Y2(0),…), we can compute the first two terms of (3.12).The value ofχ(0)=∑i=2∞Yi(0)Ui−2, where U=(−E)−1E2,
is obtained by substituting s=0 in (3.7), and it needs to be evaluated
numerically. Since Ue1+m+n+mn=e1+m+n+mn,
owing to the relation E2e1+m+n+mn+Ee1+m+n+mn=0,
we have that χ(0)e1+m+n+mn=1−Y0(0)−Y1(0)e1+m+n. The value of χ(0)e1+m+n+mn can also be used, as mentioned in
[11], to evaluate an approximate value of χ(0) by finite summation. Using (3.13) and
(3.14), we
get the value of Φ′(2,0), for the fourth term of (3.12).To compute the third term of (3.12), differentiating
(3.7) with respect to s and setting s=0,
we obtain(3.16)χ′(0)=−∑i=1∞Y2+i(0)∑j=0i−1Uj(−E)−1Ui−j.Since U is a stochastic matrix, and using the
relationship Ue1+m+n+mn=e1+m+n+mn, it follows that(3.17)−χ′(0)e1+m+n+mn=∑i=1∞Y2+i(0)∑j=0i−1Uj(−E)−1e1+m+n+mn.To obtain the value of −χ′(0)e1+m+n+mn from (3.17), we modify the technique
used by
Kao and  Narayanan [11] and Neuts and Lucantoni
[22]. Now, construct a
stochastic matrix U2 such that I−U+U2 is nonsingular and generalized inverse of (I−U). In cases where U is irreducible, the matrix U2 may be chosen as U2=e1+m+n+mnu0,
where u0 is the invariant probability vector of U,
that is, u0U=u0 and u0e1+m+n+mn=1. This follows from the classical theorem on
finite Markov chains given in the work of
Kemeny and  Snell [23, page 100].Further, the following relation is satisfied owing to
the propertyUU2=U2U=U2:(3.18)∑j=0i−1Uj(I−U+U2)=I−Ui+iU2,fori≥1.Substituting (3.18) in
(3.17)
and  simplifying, we  obtain(3.19)−χ′(0)e1+m+n+mn={Y2(0)(I−R)−1+Y2(0)[(I−R)−2−(I−R)−1]U2−χ(0)}×(I−U−U2)−1(−E)−1e1+m+n+mn.Thus, all four terms of (3.12)
have been computed, and the mean waiting time can be obtained.Hence, we are able to compute the values of
steady-state joint probabilities and mean waiting time using algorithms for
this queueing system with Bernoulli vacation scheduling service.


## 3.1. Mean Waiting Time

The mean waiting time of an arriving customer is
computed fromW(s)(3.12)E(W)=−Y0(0)Φ′(0,0)emn−Y1(0)Φ′(1,0)emn−χ′(0)e1+m+n+mn−χ(0)Φ(2,0)emn.The first two terms give the
mean time to reach an absorbing state {∗} by the tagged customer if the system is in a
level ≤1. On its arrival, the third and fourth terms
represent the time to reach the absorbing state {∗} if the system is in a level ≥2.To compute the mean waiting time of the tagged
customer, we must calculate the value of each term in (3.12). Differentiating
(3.8) with respect to s and setting s=0, we get(3.13)Φ(0,0)=(−1)(−E0)−1C0.Similarly, differentiating (3.9)
and (3.10) with respect to s and setting s=0,
we obtain(3.14)Φ′(1,0)=(−1)(−E1)−2E10Φ(0,0)+(−E1)−1E10Φ′(0,0)+(−1)(−E1)−2C1,(3.15)Φ′(2,0)=(−1)(−E)−2E21Φ(1,0)+(−E)−1E21Φ′(1,0)+(−1)(−E)−2C2.Thus, formulae (3.13)–(3.15)
permit the recursive computation of the matrices Φ′(i,0),0≤i≤2. Using (3.13) to (3.15) and absorbing the
initial condition Y(0)=(Y0(0),Y1(0),Y2(0),…), we can compute the first two terms of (3.12).The value ofχ(0)=∑i=2∞Yi(0)Ui−2, where U=(−E)−1E2,
is obtained by substituting s=0 in (3.7), and it needs to be evaluated
numerically. Since Ue1+m+n+mn=e1+m+n+mn,
owing to the relation E2e1+m+n+mn+Ee1+m+n+mn=0,
we have that χ(0)e1+m+n+mn=1−Y0(0)−Y1(0)e1+m+n. The value of χ(0)e1+m+n+mn can also be used, as mentioned in
[11], to evaluate an approximate value of χ(0) by finite summation. Using (3.13) and
(3.14), we
get the value of Φ′(2,0), for the fourth term of (3.12).To compute the third term of (3.12), differentiating
(3.7) with respect to s and setting s=0,
we obtain(3.16)χ′(0)=−∑i=1∞Y2+i(0)∑j=0i−1Uj(−E)−1Ui−j.Since U is a stochastic matrix, and using the
relationship Ue1+m+n+mn=e1+m+n+mn, it follows that(3.17)−χ′(0)e1+m+n+mn=∑i=1∞Y2+i(0)∑j=0i−1Uj(−E)−1e1+m+n+mn.To obtain the value of −χ′(0)e1+m+n+mn from (3.17), we modify the technique
used by
Kao and  Narayanan [11] and Neuts and Lucantoni
[22]. Now, construct a
stochastic matrix U2 such that I−U+U2 is nonsingular and generalized inverse of (I−U). In cases where U is irreducible, the matrix U2 may be chosen as U2=e1+m+n+mnu0,
where u0 is the invariant probability vector of U,
that is, u0U=u0 and u0e1+m+n+mn=1. This follows from the classical theorem on
finite Markov chains given in the work of
Kemeny and  Snell [23, page 100].Further, the following relation is satisfied owing to
the propertyUU2=U2U=U2:(3.18)∑j=0i−1Uj(I−U+U2)=I−Ui+iU2,fori≥1.Substituting (3.18) in
(3.17)
and  simplifying, we  obtain(3.19)−χ′(0)e1+m+n+mn={Y2(0)(I−R)−1+Y2(0)[(I−R)−2−(I−R)−1]U2−χ(0)}×(I−U−U2)−1(−E)−1e1+m+n+mn.Thus, all four terms of (3.12)
have been computed, and the mean waiting time can be obtained.Hence, we are able to compute the values of
steady-state joint probabilities and mean waiting time using algorithms for
this queueing system with Bernoulli vacation scheduling service.


## 4. Numerical Examples

In this section, we discuss some interesting numerical
examples that qualitatively describe the performance of the queueing system
under investigation. To gain an understanding of the performance measures of
the Bernoulli vacation scheduling service queueing model, we study the effect
of the system parameters on the following
items:(i)
the expected numberE(N) of customers in the system,(ii)
the expected numberE(NB) of customers in the system when both servers
are busy,(iii)
the probabilityP0 of no customers in the system,(iv)
the probabilityP12 that both servers
are busy, and(v)
the mean waiting timeE(W) of an arriving customer.For the arrival process, we consider the MAP input
which is characterized by the matrices:(4.1)D0=[−λλ0−λ],D1=[00λ0].In other words, the
continuous-time Markov chain, which governs the input, has two states. For
various values of λ ranging from 4 to 13, this MAP has the
fundamental rate δ ranging from 2 to 6.5.Next, we consider the phase-type (PH) service time
processes for server-1 and server-2 as(4.2)α=(0.85,0.14,0.01),S=[−200000−20000−0.5],S0=[200200.5],β=(1,0),T=[−20200−20],T0=[020].The average  intensities of the
services of server-1 and server-2 are given by μ1=1/−αS−1e3=31.94 and μ2=1/−βT−1e2=10,
respectively.In Figures1 and 2,
the values of E(N), the mean numbers of customers in the system
and E(NB),
the mean number of customers in the system when both servers being busy are
plotted against the fundamental rate δ for chosen values of μ1,μ2,θ1,θ2,p1,
and p2 satisfying stability condition (2.9).Figure 1
E(N) versus δ for μ1=31.94,μ2=10.Figure 2
E(NB) versus δ for μ1=31.94,μ2=10.By considering higher vacation rates (of order105) in the vacation model under study, we obtain
approximate results for corresponding nonvacation model. By fixing   μ1=31.94,μ2=10,θ1=4,
and θ2=5,
the values of E(N) versus the fundamental rate δ are plotted in Figure 1 for the following cases:(1)
1-limited service policy(p1=p2=1),(2)
Bernoulli vacation scheduling service(p1=0.4,p2=0.5),(3)
exhaustive service policy(p1=p2=0),(4)
with no vacation system.In all the
cases, it is observed that E(N) steadily increases as δ increases and decreases with decreasing values
of p1 and p2. Figure 2 indicates that E(NB),
the mean of the system size when both servers being busy for 1-limited service
policy, Bernoulli vacation scheduling service, and
exhaustive service with multiple vacation grow at a
faster rate than nonvacation system for increasing values of the fundamental
arrival rate δ.In Figure3, the values of P0, the probability that there is no customer in
the system, and both server-1 and server-2 on vacation are plotted against the
fundamental arrival rate δ for the chosen parametric values of the system
satisfying the stability condition (2.9). It is seen that the probability P0 steadily decreases as the values of δ increase, and it decreases for increasing
values of p1 and p2.Figure 3
P0 versus δ for μ1=31.94,μ2=10.In Figure4, we plot the probability P12 that both server-1 and server-2 are busy
versus the fundamental arrival rate δ for the different values of p1 and p2.
It is seen that the probability P12 exhibits the opposite trend to that of the
probability P0 in the sense that it increases with increasing δ as expected. However, P12 decreases for increasing values of p1 and p2.
Moreover, for the case of nonvacation system, the value of P12 is seen to be more than that for any of the
vacation policies under discussion.Figure 4
P12 versus δ for μ1=31.94,μ2=10.The trends of the  average waiting timeE(W) are depicted in Figures 5–7. The computation
of the mean waiting time E(W) of customer at the arrival epoch for the
exhaustive service policy is carried out in accordance with procedure given in
the work of Kao and Narayanan [11] and in the
case of 1-limited service discipline, the approach due to the
work of Tyagi et al. [14] is followed. It is observed from
Figure 5 that E(W) grows in an unbounded fashion for system
with/without vacation for increasing values of δ.
For nonvacation system and exhaustive service discipline (p1=p2=0),
the growth of E(W) is not much faster whereas in the cases of
Bernoulli vacation scheduling service (p1=p2=0.5) and 1-limited service discipline (p1=p2=1), there is a steep increase in E(W) for larger values of δ.Figure 5
E(W) versus δ for μ1=31.94,μ2=10.Figure 6
E(W) versus δ for μ1=31.94,μ2=10.Figure 7
E(W) versus δ for μ1=31.94,μ2=10.Figure6 illustrates the trend of expected waiting
time E(W) of the customer at arrival epoch versus the
fundamental arrival rate δ if server-1 follows Bernoulli vacation
scheduling service and server-2 follows either of the following: (i) 1-limited
service policy, (ii) Bernoulli vacation scheduling, (iii) exhaustive service
discipline, and (iv) no vacation system. In all the cases, the expected waiting
time E(W) increases for increasing values of δ. Finally, Figure 7 exhibits a similar trend
wherein the service disciplines of server-1 and server-2  are interchanged
corresponding to Figure 6.


## 5. Conclusions and Further Research

A queueing system with two heterogeneous servers and
Bernoulli vacation has been presented. Customers arrival pattern is described
by the MAP, and service times have PH distributions. Based on the matrix
geometric method, the stationary queue length distribution, mean system size,
and other system performance measure have been computed. This system subsumes
the 1-limited service discipline and the exhaustive service discipline as
special cases. Moreover, the expected waiting time of the customer at arrival
epoch has been analyzed in detail. Results of numerical experiments giving
insight into behavior of the systems are presented. We expect that the method
of analysis adopted in this paper can be used to discuss other complex queueing
systems such as multiserver retrial queue with Bernoulli vacation
policy.



---

*Source: 396871-2008-12-17.xml*