# M

Authors: Bin Sun; Moon Ho Lee; Alexander N. Dudin; Sergey A. Dudin
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We consider a multiserver queueing system with an infinite buffer and two types of customers. The flow of customers is described by two Markovian arrival processes (MAPs). Type 1 customers have absolute priority over type 2 customers. If the arriving type 1 customer encounters all servers busy, but some of them provide service to type 2 customers, service of one type 2 customer is terminated and type 1 customer occupies the released server. To avoid too frequent termination of service of type 2 customers, we suggest reservation of some number of servers for type 1 customers. Type 2 customers, who do not succeed to get a server upon arrival or are knocked out from a server, join the buffer or leave the system forever. During a waiting period in the buffer, type 2 customers can be impatient and may leave the system forever. The ergodicity condition of the system is derived in an analytically tractable form. The stationary distribution of the system states and the main performance measures are calculated. The Laplace-Stieltjes transform of the waiting time distribution of an arbitrary type 2 customer is derived. Numerical examples are presented. The problem of the optimal channel reservation is numerically solved.


---

## Body

## 1. Introduction

Queueing theory is the well recognized mathematical tool for solving the problems of design, capacity planning, performance evaluation, and optimization of many real life objects, especially in telecommunications, manufacturing, computer engineering, and so forth. The relevant literature is huge. The most part of the literature is devoted to queueing systems with homogeneous customers while it is a quite frequent real life situation when arriving customers have different importance to the system and various requirements to the quality of their service. So, an important part of queueing literature is devoted to so called priority queues. In such queues, customers of different types are arranged into several classes enumerated, for example, in descending order of their value (economical, social, etc.) for the system and customers from different classes have different treatment in the system. Customers from the classes having higher priority have preferences to others in access to the servers, if they are available or picking-up from the queue to service.The existing literature concerning the priority queues is also huge. So, to essentially reduce the list of the relevant references, here we will cite only papers devoted to priority queues with a Markovian arrival process (MAP); see, for example, [1, 2]. Such an arrival process is the significant generalization of the stationary Poisson process and is very popular descriptor of the flows of customers in modern real life systems now. In contrast to the stationary Poisson process, which allows fitting of only the average value of interarrival times, theMAP allows fitting of also the variance and high order moments of the distribution of interarrival times and correlation of successive interarrival times. The single-server priority queues with theMAPs or a bit more general marked Markovian arrival process (MMAP) (see, e.g., [3]) were considered, for examples, in [4–8].There are different kinds of priorities provided to important customers. The most well known are preemptive and nonpreemptive priorities. Nonpreemptive priority suggests that an arriving high priority customer cannot interrupt service currently provided to a low priority customer. Nonpreemptive priority plays a role only when a server finishes service and the next customers should start processing at this server. Preemptive priority suggests that an arriving high priority customer interrupts service currently provided to a low priority customer. This low priority customer leaves the server. It can leave the system without service permanently or try to get service later when a server will become available. Its service time may be started from the point of the interruption, from the last check point before the interruption, or from the early beginning with the same or different distribution of the service time.The most popular variant of priority queues assumes existence of only two types of customers. Note that the important special cases of priority queues with a preemptive priority are queues with server breakdowns or interruptions. The breakdowns and interruptions can be interpreted as high level customers whose arrival causes termination of service of a usual (low level) customer. Short review of the recent papers related to this subject can be found in [9] where a multiserver queue with quite involved mechanisms of servers breakdowns and repair is analyzed with emphasis to evaluation of survivability of the system. In [10–12], multiserver queues with nonpreemptive priorities are investigated. Model in [12] assumes self-generation of priorities. In [10], multiserver queue with nonpreemptive priority and impatient customers is investigated. Model in [11] assumes that a decision about admission of a nonpriority customer to the first station of a tandem queue is based on information about the current number of customers at the second station of a tandem.In this paper, we consider a multiserver queue with a preemptive priority. The most close papers in literature are [13, 14]. It is supposed in [13] that there is a finite buffer for the nonpriority customers whose service was interrupted. In [14], it is assumed that the nonpriority customers whose service was interrupted go to orbit and retry for the service later on as the priority customers.It is evident that the preemptive priority is much better comparing to the nonpreemptive priority from the point of view of high priority customers. However, the preemptive priority is much worse comparing to the nonpreemptive one from the point of view of low priority customers and from the point of view of the system resources utilization. Some work already done by a server is wasted when the service interruption occurs. As a trade-off, the discipline with the nonpreemptive priority can be used in combination with reservation of some servers exclusively for the service of priority customers. Queueing systems with nonpreemptive priority and reservation of some servers were considered, for example, in [15–17]. In [15], such a system was used for analysis and optimization of the work of the cell of a mobile communication network. The models considered in [16, 17] are the dual tandem queues.The obvious aim of the proposed combination of the reservation with the non-preemptive priority in [15–17] was the desire to give more advantage to high priority customers comparing to an usual nonpreemptive priority discipline. In our present paper, we propose the combination of a reservation with apreemptive priority. Because the preemptive priority itself gives too much advantage to high priority customers, they do not need an additional reservation of the servers. So, motivation of the discipline considered in this paper is to improve quality of low priority customers by means of decreasing the frequency of service interruptions. This is important because interruptions may be quite offensive for low priority customers and also lead to the waste of the system resources.Related model was analyzed in our recent paper [18]. In that paper, it is assumed that the arriving nonpriority customers are not registered by the system manager and the nonpriority customers who cannot enter the service immediately upon arrival or whose service was interrupted go to some virtual place called as an orbit and retry for the service later on. In this paper, we consider another type of arrival process and also assume that there exists registration of nonpriority customers and they are placed in an infinite buffer if they cannot enter the service immediately upon arrival or are interrupted. This assumption allows us to provide a detailed analysis of waiting time distribution for nonpriority customers while such an analysis is impossible for the system with retrials.The results of analysis presented in our paper can be used for enhancement of operation of many real life systems. Let us briefly mention three of them.(i)
Cognitive radio systems; see, for example, [19–24]: in these systems, the high priority is assigned to the primary, licensed customers and the low priority is assigned to the secondary, unlicensed customers. The secondary customers may occupy the free servers (channels or subchannels), but the service of some secondary customers is terminated if a primary customer arrives and does not see a free server.
(ii)
Contact and call centers; see, for example, [25–34]: in these systems, the high priority is assigned to the more important customers or voice requests and the low priority is assigned to the less important customers, e-mail requests, and work relating to providing a call-back option.
(iii)
Different technical, manufacturing, service systems where, to avoid possible starvation and increase a profit, the servers provide the service to some background or external customers in absence of the primary customers.The rest of the paper is organized as follows. In Section2, the mathematical model is described. Multidimensional Markov chain defining behavior of the system is introduced in Section 3. The infinitesimal generator of this Markov chain is written down there. The ergodicity condition and the stationary distribution of the system states are analyzed in Section 4. The expressions for the main system performance measures are given in Section 5. The Laplace-Stieltjes transform of the waiting time distribution of an arbitrary type 2 customer is derived in Section 6. Section 7 contains some numerical illustrations. Finally, Section 8 concludes the paper.


## 2. Mathematical Model

We consider anN-server queueing model with an infinite buffer and two types of customers. Type 1 customers arrive according to the Markovian arrival flowMAP
1. TheMAP
1 is defined by the underlying process ν
t
,
t
≥
0, which is an irreducible continuous-time Markov chain with the state space {
0,1
,
…
,
W
}. Arrivals occur only at the epochs of jumps in the underlying process ν
t
,
t
≥
0. The intensities of transitions of the process ν
t
,
t
≥
0, which are accompanied (not accompanied) by the arrival of a customer, are defined by the square matrix D
1
(
D
0
) of size W
-
=
W
+
1. The matrix D
=
D
0
+
D
1 is an infinitesimal generator of the process ν
t
,
t
≥
0. The stationary distribution vector χ of this process satisfies the system of equations χ
D
=
0, χ
e
=
1. Here and throughout this paper, 0 is a zero row vector, ande denotes a unit column vector.Such arrival process was introduced as a versatile Markovian point process (VMPP) by M. F. Neuts in the 70s. The original development ofVMPP contained extensive notations; however, these notations were simplified greatly in [2] and ever since this process bears the name Markovian arrival process. The class ofMAPs includes many input flows considered previously, such as stationary Poisson (M), Erlangian (E
k), Hyper-Markovian (HM), Phase-Type (PH), and Markov Modulated Poisson Process (MMPP). Generally speaking, theMAP is correlated, so it is ideal to model correlated and/or bursty traffic in modern telecommunication networks. For more information about theMAP, its properties, and special cases, see [1, 2]. Discussion of applicability of theMAP for description of real life information flows in modern telecommunication networks can be found in [35, 36]. Possibilities of fitting the real world arrival process by means of theMAP are discussed, for example, in [37].The average intensityλ
1 (fundamental rate) of theMAP
1 is defined by λ
1
=
χ
D
1
e. The coefficient of variation c
var of intervals between customer arrivals is calculated as c
var
=
2
λ
1
χ
-
D
0
-
1
e
-
1, and the coefficient of correlation c
cor of successive intervals between arrivals is given as c
cor
=
(
λ
1
χ
-
D
0
-
1
D
1
-
D
0
-
1
e
-
1
)
/
c
var
2.Type 2 customers arrive to the system according to theMAP
2. TheMAP
2 is defined by the underlying process ζ
t
,
t
≥
0, with the finite state space {
0,1
,
…
,
Z
}, and described by the square matrices H
0 and H
1 of size Z
-
=
Z
+
1.The average intensityλ
2 of arrival of type 2 customers is given by λ
2
=
θ
H
1
e; there the vector θ is the stationary distribution vector of the process ζ
t
,
t
≥
0 and is defined as the unique solution to the system θ
(
H
0
+
H
1
)
=
0, θ
e
=
1.We assume that type 1 customers have absolute priority over type 2 customers. If there is a free server during a type 1 customer arrival epoch, this customer receives service immediately. If all servers are busy during a type 1 customer arrival epoch and there are type 2 customers receiving service, the service process of one type 2 customer is terminated and type 1 customer occupies the released server. The type 2 customer who was knocked out from the system goes to the buffer in the tail of the queue with probabilityp and leaves the system with the complimentary probability 1
-
p. If all servers are occupied by type 1 customers during a type 1 customer arrival epoch, this customer leaves the system forever.We assume that some parameter (threshold)M is fixed, 0
<
M
≤
N. Type 2 customers are admitted to the system if the number of busy servers is less than M during type 2 customer arrival epoch. If the number of busy servers is greater than M
-
1 during an arbitrary type 2 customer arrival epoch, this customer goes to the buffer with probability q and with the complimentary probability leaves (balks) the system.Additionally, we assume that type 2 customers can be impatient and leave the buffer after an exponentially distributed time described by parameterα, α
>
0, due to lack of service. If we assume that type 2 customers are patient, we set α
=
0.The service time of typer customers has an exponential distribution with the parameter μ
r, r
=
1,2.


## 3. Process of System States

Leti
t
,
i
t
≥
0, be the number of type 2 customers in the buffer, let n
t
,
n
t
=
0
,
N
¯, be the number of busy servers, let l
t
,
l
t
=
0
,
min
⁡
{
n
t
,
M
}
¯, be the number of type 2 customers in service, let ν
t
,
ν
t
=
0
,
W
¯, be the state of the directing process of theMAP
1, and let ζ
t
,
ζ
t
=
0
,
Z
¯, be the state of the directing process of theMAP
2 at the epoch t
,
t
≥
0. Here the notation like k
=
0
,
K
¯ means that the variable k takes integer values from the set {
0,1
,
2
,
…
,
K
}.The behavior of the system under study can be described in terms of the regular irreducible continuous-time Markov chainξ
t
=
{
i
t
,
n
t
,
l
t
,
ν
t
,
ζ
t
}
,
t
≥
0.Let us introduce the following notation:(i)
I is the identity matrix, and O is a zero matrix of appropriate dimension. If the dimension of a matrix or a vector is not clear from context, it is indicated as the suffix;
(ii)
⊕ and ⊗ indicate the Kronecker sum and product of matrices, respectively; see, for example, [38];
(iii)
diag
⁡
{
A
1
,
…
,
A
l
} is the diagonal matrix with the diagonal entries or blocks A
1
,
…
,
A
l;
(iv)
C
l
=
diag
⁡
{
0,1
,
…
,
l
}, C
-
l
=
diag
⁡
{
l
,
l
-
1
,
…
,
0
}, l
=
0
,
M
¯;
(v)
C
~
l
=
diag
⁡
{
l
,
l
-
1
,
…
,
l
-
M
+
1
,
l
-
M
}, l
=
M
,
N
¯;
(vi)
E
n
+
,
E
^
n
+
,
n
=
0
,
M
-
1
¯, are the matrices of size (
n
+
1
)
×
(
n
+
2
) with all zero entries except the entries (
E
n
+
)
l
,
l
+
1
,
l
=
0
,
n
+
1
¯, and (
E
^
n
+
)
l
,
l
,
l
=
0
,
n
+
1
¯, which are equal to 1;
(vii)
E
n
-
,
E
^
n
-
,
n
=
1
,
M
¯, are the matrices of size (
n
+
1
)
×
n with all zero entries except the entries (
E
n
-
)
l
,
l, l
=
0
,
n
¯, and (
E
^
n
-
)
l
,
l
-
1, l
=
1
,
n
+
1
¯, which are equal to 1;
(viii)
E
- is the square matrix of size M
+
1 with all zero entries except the entries (
E
-
)
l
,
l
-
1
,
l
=
1
,
M
¯, which are equal to 1;
(ix)
I
^
l
,
l
=
M
+
1
,
N
-
M
+
1
¯, are the square matrices of size l with all zero entries except the entry (
I
^
l
)
0,0 which is equal to 1.Let us enumerate the states of the Markov chainξ
t in the direct lexicographic order of the components (
i
,
n
,
l
,
ν
,
ζ
) and refer to the pair (
i
,
n
) as a macrostate.LetQ be the generator of the Markov chain ξ
t
,
t
≥
0, consisting of the blocks Q
i
,
j, which, in turn, consist of the matrices (
Q
i
,
j
)
n
,
n
′ of the transition rates of the Markov chain ξ
t from the macrostate (
i
,
n
) to the macrostate (
j
,
n
′
)
,
n
,
n
′
=
0
,
N
¯. The diagonal entries of the matrices Q
i
,
i are negative, and the moduli of the diagonal entries of these matrices define the total intensities of leaving the corresponding state of the Markov chain ξ
t
,
t
≥
0.Lemma 1.
The infinitesimal generatorQ of the Markov chain ξ
t
,
t
≥
0, has the block-three-diagonal structure
(1)
Q
=
Q
0,0
Q
0,1
O
O
…
Q
1,0
Q
1,1
Q
1,2
O
…
O
Q
2,1
Q
2,2
Q
2,3
…
⋮
⋮
⋮
⋮
⋱
.
The nonzero blocks Q
i
,
j
,
i
,
j
≥
0, have the following form:
(2)
Q
0,0
=
A
0
(
0
)
B
(
0
)
O
…
O
O
F
(
1
)
A
0
(
1
)
B
(
1
)
…
O
O
⋮
⋮
⋱
⋱
⋮
⋮
O
O
O
⋱
A
0
(
N
-
1
)
B
(
N
-
1
)
O
O
O
…
F
(
N
)
A
0
(
N
)
+
I
(
M
+
1
)
(
N
-
M
/
2
+
1
)
⊗
(
D
0
⊕
H
0
)
,
Q
i
,
i
=
A
i
(
M
)
B
(
M
)
O
…
O
O
F
(
M
+
1
)
A
i
(
M
+
1
)
B
(
M
+
1
)
…
O
O
⋮
⋮
⋱
⋱
⋮
⋮
O
O
O
⋱
A
i
(
N
-
1
)
B
(
N
-
1
)
O
O
O
…
F
(
N
)
A
i
(
N
)
+
I
(
N
-
M
+
1
)
(
M
+
1
)
⊗
(
D
0
⊕
H
0
)
,
i
≥
1
,
Q
0,1
=
O
(
M
(
M
+
1
)
/
2
)
W
-
Z
-
×
(
N
-
M
+
1
)
(
M
+
1
)
W
-
Z
-
Q
+
,
Q
+
=
diag
⁡
q
I
(
M
+
1
)
W
-
⊗
H
1
,
…
,
q
I
(
M
+
1
)
W
-
⊗
H
1
︸
N
-
M
,
h
h
h
h
h
p
E
-
⊗
D
1
⊗
I
Z
-
+
q
I
(
M
+
1
)
W
-
⊗
H
1
q
I
(
M
+
1
)
W
-
⊗
H
1
,
…
,
q
I
(
M
+
1
)
W
-
⊗
H
1
︸
N
-
M
,
Q
i
,
i
+
1
=
Q
+
,
i
≥
1
,
Q
1,0
=
O
(
N
-
M
+
1
)
(
M
+
1
)
W
-
Z
-
×
M
(
M
+
1
)
/
2
W
-
Z
-
Q
-
,
Q
-
=
diag
⁡
α
I
M
+
1
+
μ
1
C
-
M
E
+
h
h
h
h
+
μ
2
C
M
,
α
I
M
+
1
,
…
,
α
I
M
+
1
α
I
M
+
1
+
μ
1
C
-
M
E
+
⊗
I
W
-
Z
-
,
Q
i
,
i
-
1
=
diag
⁡
i
α
I
M
+
1
+
μ
1
C
-
M
E
+
h
h
h
h
h
+
μ
2
C
M
,
i
α
I
M
+
1
,
…
,
i
α
I
M
+
1
C
-
M
E
+
⊗
I
W
-
Z
-
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
i
>
1
,
where
(3)
A
i
(
n
)
=
-
(
μ
1
C
~
n
+
μ
2
C
M
)
⊗
I
W
-
Z
-
,
0
≤
n
<
M
,
-
(
μ
1
C
~
n
+
μ
2
C
M
+
i
α
I
M
+
1
)
⊗
I
W
-
Z
-
+
(
1
-
q
)
I
(
M
+
1
)
W
-
⊗
H
1
,
M
≤
n
<
N
,
-
(
μ
1
C
~
n
+
μ
2
C
M
+
i
α
I
M
+
1
)
⊗
I
W
-
Z
-
+
(
I
^
M
+
1
+
(
1
-
p
)
E
-
)
⊗
D
1
⊗
I
Z
-
+
(
1
-
q
)
I
(
M
+
1
)
W
-
⊗
H
1
,
n
=
N
,
i
≥
0
;
B
(
n
)
=
E
n
+
⊗
I
W
-
⊗
H
1
+
E
^
n
+
⊗
D
1
⊗
I
Z
-
,
0
≤
n
<
M
,
I
M
+
1
⊗
D
1
⊗
I
Z
-
,
M
≤
n
<
N
;
F
(
n
)
=
(
μ
1
C
-
n
E
n
-
+
μ
2
C
n
E
^
n
-
)
⊗
I
W
-
Z
-
,
0
<
n
≤
M
,
(
μ
1
C
~
n
+
μ
2
C
M
E
-
)
⊗
I
W
-
Z
-
,
M
<
n
≤
N
.Proof of the lemma is implemented by the analysis of the Markov chainξ
t
,
t
≥
0, transitions during the interval of infinitesimal length, and further combining the corresponding transition intensities in block matrix form.


## 4. Ergodicity Condition and Computation of the Stationary Probabilities

Further, we will separately consider the following two cases.(1) Let us assume thatα
≠
0; that is, customers in the buffer are impatient. In this case, it is possible to verify that the following limits exist:
(4)
Y
0
=
lim
⁡
i
→
∞
R
i
-
1
Q
i
,
i
-
1
,
Y
1
=
lim
⁡
i
→
∞
R
i
-
1
Q
i
,
i
+
I
,
Y
2
=
lim
⁡
i
→
∞
R
i
-
1
Q
i
,
i
+
1
,
where R
i is a diagonal matrix with diagonal entries defined as the moduli of the corresponding diagonal entries of the matrix Q
i
,
i, i
≥
0.The matrixR
i is the block-diagonal matrix with the diagonal blocks T
i
(
n
), n
=
M
,
N
¯, i
≥
0, defined as follows:
(5)
T
i
(
n
)
=
(
μ
1
C
~
n
+
μ
2
C
M
+
i
α
I
M
+
1
)
⊗
I
W
-
Z
-
+
I
M
+
1
⊗
(
Λ
0
⊕
Σ
0
)
-
(
1
-
q
)
I
(
M
+
1
)
W
-
⊗
Σ
1
,
n
=
M
,
N
-
1
¯
;
(
μ
1
C
~
N
+
μ
2
C
M
+
i
α
I
M
+
1
)
⊗
I
W
-
-
I
^
M
+
1
⊗
Σ
1
⊗
I
Z
-
+
I
M
+
1
⊗
(
Λ
0
⊕
Σ
0
)
-
(
1
-
q
)
I
(
M
+
1
)
W
-
⊗
Σ
1
,
n
=
N
,
where Λ
0, Λ
1, Σ
0, and Σ
1 are diagonal matrices with diagonal entries defined by the diagonal entries of the matrices -
D
0, D
1
,
-
H
0, and H
1, respectively.The matricesY
0, Y
1, and Y
2 have the following form:
(6)
Y
0
=
I
,
Y
1
=
O
,
Y
2
=
O
;
so, their sum is the stochastic matrix.According to the definition given in [39], the Markov chain ξ
t, t
≥
0, belongs to the class of so called continuous-time asymptotically quasi-Toeplitz Markov chains (AQTMC).As follows from [39], the sufficient condition for the ergodicity of theAQTMC is the following condition:
(7)
y
Y
0
e
>
y
Y
2
e
,
where the row-vector y is the unique solution to the following system of linear algebraic equations:
(8)
y
Y
0
+
Y
1
+
Y
2
=
y
,
y
e
=
1
.Taking into account explicit values (6) of the matrices Y
0, Y
1, and Y
2, inequality (7) can be rewritten as y
Y
0
e
>
0, and system (8) is rewritten in the form y
Y
0
=
y, y
e
=
1. Hence, y
Y
0
e
=
y
e
=
1
>
0; so, inequality (7) holds true for each set of the system parameters. So, the Markov chain under consideration is ergodic and the queueing system under study is stable for any set of the system parameters.(2) Let us assume now thatα
=
0. In this case, the blocks of the generator have the following form:
(9)
Q
i
,
i
=
Q
1
=
A
0
M
B
M
O
…
O
O
F
M
+
1
A
0
M
+
1
B
M
+
1
…
O
O
⋮
⋮
⋱
⋱
⋮
⋮
O
O
O
⋱
A
0
N
-
1
B
N
-
1
O
O
O
…
F
N
A
0
N
+
I
N
-
M
+
1
M
+
1
⊗
D
0
⊕
H
0
,
i
>
0
,
Q
i
,
i
+
1
=
Q
2
=
Q
+
,
i
≥
1
,
Q
i
,
i
-
1
=
Q
0
=
diag
⁡
μ
1
C
-
M
E
+
+
μ
2
C
M
,
O
M
+
1
,
…
,
O
M
+
1
⊗
I
W
-
Z
-
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
i
>
1
.Thus, the blocks of the generator do not depend on the variablei when i
>
1 and the Markov chain ξ
t
,
t
≥
0, belongs to the class of continuous-time quasi-Toeplitz Markov chains (QTMC) or M
/
G
/
1-type Markov chains; see [40].As follows from [40], the necessary and sufficient condition for the ergodicity of theQTMC is the fulfillment of the following inequality:
(10)
x
Q
0
e
>
x
Q
2
e
,
where the vector x is the unique solution to the system
(11)
x
(
Q
0
+
Q
1
+
Q
2
)
=
0
,
x
e
=
1
.It is easy to verify that system (11) can be rewritten in the form(12)
0
=
x
(
Q
0
+
Q
1
+
Q
2
)
=
x
-
μ
1
C
~
M
(
I
-
E
+
)
O
O
…
O
O
μ
1
C
~
M
+
1
+
μ
2
C
M
E
-
-
(
μ
1
C
~
M
+
1
+
μ
2
C
M
)
O
…
O
O
⋮
⋮
⋮
⋱
⋮
⋮
O
O
O
…
-
(
μ
1
C
~
N
-
1
+
μ
2
C
M
)
O
O
O
O
…
μ
1
C
~
N
+
μ
2
C
M
E
-
-
(
μ
1
C
~
N
+
μ
2
C
M
)
I
M
+
1
⊗
D
0
I
M
+
1
⊗
D
1
…
O
O
O
I
M
+
1
⊗
D
0
…
O
O
⋮
⋮
⋱
⋮
⋮
O
O
…
I
M
+
1
⊗
D
0
I
M
+
1
⊗
D
1
O
O
…
O
(
E
-
+
I
^
)
⊗
D
1
+
I
M
+
1
⊗
D
0
⊗
I
Z
-
hhh
+
I
N
-
M
+
1
M
+
1
W
-
⊗
H
1
hhh
+
-
μ
1
C
~
M
(
I
-
E
+
)
O
O
…
O
O
μ
1
C
~
M
+
1
+
μ
2
C
M
E
-
-
(
μ
1
C
~
M
+
1
+
μ
2
C
M
)
O
…
O
O
⋮
⋮
⋮
⋱
⋮
⋮
O
O
O
…
-
(
μ
1
C
~
N
-
1
+
μ
2
C
M
)
O
O
O
O
…
μ
1
C
~
N
+
μ
2
C
M
E
-
-
(
μ
1
C
~
N
+
μ
2
C
M
)
⊗
I
W
-
Z
-
,
x
e
=
1
.By postmultiplying the left and right hand side of (12) by e
(
N
-
M
+
1
)
(
M
+
1
)
W
-
⊗
I
Z
- we obtain that
(13)
x
(
e
(
N
-
M
+
1
)
(
M
+
1
)
W
-
⊗
H
(
1
)
)
=
0
,
x
e
=
1
.By postmultiplying the left and right hand side of (12) by e
(
N
-
M
+
1
)
(
M
+
1
)
⊗
I
W
-
⊗
e
Z
- we obtain that
(14)
x
(
e
N
-
M
+
1
M
+
1
⊗
D
(
1
)
⊗
e
Z
-
)
=
0
,
x
e
=
1
.It follows from (13) and (14) that the vector x can be represented in the form
(15)
x
=
z
⊗
χ
⊗
θ
,
where z is a stochastic vector of size (
N
-
M
+
1
)
(
M
+
1
), χ is the invariant probability vector of the underlying Markov chain of theMAP
1, and θ is the invariant probability vector of the underlying Markov chain of theMAP
2.Substituting the vectorx form (15) into (12), postmultiplying this equation by I
(
N
-
M
+
1
)
(
M
+
1
)
⊗
e
W
-
Z
-, and taking into account that χ
D
1
e
=
λ
1,χ
D
0
e
=
-
χ
D
1
e
=
-
λ
1, θ
H
(
1
)
=
0, θ
e
=
1, and χ
e
=
1, we obtain that the vector z is the unique solution to the system
(16)
z
Ω
=
0
,
z
e
=
1
,
where(17)
Ω
=
A
~
(
M
)
λ
1
I
M
+
1
O
…
O
O
O
μ
1
C
~
M
+
1
+
μ
2
C
M
E
-
A
~
(
M
+
1
)
λ
1
I
M
+
1
…
O
O
O
⋮
⋮
⋮
⋱
⋮
⋮
⋮
O
O
O
…
μ
1
C
~
N
-
1
+
μ
2
C
M
E
-
A
~
(
N
-
1
)
λ
1
I
M
+
1
O
O
O
…
O
μ
1
C
~
N
+
μ
2
C
M
E
-
A
~
(
N
)
,
A
~
(
n
)
=
-
μ
1
C
~
M
(
I
-
E
+
)
-
λ
1
I
M
+
1
,
n
=
M
,
M
<
N
;
-
μ
1
C
~
M
(
I
-
E
+
)
-
λ
1
(
I
-
E
-
-
I
^
)
,
n
=
M
=
N
,
-
μ
1
C
~
n
-
μ
2
C
M
-
λ
1
I
M
+
1
,
M
<
n
<
N
,
-
μ
1
C
~
N
-
μ
2
C
M
-
λ
1
(
I
-
E
-
-
I
^
M
+
1
)
,
n
=
N
>
M
.It easy to verify that the matrixΩ is the generator of two-dimensional Markov chain {
n
t
,
l
t
}
,
t
≥
0, defining the number of busy servers n
t
,
n
t
=
M
,
N
¯, and the number of servers occupied by type 2 customers l
t
,
l
t
=
0
,
M
¯, at the moment t in the case when the system is overloaded. It is evident that when the system is overloaded the number of busy servers n
t can vary in the interval [
M
,
N
]. It follows from (16) that the vector z
=
(
z
M
,
…
,
z
N
), z
n
=
(
z
(
n
,
0
)
,
…
,
z
(
n
,
M
)
), n
=
M
,
N
¯, defines the joint stationary distribution of the number of busy servers and the number of servers occupied by type 2 customers when the system is overloaded.Taking this into account, substituting the vectorx form (15) into inequality (10) and performing some algebra, we obtain the following inequality:
(18)
z
M
μ
1
C
-
M
+
μ
2
C
M
e
>
q
λ
2
+
p
λ
1
z
N
e
^
,
where e
^ is the vector of size M
+
1 with all unit entries except the entry (
e
^
)
0 which is equal to zero.Thus, we have proved the following assertion.Theorem 2.
Ifα
≠
0, the Markov chain ξ
t
,
t
≥
0, is ergodic for any set of the system parameters. If α
=
0, the Markov chain ξ
t
,
t
≥
0, is ergodic, if and only if inequality (18) holds true where the vector z is defined as the solution to system (16).Remark 3.
Condition (18) is intuitively clear and can be interpreted as follows. If the system is overloaded and type 2 customers are patient (α
=
0), then type 2 customer can leave the buffer only if the number of busy servers becomes less than M. The components z
(
M
,
l
)
,
l
=
0
,
M
¯, of the vector z
M define the probability that during an arbitrary epoch the number of busy servers is M and there are l type 2 customers who receive service. So, the left hand side of (18) defines the intensity of the service completions when M servers are busy (the intensity of customers leaving the buffer). The right hand side of (18) defines the total intensity of type 2 customers arrival into the buffer. When the system is overloaded, all admitted type 2 customers (the intensity of this flow is q
λ
2) and type 2 customers whose service was terminated by arrival of type 1 customers (the intensity of this flow is p
λ
1
z
N
e
^) arrive into the buffer. Thus, ergodicity condition (18) requires that, in the situation when the system is overloaded, the intensity of type 2 customers arriving to the buffer is less than the intensity of type 2 customers leaving the buffer.Further, we assume that Markov chainξ
t
,
t
≥
0, is ergodic. Then the following limits (stationary probabilities) exist:
(19)
π
i
,
n
,
l
,
ν
,
ζ
=
lim
⁡
t
→
∞
P
i
t
=
i
,
n
t
=
n
,
l
t
=
l
,
ν
t
=
ν
,
ζ
t
=
ζ
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
i
≥
0
,
n
=
1
-
δ
i
,
0
M
,
N
¯
,
h
h
h
h
h
h
h
h
h
h
h
h
h
l
=
0
,
min
⁡
⁡
n
,
M
¯
,
ν
=
0
,
W
¯
,
ζ
=
0
,
Z
¯
.
Here δ
i
,
0 indicates the Kronecker delta.Let us form the row vectorsπ
i of these probabilities as follows:
(20)
π
i
,
n
,
l
,
ν
=
π
i
,
n
,
l
,
ν
,
0
,
π
i
,
n
,
l
,
ν
,
1
,
…
,
π
i
,
n
,
l
,
ν
,
Z
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
i
≥
0
,
n
=
1
-
δ
i
,
0
M
,
N
¯
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
l
=
0
,
min
⁡
{
n
,
M
}
¯
,
ν
=
0
,
W
¯
,
π
i
,
n
,
l
=
(
π
(
i
,
n
,
l
,
0
)
,
π
(
i
,
n
,
l
,
1
)
,
…
,
π
(
i
,
n
,
l
,
W
)
)
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
i
≥
0
,
n
=
1
-
δ
i
,
0
M
,
N
¯
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
l
=
0
,
min
⁡
{
n
,
M
}
¯
,
π
i
,
n
=
(
π
(
i
,
n
,
0
)
,
π
(
i
,
n
,
1
)
,
…
,
π
(
i
,
n
,
min
⁡
{
n
,
M
}
)
)
,
hhhhhhhhhhhhhh
i
≥
0
,
n
=
(
1
-
δ
i
,
0
)
M
,
N
¯
,
π
i
=
π
i
,
0
,
π
i
,
1
,
…
,
π
i
,
N
,
i
≥
0
.It is well known that the probability vectorsπ
i
,
i
≥
0, satisfy the following system of linear algebraic equations:
(21)
(
π
0
,
π
1
,
…
)
Q
=
0
,
(
π
0
,
π
1
,
…
)
e
=
1
.System (21) is infinite, so it can not be solved on a computer by standard methods. To compute the probability vectors π
i
,
i
≥
0, in both the cases, α
>
0 and α
=
0, the numerically stable algorithms presented in [39] can be used. The idea of these algorithms is as follows. Instead of solution of the system (21), another infinite system of linear algebraic equations for the probability vectors π
i
,
i
≥
0, is derived by means of sequential constructions of so called censored Markov chains (see, e.g., [41]) for the initial Markov chain ξ
t
,
t
≥
0, with different levels of censoring. This leads to numerically stable procedure for computation of the vectors π
i
,
i
≥
0.


## 5. Performance Measures

Having computed the vectors of the stationary probabilitiesπ
i
,
i
≥
0, it is possible to compute a variety of the system performance measures.The average number of customers in the system is(22)
L
=
∑
n
=
1
N
‍
n
π
(
0
,
n
)
e
+
∑
i
=
1
∞
‍
∑
n
=
M
N
‍
(
i
+
n
)
π
(
i
,
n
)
e
.The average number of customers in the buffer is(23)
N
buffer
=
∑
i
=
1
∞
‍
i
π
i
e
.The average number of busy servers is(24)
N
server
=
∑
i
=
0
∞
‍
∑
n
=
1
N
‍
n
π
(
i
,
n
)
e
.The average number of busy servers providing service to type 1 customers is(25)
N
server
-
1
=
∑
n
=
1
N
‍
∑
l
=
0
min
⁡
{
n
,
M
}
‍
(
n
-
l
)
π
(
0
,
n
,
l
)
e
+
∑
i
=
1
∞
‍
∑
n
=
M
N
‍
∑
l
=
0
M
‍
(
n
-
l
)
π
(
i
,
n
,
l
)
e
.The average number of busy servers providing service to type 2 customers is(26)
N
server
-
2
=
∑
n
=
1
N
‍
∑
l
=
1
min
⁡
{
n
,
M
}
‍
l
π
(
0
,
n
,
l
)
e
+
∑
i
=
1
∞
‍
∑
n
=
M
N
‍
∑
l
=
1
M
‍
l
π
(
i
,
n
,
l
)
e
=
N
server
-
N
server
-
1
.The intensity of output flow of type 1 customers is(27)
λ
out
(
1
)
=
μ
1
N
server
-
1
.The intensity of output flow of type 2 customers is(28)
λ
2
out
=
μ
2
N
server
-
2
.The intensity of output flow of customers is(29)
λ
out
=
λ
1
out
+
λ
2
out
.The loss probability of type 1 customers is(30)
P
1
loss
=
λ
1
-
1
∑
i
=
0
∞
‍
π
(
i
,
N
,
0
)
(
D
1
⊗
I
Z
-
)
e
=
1
-
λ
1
out
λ
1
.The loss probability of type 2 customers is(31)
P
2
loss
=
1
-
λ
2
out
λ
2
.The loss probability of an arbitrary customer is(32)
P
loss
=
1
-
λ
out
λ
1
+
λ
2
.The probability of type 2 customer loss at the entrance to the system is(33)
P
ent-loss
=
(
1
-
q
)
λ
2
-
1
∑
i
=
0
∞
‍
∑
n
=
M
N
‍
π
(
i
,
n
)
(
I
(
M
+
1
)
W
-
⊗
H
1
)
e
.The probability that an arbitrary type 2 customer will be forced to terminate its service and go to the buffer is(34)
P
knock-out-to-buffer
=
p
λ
1
-
1
∑
i
=
0
∞
‍
∑
l
=
1
M
‍
π
(
i
,
N
,
l
)
(
D
1
⊗
I
Z
-
)
e
.The probability that an arbitrary type 2 customer will be forced to terminate its service and leave the system is(35)
P
knock-out-loss
=
(
1
-
p
)
λ
1
-
1
∑
i
=
0
∞
‍
∑
l
=
1
M
‍
π
(
i
,
N
,
l
)
(
D
1
⊗
I
Z
-
)
e
.The probability that an arbitrary type 2 customer will leave the buffer due to impatience is(36)
P
imp-loss
=
P
2
loss
-
P
ent-loss
-
P
knock-out-loss
.


## 6. Distribution of the Waiting Time of an Arbitrary Type 2 Customer

Type 1 customers having preemptive priority do not wait for service. So, we analyze only the distribution of waiting time of an arbitrary type 2 customer. Speaking about the arbitrary type 2 customer, we do not distinguish type 2 customers arriving to the system from outside and customers arriving to the buffer due to the service force termination.LetV
(
x
) be the distribution function of the waiting time of an arbitrary type 2 customer in the system and let v
(
s
)
=
∫
0
∞
‍
e
-
s
x
d
V
(
x
)
,
Re
s
>
0, be its Laplace-Stieltjes transform (LST).To derive an expression for theLST
v
(
s
), we use the method of collective marks; see, for example, [42, 43]. Let us tag an arbitrary type 2 customer and keep track of its staying in the system. According to the idea of the method of collective marks, v
(
s
) has the meaning of the probability that no catastrophe from some virtual stationary Poisson flow of catastrophes with the intensity s arrives during the waiting time of the tagged type 2 customer.Letv
(
s
,
r
,
n
,
l
,
ν
) be the probability that no catastrophe arrive during the rest of the tagged customer waiting time conditioned on the fact that, at the given moment, the position of the tagged customer in the buffer is equal to r
,
r
≥
1, the number of busy servers is n
,
n
=
M
,
N
¯, the number of busy servers providing service to type 2 customers is l
,
l
=
0
,
M
¯, and the state of the process ν
t
,
t
≥
0, is ν.Let us enumerate the probabilitiesv
(
s
,
r
,
n
,
l
,
ν
) in the lexicographic order of the components n
,
l, and ν and form the following column vectors:
(37)
v
(
s
,
r
,
n
,
l
)
=
v
s
,
r
,
n
,
l
,
0
,
…
,
v
s
,
r
,
n
,
l
,
W
T
,
l
=
0
,
M
¯
,
v
(
s
,
r
,
n
)
=
v
s
,
r
,
n
,
0
,
…
,
v
s
,
r
,
n
,
M
T
,
n
=
M
,
N
¯
,
v
(
s
,
r
)
=
v
s
,
r
,
M
,
…
,
v
s
,
r
,
N
T
,
r
≥
1
.Let us also introduce the following notation:(38)
V
r
,
r
=
A
-
r
(
M
)
I
M
+
1
⊗
D
1
O
…
O
O
F
-
(
M
+
1
)
A
-
r
(
M
+
1
)
I
M
+
1
⊗
D
1
…
O
O
⋮
⋮
⋱
⋱
⋮
⋮
O
O
O
⋱
A
-
r
(
N
-
1
)
I
M
+
1
⊗
D
1
O
O
O
…
F
-
(
N
)
A
-
r
(
N
)
+
I
(
N
-
M
+
1
)
(
M
+
1
)
⊗
D
0
,
r
≥
1
,
V
r
,
r
-
1
=
I
^
N
-
M
+
1
⊗
(
μ
1
C
-
M
E
+
+
μ
2
C
M
)
⊗
I
W
-
+
r
-
1
α
I
N
-
M
+
1
M
+
1
W
-
,
r
≥
1
,where
(39)
A
-
r
(
n
)
=
-
(
μ
1
C
~
n
+
μ
2
C
M
+
r
α
I
M
+
1
)
⊗
I
W
-
,
M
≤
n
<
N
,
r
≥
0
,
-
(
μ
1
C
~
n
+
μ
2
C
M
+
r
α
I
M
+
1
)
⊗
I
W
-
+
(
E
-
+
I
^
M
+
1
)
⊗
D
1
,
n
=
N
,
r
≥
0
;
(40)
F
-
(
n
)
=
(
μ
1
C
~
n
+
μ
2
C
M
E
-
)
⊗
I
W
-
,
M
<
n
≤
N
.Lemma 4.
The vectorsv
(
s
,
r
),r
≥
1, can be recursively calculated as follows:
(41)
v
s
,
1
=
s
I
-
V
1,1
-
1
×
α
I
+
I
^
N
-
M
+
1
⊗
μ
1
C
~
M
+
μ
2
C
M
⊗
I
W
-
e
,
v
s
,
r
=
s
I
-
V
r
,
r
-
1
V
r
,
r
-
1
v
s
,
r
-
1
+
α
e
,
r
>
1
.Proof.
Based on a probabilistic sense of theLST, we obtain the following system of equations for calculation of the vectors v
(
s
,
r
,
n
,
l
):
(42)
v
s
,
r
,
n
,
l
=
s
+
r
α
+
n
-
l
μ
1
+
l
μ
2
I
W
-
-
D
0
-
1
×
+
n
-
l
μ
1
v
s
,
r
,
n
-
1
,
l
1
-
δ
n
,
N
D
1
v
s
,
r
,
n
+
1
,
l
hhhhhh
+
(
r
-
1
)
α
v
(
s
,
r
-
1
,
n
,
l
)
hhhhhh
+
δ
n
,
N
1
-
δ
l
,
0
δ
l
,
0
D
1
v
(
s
,
r
,
n
,
l
)
hhhhhhhhhhhh
+
1
-
δ
l
,
0
D
1
v
s
,
r
,
n
,
l
-
1
hhhhhh
+
1
-
δ
r
,
1
δ
n
,
M
n
-
l
μ
1
l
μ
2
v
s
,
r
-
1
,
n
,
l
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
+
n
-
l
μ
1
v
s
,
r
-
1
,
n
,
l
+
1
hhhhhh
+
δ
r
,
1
δ
n
,
M
l
μ
2
+
n
-
l
μ
1
e
+
α
e
hhhhhh
+
1
-
δ
n
,
M
n
-
l
μ
1
l
μ
2
v
s
,
r
,
n
-
1
,
l
-
1
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
+
n
-
l
μ
1
v
s
,
r
,
n
-
1
,
l
,
l
=
0
,
M
¯
,
n
=
M
,
N
¯
,
r
≥
1
.
System (42) can be rewritten in the following matrix form:
(43)
-
s
I
+
V
r
,
r
v
(
s
,
r
)
+
1
-
δ
r
,
1
V
r
,
r
-
1
v
s
,
r
-
1
+
α
e
+
δ
r
,
1
I
^
N
-
M
+
1
⊗
μ
2
C
M
+
μ
1
C
~
M
⊗
I
W
-
e
=
0
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
r
≥
1
,
which can be further transformed to form (41). Lemma is proved.Theorem 5.
TheLST
v
(
s
) of the distribution of the waiting time of an arbitrary type 2 customer in the system is calculated as follows:
(44)
v
s
=
λ
~
-
1
∑
n
=
0
M
-
1
‍
π
(
0
,
n
)
(
I
(
n
+
1
)
W
-
⊗
H
1
)
e
hhhhhhh
+
1
-
q
∑
i
=
0
∞
‍
∑
n
=
M
N
‍
π
i
,
n
I
M
+
1
W
-
⊗
H
1
e
hhhhhhh
+
q
∑
i
=
0
∞
‍
∑
n
=
M
N
‍
∑
l
=
0
M
‍
π
i
,
n
,
l
I
W
-
⊗
H
1
e
Z
-
v
s
,
i
+
1
,
n
,
l
hhhhhhh
+
p
∑
i
=
0
∞
‍
∑
l
=
1
M
‍
π
i
,
N
,
l
D
1
⊗
e
Z
-
v
s
,
i
+
1
,
N
,
l
-
1
,
where
(45)
λ
~
=
λ
2
+
p
∑
i
=
0
∞
‍
∑
l
=
1
M
‍
π
(
i
,
N
,
l
)
(
D
1
⊗
I
Z
-
)
e
.Proof.
The proof follows from the law of total probability and a probabilistic sense of theLSTs.
The following situations are possible during the arrival epoch of the tagged type 2 customer.(i)
The number of busy servers is less thanM and the tagged customer immediately receives service. The probability of this event is λ
~
-
1
∑
n
=
0
M
-
1
‍
π
(
0
,
n
)
(
I
(
n
+
1
)
W
-
⊗
H
1
)
e. In this case, the probability of no catastrophe arrival during the waiting time is equal to one.
(ii)
The number of busy servers is greater thanM and the customer decides to balk the system. The probability of this event is λ
~
-
1
(
1
-
q
)
∑
i
=
0
∞
‍
∑
n
=
M
N
‍
π
(
i
,
n
)
(
I
(
M
+
1
)
W
-
⊗
H
1
)
e. In this case, the probability of no catastrophe arrival during the waiting time of the tagged type 2 customer is also equal to one.
(iii)
The number of busy servers is greater thanM and the customer decides to join the buffer. The probability of this event is λ
~
-
1
q
∑
i
=
0
∞
‍
∑
n
=
M
N
‍
∑
l
=
0
M
‍
π
(
i
,
n
,
l
)
(
I
W
-
⊗
H
1
e
Z
-
). In this case, the probability of no catastrophe arrival during the waiting time of the tagged type 2 customer under the fixed values of the components i
,
n, and l is equal to v
(
s
,
i
+
1
,
n
,
l
).
(iv)
The tagged customer arrives to the buffer after the termination of its service by arriving type 1 customer. The probability of this event isλ
~
-
1
p
∑
i
=
0
∞
‍
∑
l
=
1
M
‍
π
(
i
,
N
,
l
)
(
D
1
⊗
e
Z
-
). In this case, the probability of no one catastrophe arrival during the waiting time of the tagged type 2 customer under the fixed values of the components i
,
n
,
l is equal to v
(
s
,
i
+
1
,
N
,
l
-
1
).
Using the law of total probability, now it is possible to easily verify the validity of the statement of the theorem.Corollary 6.
The average waiting timeV
w
a
i
t of an arbitrary type 2 customer can be calculated as follows:
(46)
V
w
a
i
t
=
-
λ
~
-
1
p
∑
i
=
0
∞
‍
∑
l
=
1
M
‍
π
i
,
N
,
l
D
1
⊗
e
Z
-
h
h
h
h
h
h
h
h
h
h
×
v
′
(
s
,
i
+
1
,
N
,
l
-
1
)
s
=
0
h
h
h
h
h
h
h
h
h
h
+
q
∑
i
=
0
∞
‍
∑
n
=
M
N
‍
∑
l
=
0
M
‍
π
i
,
n
,
l
I
W
-
⊗
H
1
e
Z
-
h
h
h
h
h
h
h
h
h
h
×
v
′
s
,
i
+
1
,
n
,
l
s
=
0
∑
l
=
1
M
‍
.
Here, the column vectorsv
′
(
s
,
r
,
n
,
l
)
s
=
0 are defined as blocks of the vectors v
′
(
s
,
r
)
|
s
=
0
,
r
≥
1, which can be calculated as
(47)
v
′
s
,
1
s
=
0
=
-
V
1,1
-
2
α
I
+
I
^
N
-
M
+
1
⊗
μ
2
C
M
+
μ
1
C
~
M
⊗
I
W
-
e
,
v
′
(
s
,
r
)
s
=
0
=
V
r
,
r
-
1
e
-
V
r
,
r
-
1
v
′
s
,
r
-
1
,
r
>
1
.


## 7. Numerical Examples and Optimization Problem

The purposes of this section are to demonstrate the feasibility of the proposed algorithms for computation of the key performance measures of the system, to give an example of numerical solution of optimization problem and to bring out some qualitative aspects of the considered queue.Let the arrival process of type 1 customers be defined by the matrices(48)
D
0
=
-
3.64163
0.10758
0.04921
-
0.31828
,
D
1
=
3.45660
0.07745
0.06276
0.20631
.
The fundamental rate of this arrival process is λ
1
=
1.5, the coefficient of correlation of successive interarrival times is c
cor
=
0.25, the coefficient of variation of interarrival times is c
var
=
5.4.Basically, the arrival process of type 2 customers is defined by the matrices(49)
H
0
=
-
0.6759
0
0
-
0.02193
,
H
1
=
0.67141
0.00449
0.01222
0.00971
.
The fundamental rate of this arrival process is λ
2
=
0.5, the coefficient of correlation of successive interarrival times is c
cor
=
0.2, and the coefficient of variation of interarrival times is c
var
=
12.34.The rest of the system parameters are given by(50)
N
=
24
,
α
=
0.15
,
q
=
0.8
,
p
=
0.1
,
μ
1
=
0.22
,
μ
2
=
0.3
.To illustrate behavior of the key performance measures of the system, we will vary the thresholdM of admission strategy (recall that a type 2 customer is admitted to service only if the number of busy servers at its arrival instant is less than M) in the range M
∈
[
1
;
24
] and the intensity λ
2 of the arrival process of type 2 customers in the range λ
2
∈
[
0.5
;
6
]. Variation of the intensity λ
2 is easily implemented by means of multiplying the matrices H
0 and H
1 by the corresponding factor.Three-dimensional Figure1 illustrates the dependence of the average number of customers in the system L and the average number of customers in the buffer N
buffer on M and λ
2.Dependence ofL and N
buffer on M and λ
2.
(a)
(b)It is quite natural that bothL and N
buffer increase when the intensity λ
2 grows: the grow of the arrival rate under the fixed services rates causes presence of more customers in the system and in the buffer. But the increase of M oppositely affects the values L and N
buffer. When M grows, the value of L increases because the growth of M decreases the probability of type 2 customers balking (increases the rate of the flow of admitted customers). The value of N
buffer decreases when M grows because the growth of M increases the percentage of type 2 customers that succeed to get access to service immediately upon arrival, without visiting the buffer. However, when M becomes too close to N, many type 2 customers are compelled to terminate service due to type 1 customer arrival and the value of N
buffer stops decreasing.Figure2 illustrates the dependence of the probability P
ent-loss of the type 2 customer loss at the entrance to the system and the probability P
imp-loss that an arbitrary type 2 customer leaves the buffer due to impatience on M and λ
2.Dependence ofP
ent-loss and P
imp-loss on M and λ
2.
(a)
(b)It can be seen that the value ofP
ent-loss sharply grows when M decreases and λ
2 increases. It is obvious because the decrease of M and the growth of λ
2 imply congestion in the system for type 2 customers. When M is small or λ
2 is large, type 2 customers practically have the chance to start service immediately upon arrival. In this situation, they balk with probability 1
-
q
=
0.2 what explains the presence of almost plate part on the surface in Figure 2 at level 0.2. Behavior of P
imp-loss correlates with behavior of N
buffer in Figure 1 what is easily understandable because the rate of customers departure from the system due to impatience positively correlates with the number of customers in the buffer.Figure3 illustrates the dependence of the probability P
knock-out-loss that an arbitrary type 2 customer will be forced to terminate service and will leave the system and the probability P
2
loss that an arbitrary type 2 customer is lost on M and λ
2.Dependence ofP
knock-out-loss and P
2
loss on M and λ
2.
(a)
(b)The plot illustrating behavior of the probabilityP
knock-out-loss well illustrates the reasonability of reservation of some part of servers exclusively for service of priority customers. When the parameter M approaches the value N, that is, the number of reserved servers decreases, the probability P
knock-out-loss drastically increases, especially when the arrival rate λ
2 is not very small. The plot illustrating behavior of the probability P
2
loss is quite clear taking in mind that this probability is the sum of the probabilities P
ent-loss, P
knock-out-loss, and P
imp-loss illustrated in the previous figures.Figure4 illustrates the dependence of the intensity of output flow of type 2 customers λ
2
out and the average waiting time V
wait of an arbitrary type 2 customer on M and λ
2.Dependenceλ
2
out and V
wait on M and λ
2.
(a)
(b)Behavior ofλ
2
out is quite clear taking into account the illustrated above behavior of P
2
loss and formula P
2
loss
=
1
-
(
λ
2
out
/
λ
2
). Behavior of V
wait is similar to behavior of N
buffer in Figure 1. However, V
wait does not grow so quickly for small M and large λ
2 as the value N
buffer grows. This is explained by the fact that it is accounted for in calculation of the average waiting time V
wait of an arbitrary type 2 customer that, by definition, some such customers do not visit the buffer at all (they are lost at the entrance to the system or are lucky to receive service without visiting the buffer) and, so, have zero waiting time.Let us consider optimization problem. First of all, we have to formulate a cost criterion in terms of which the quality of system operation will be evaluated. Because type 1 customers have preemptive priority, the quality of their service is completely defined by the value ofP
1
loss which does not depend on the arrival and service processes of type 2 customers. P
1
loss is constant for any values of the control parameter M. So, cost criterion should include only characteristics of service of type 2 customers. Because the goal of the operation of almost any queueing system is to provide maximal profit to the system owner and this profit is proportional to the number of customers, who got service in the system, it is reasonable to include the output rate λ
2
out as the main component of the cost criterion. But if the cost criterion will include only the output rate λ
2
out, solution of optimization problem seems be trivial M
=
N; that is, no server reservation should be assumed. Any arriving customer should be admitted to the system if ergodicity condition for the system is fulfilled. But, as we see from the presented numerical results, the absence of servers reservation implies high values of the probabilities of losses of type 2 customers, in particular, the probability of force termination of service provided to type 2 customers. Such a termination can be quite offensive and frustrating for type 2 customers. Also the absence of servers reservation causes long average waiting time, especially waiting time of customers who really wait for beginning of service.As the result of these considerations, we conclude that the reasonable form of the cost criterion (profit obtained during a unit of time) is the following one:(51)
E
M
,
λ
2
=
a
λ
2
out
-
λ
2
c
1
P
ent-loss
+
c
2
P
imp-loss
+
c
3
P
knock-out-loss
-
c
4
V
wait
,
where the performance indices λ
2
out, P
ent-loss, P
imp-loss, P
knock-out-loss, and V
wait were introduced above, a is the average profit earned by service of one type 2 customer, and c
1
,
c
2
,
c
3
,
c
4, are the corresponding charged for customer loss and waiting. Our aim is to find the optimal value M
* of the parameter M that provides the maximal value of the cost criterion E
(
M
,
λ
2
). It should be noted that maximization of E
(
M
,
λ
2
) has to be done with respect to M for a fixed value of λ
2. We included λ
2 to notation E
(
M
,
λ
2
) just to stress that the optimal value M
* may be different for various values of λ
2.Let us fix the same values of parameters of the system as above and the values of cost coefficients are fixed as follows:(52)
a
=
10
,
c
1
=
5
,
c
2
=
3
,
c
3
=
20
,
c
4
=
3
.Figure5 illustrates the dependence of the cost criterion E
(
M
,
λ
2
) on Mand λ
2.Figure 5Presented table gives a bit more information about the behavior of the cost criterionE
(
M
,
λ
2
) on M. For various λ
2, the table gives the optimal value M
* of the parameter M, optimal value E
(
M
*
,
λ
2
) of the cost criterion, value E
(
N
,
λ
2
) of the cost criterion for the system without servers reservation, the difference E
(
M
*
,
λ
2
)
-
E
(
N
,
λ
2
) (the profit provided by means of the optimal reservation), and the ratio (
(
E
(
M
*
,
λ
2
)
-
E
(
N
,
λ
2
)
)
/
E
(
N
,
λ
2
)
)
×
100
% of the relative profit provided by means of the optimal reservation comparing to a strategy of customers access without servers reservation.It is seen from Figure5 and Table 1 that the profit and the relative profit provided by means of the optimal reservation comparing to a strategy of customers access without servers reservation can be significant.Table 1
Information about the optimal values of the threshold, cost criterion, and profit in comparison to the system without admission control for various intensitiesλ
2.
λ
2
M
*
E
(
M
*
,
λ
2
)
E
(
N
,
λ
2
)
E
(
M
*
,
λ
2
)
-
E
(
N
,
λ
2
)
E
l
(
M
*
,
λ
2
)
-
E
(
N
,
λ
2
)
E
(
N
,
λ
2
)
×
100
%
0.5
23
4.76106
4.74152
0.01954
0.4121%
1
22
9.24359
9.1041
0.13949
1.5321%
1.5
22
13.3147
12.9048
0.4099
3.1763%
2
22
16.8746
16.0199
0.8547
5.3352%
2.5
22
19.8463
18.3934
1.4529
7.899%
3
22
22.1576
20.013
2.1446
10.716%
3.5
22
23.752
20.8855
2.8665
13.7248%
4
22
24.6281
21.0436
3.5845
17.0336%
4.5
22
24.8576
20.5675
4.2901
20.8586%
5
22
24.562
19.5818
4.9802
25.4327%
5.5
22
23.8748
18.2299
5.6449
30.9650%
6
22
22.9148
16.6467
6.2681
37.6537%


## 8. Conclusion

We considered a multiserver queuing system with an infinite buffer and two types of customers one of which has preemptive priority over another. To reduce the frequency of forced termination of service of type 2 customers, we offered the threshold strategy of access of type 2 customers. Access of such customers is denied if the number of busy servers at the customer arrival moment is not less than the preassigned threshold value. For the fixed value of the threshold, we described behavior of the system by the multidimensional Markov chain. For this chain, the ergodicity condition is derived; the stationary distribution of the system states and the main performance measures are calculated. The Laplace-Stieltjes transform of the waiting time distribution of an arbitrary type 2 customer is derived. Numerical examples confirming the advantage of the proposed access strategy under properly chosen value of the threshold are presented.Presented analysis may be extended to the cases of theMMAP (marked Markovian arrival process) of customers arrival (what allows to take into account possible correlation within arrivals of priority and nonpriority customers) and theBMAP (batch Markovian arrival process) of nonpriority customers, possibility to have an additional finite buffer for priority customers, and so forth.In this paper we assume that the service time distribution for both types of customers is exponential. This is rather restrictive assumption. It is worth to note that in many practical situations available information about the service time is only the mean service time. In this case, there is no chance to estimate parameters of the service time distribution and assumption about exponential service time distribution is quite natural because it greatly simplifies the mathematical analysis. If the detailed statistics about the service time is available, more general distribution of service time can be suggested. The presented analysis could be more or less easily extended to the case of much more general phase type distribution (see [40]), which can be used to approximate many other distributions. However, in this case we meet the following difficulty. If service time distribution is exponential, it does not matter (from the point of view of the distribution of the number of customers in the system) in which busy server the service of nonpriority customer is interrupted. In case of phase type distribution, in situation when the service in some server should be terminated it is necessary to fix the rule of a choice of the concrete busy server in which service will be terminated; for example, the phase of the service at this server should belong to some fixed group of phases. The question of justification of a fixed rule is quite complicated. If this question will be answered, the problem of analysis of the corresponding queueing model can be solved by analogy with presented above analysis, but the dimension of the blocks of generator of the Markov chain, which describes behavior of the system, catastrophically increases with increase of the number of phases and (or) servers due to necessity of taking into account the current phase of service in each busy server or the number of servers providing currently the service at each phase. Solution of this problem may be simplified by means of a proper use of methodology by D. Lucantoni and V. Ramaswami by analogy with, for example, [44] or more involved methodology from [45].In this paper we assumed that the service time distribution for both types of customers is exponential. This is rather restrictive assumption. But it is worth to note that in many practical situations available information about the service time is only the mean service time. In this case, there is no chance to estimate the parameters of the service time distribution and the assumption about an exponential service time distribution is quite natural because it greatly simplifies the mathematical analysis. If the detailed statistics about the service time is available, more general distributions of service time can be suggested. The presented analysis could be more or less easily extended to the case of much more general phase type distribution (see [40]) which can be used to approximate many other distributions. However, in this case we meet the following difficulty. If the service time distribution is exponential, it does not matter in which busy server service of nonpriority customer is interrupted. In the case of phase type distribution, in the situation when service in some server should be terminated it is necessary to fix the rule of a choice of the concrete busy server in which service will be terminated; for example, the phase of service at this server should belong to some fixed group of phases. The question of justification of the fixed rule is quite complicated. If this question will be answered, the problem of analysis of the corresponding queueing model can be solved by analogy with presented above analysis, but the dimension of the blocks of generator of the Markov chain, which describes the behavior of the system, catastrophically increases with increase of the number of phases and (or) servers due to necessity of taking into account the current phase of service in each busy server or the number of servers providing currently service at each phase. Solution of this problem may be simplified by means of a proper use of methodology by D. Lucantoni and V. Ramaswami by analogy with, for example, [44] or more involved methodology from [45].



---

*Source: 813150-2014-11-30.xml*