Transcript M/M/c/N queue with balking and reneging

Analysis of M/M/c/N Queuing System
With Balking, Reneging and Synchronous
Vacations
Dequan Yue
Department of Statistics, College of Sciences
Yanshan University, China
Wuyi Yue
Department of Information Science and Systems
Engineering
Konan University, Japan
Outline
 Introduction
 System Model
 Analysis
1. Steady-state equations
2. Block matrix solution method
3. Steady-state probabilities
4. Special cases
 Conditional Distribution
 Conclusions
Introduction
 Practical background
 Literature review
 Purpose of our research
Practical Background
 Balking and reneging
- Customers who on arrival may not join the queue when
there are many customers waiting ahead of them
- Customers who join the queue may leave the queue
without getting serviced
- A common phenomenon in many practical queuing
situations
- Examples in communication systems , production and
inventory system, air defence system and etc., see, Ancker
and Gafarian (1962), Shawky(2000) and Ke (2007)
Practical Background (cont.)
 Server vacations
-In many real world queuing system, server may become
unavailable for a random period of time
-Server vacations can represent the time when the server is
performing some secondary task
-Single server queuing models with vacations have been
studied by many researchers and applied in many fields
such as communication systems, production and inventory
system, computer networks and etc, see, Doshi(1986,1990),
Takagi(1991) and Tian and Zhang(2006)
-There are a few studies on multi-server vacation queuing
system in the vacation model literature
Literature Review
 Three types of the processes
1. Birth and death (BD) process
2. Quasi birth and death (QBD) process
3. Level-dependent quasi birth and death (LDQBD) process
Literature Review (cont.)
 BD process model
1. M/M/c queue with balking and reneging (MontazerHaghighi et.al. (1986))
-infinite buffer and a constant probability of balking,
2. M/M/c/N queue with balking and reneging (Abou-El-Ata
and Hariri (1992))
-finite buffer and a state-dependent probability of balking ,
In these models, the state processes are classical BD
processes. The steady-state probability have been obtained
by solving the difference equations
Literature Review (cont.)
 QBD process model
1. M/M/c queue with synchronous vacations (Tian et. al.
(1999))
2. M/M/c queue with synchronous vacations of partial
server ( Zhang and Tian (2003))
In these models, the state processes are infinite QBD
processes. The steady-state probability have been obtained
by using matrix geometric solution method (Neuts (1981))
Literature Review (cont.)
 LDQBD process model
-M/M/c /N queue with balking, reneging and server
breakdowns (Wang and Chang (2002))
- M/M/c /N queue with balking, reneging and
synchronous vacation of partial servers (Yue et al.
(2006))
In these models, the state process are finite LDQBD
processes. The closed form expressions for steady-state
probabilities have not been obtained
Purpose of Our Research
 To study an M/M/c/N queue with balking,
reneging and synchronous vacation
 To present a closed form expression for computing
the steady-state probability of the model
 To present a block matrix method for solving a
special queuing model with LDQBD process
 To show that some existing models in the
literature are special cases of our model
System Model
 Customers arrive according to Poisson process with rate 
 Service time is assumed to be exponentially distributed with rate 
 A customer who on arrival finds n customers in the system, either
decides to enter the queue with probability bn or balks with
probability 1  bn
 After joining the queue, a customer reneges if its waiting exceeds a
certain time Tr which is assumed to be exponentially distributed
with rate 
 All the c servers take synchronous vacation when the system is
completely empty. The vacation time is assumed to be
exponentially distributed with rate 
Procedure of Analysis
Step 1. Develop steady-state equations
Step 2. Partition infinitesimal generator and steady-state
probability vector
Step 3. Rewrite steady-state equations in block matrix
form
Step 4. Find solution in block matrix form
Step 5. Compute inversions of some block matrices
Step 6. Find the closed form expressions of steady-state
probabilities
Analysis
 Notation
the number of customers in system at time t
0, servers are taking on vacation at time t
J (t )  
on vacations at time
1, servers are not taking
(0,0),
t
{L(t ), J (t ); t  0} is a Markov process with state space:
L (t )
  {(i, 0) : i  0,1,..., N } {(i,1) : i  1, 2,..., N }
Note: If we label the states in lexicographic order:
(0,0), (1,0), (11), ..., ( N ,0), ( N ,1)
then the Markov process is a level-dependent QBD Process
Analysis (cont.)
 B0

 A1

Q




C0
B1
C1
A2
B2
C2
AN 1
BN 1
AN






CN 1 

BN 
Steady-State Equations
 Notation
Steady-state probabilities:
P1 (n)  lim P( L(t )  n, J (t )  1}
t 
P0 (n)  lim P( L(t )  n, J (t )  0}
t 
 Steady-state equations
 PQ  0

 Pe  1
where P  ( P0 (0), P1 (1),..., P0 ( N ), P1 (1), P1 (2),..., P1 ( N )) is steady-state
probability vector, Q is a generator, and e  (1,1,...,1)T is a
column vector of order (2 N  1)
Block Matrix Solution Method
 Partitioned block structure
 Q11 Q12

Q   0 Q22
Q
 31 0
1 N
Q13  N

Q23  1
Q33  N
N
where
P0  ( P0 (0), P0 (1),..., P0 ( N  1))
P1  ( P1 (1), P1 (2),..., P1 ( N ))
P  ( P0 , P0 ( N ), P1 )
Block Matrix Solution Method (cont.)
 The steady-state equations in block matrix form
P0Q11  PQ
1 31  0,
P0Q12  P0 ( N )Q22  0,
P0Q13  P0 ( N )Q23  PQ
1 33  0,
P0 eN  P0 ( N )  Pe
1 N 1
where eN is a column vector of order
components equal to one
N
with all its
Solution in Block Matrix Form
 Theorem 1.
The segments of the steady-state probability vectors are
given by
P0   P0 ( N )Q22Q121 ,
P1   P0 ( N )(Q23  Q22Q121Q13 )Q331
where
P0 ( N )  {1  Q22Q121eN  (Q23  Q22Q121Q13 )Q331}1
Computing Inverse Matrix
 Notations
ui  bi , i  0,1,2,..., N  1,
vi  i , i  1,2,..., N ,
vi    ui , i  1,2,..., N  1
wi  
  vN , i  N ,
i , i  1,2,..., c
si  
c  (i  c) , i  c  1, c  2,..., N ,
 , i  1,2,..., c  1
ti  
bi , i  c, c  1,..., N  1
Computing Inverse Matrix
 Lemma 1-Inverse of matrix
For
j  1, 2,..., N ,
Q12
the elements of the matrix
cij  0,
i  1, 2,..., j  1,
1
cij 
,
i  j,
u j 1
1
cij  kij
, i  j  1, j  2,..., N
u j 1
Q121
is given by
where k ij are given by the following recursive relations
kij 
wi 1
v
ki 1 j  i 1 ki  2 j ,
ui 1
ui 1
where k jj  1 and k j 1 j  0
i  j  1, j  2,..., N
Computing Inverse Matrix (cont.)
 Explicit expression of k ij
kij   Aj Aj 1...Ai 1 T , i  j  1, j  2,..., N ,
j  1, 2,..., N
where   (1, 0) is a row vector of order 2 and
 wk
 u
k
Ak  
 vk

 uk

1
,

0

k  1, 2,..., N  1
Example 1
 0.9167




1.8333
0.8333


 1.0000 2.2500 0.7500

Q12  

1.5000

2.667
0.6667




2.0000 3.0833 0.5833


2.5000

3.5000
0.5000


 1.0909



2.400
1.2000


 5.7455

3.6000
1.3333
1
Q12  

17.5818
11.7000
5.3333
1.5000


 73.2338 49.5000 23.6190 7.9386 1.7143



 424.7273 288.0000 138.6667 748.000 12.0000 2.0000 
Computing Inverse Matrix (cont.)
 Lemma 2- Inverse of matrix Q
33
For j  1, 2,..., N ,
the elements of matrix
Q331
is given by
 i tk tk 1...t j 1
,
i  1, 2,..., j  1,
 k1
sk sk 1...s j

dij  
j 1 t t
1
k k 1 ...t j 1
 
 , i  j , j  1,..., N
 k 1 sk sk 1...s j s j

0
the empty summation  is defined to be zero.
k 1
Example 2
 3.000 2.000



2.000

4.000
2.000




3.000 4.5000 1.5000
Q33  

4.5000

5.8333
1.3333



6.0000 7.1667 1.1667 


7.5000 7.5000 

 1.0000

 1.0000
 1.0000
Q331  
 1.0000
 1.0000

 1.0000
1.0000 0.6667 0.2222 0.0494 0.0077 

1.5000 1.0000 0.3333 0.0741 0.0115 
1.5000 1.3333 0.4444 0.0988 0.0154 

1.5000 1.3333 0.6667 0.1481 0.0230 
1.5000 1.3333 0.6667 0.3148 0.0490 

1.5000 1.3333 0.6667 0.3148 0.1823 
Steady-state Probabilities
 Theorem 2
The steady-state probabilities are given by
P0 ( j )  
 j 1
,
j  0,1,..., N  1,

1
P0 ( N )   ,

N 1

P1 ( j )   (d Nj   dij  i 1 ),
j  1, 2,..., N
i 1

where
N
N
N 1
j 1
j 1
i 1
  1    j    (d Nj   dij  i 1 ),
vN cN 1 j  wN cN j ,
j  1, 2,..., N  1,
 wN cN N ,
jN
j  
Special Cases
 M/M/c/N queue with balking and reneging
Let
 
and
1,

bn    (1  (n  c  1) N )
,
m

(
n

c

2)

n  0,1,..., c,
n  c, c  1,..., N
then our model becomes the model studied by Abou-EIAtaharir (1992)
Special Cases (cont.)
 M/M/c queue with balking and reneging
Let    and
1,
bn  
 ,
n  0,1,..., c,
n  c, c  1,..., N ,
then our model becomes the model studied by Haghighi et
al. (1986)
 M/M/c queue with synchronous vacation
Let N  ,   0 and bi  1, i  0,1,..., then our model
becomes the model studied by Tian et al. (1999)
Conditional Distribution
 Let Qc represent the conditional queue length given that
all servers are busy, then we have
Theorem 3
The conditional stationary distribution of the queue length
is given by
N 1
P(Qc  j ) 
d N ( j c )   di ( j c )  i 1
N
i 1
N 1
 (d Nj   dij  i 1 )
j c
,
j  0,1,..., N  c
i 1
where d ij and  j are given in Lemma 2 and Theorem 2
Conditional Distributions (cont.)
 Remark 2. Based on Theorem 2, we can obtain some other
performances such as the expected number of customers in
the system and in the queue, etc. However, these
performance have very complex expressions.
Conclusions
 Studied an M/M/c/N queue with balking , reneging and
synchronous vacations
 Presented a block matrix method for solving the steadystate equations
 Presented a closed form expressions for steady-state
probabilities
 Obtained some existing models in the literature as special
cases of our model
 Derived the conditional distributions for the queue length
Thank you very much!