# Study on the Departure Process of Discrete-TimeGeo/G/1 Queue with Randomized Vacations

Authors: Chuanyi Luo; Xiaoying Huang; Chuan Ding
Journal: Discrete Dynamics in Nature and Society
 (2014)

---

## Abstract

This paper presents an analysis of the departure process of a discrete-timeG
e
o
/
G
/
1 queue
with randomized vacations. By using probability decomposition techniques and renewal process, the
expression of expected number of departures during time interval (
0
+
,
n
+
] is derived. The relation
among departure process, server state process, and service renewal process is obtained. The relation
displays the decomposition characteristic of the departure process. Furthermore, the approximate
expansion of the expected number of departures is gained. Since the departure process also often
corresponds to an arrival process for a downstream queue in queueing network, it is hoped that the
results obtained in this paper may provide useful information for queueing network.


---

## Body

## 1. Introduction

Since discrete-time queues with vacation schedule are more suitable for its applicability in the performance analysis of telecommunication systems, it has gained extended attention. For an excellent survey of earlier works on vacation models as well as its applications, interested readers can refer to [1–5]. Keilson and Servi (1986) [6] introduced another type of important vacation—Bernoulli vacations in which, after each service completion, the server takes a vacation with probability p or continues its busy period (if there are customers in the system) with probability 1
-
p. Following the work of Keilson and Servi, much further research on queueing system with Bernoulli vacations was done in [7–10]. On this base, Ke and Chu (2006) [11] develop an interesting vacation discipline from actual situation, where the server takes at most J vacations repeatedly until at least one customer is found waiting in the queue upon the server returns from a vacation. In the subsequent research of [12–14], Ke and Huang extend the vacation discipline to the randomized vacation policy with at most J vacations where the server takes another vacation with probability p or remains dormant within the system with probability 1
-
p if no customer is found waiting in the queue while the server returns from a vacation; otherwise, the server starts to serve the customers immediately if there are some customers waiting for service at the end of the vacation. This pattern does not terminate until the server has taken J successive vacations. Wang (2010) [15] and Wang et al. (2011) [16] introduce the randomized vacation policy to the discrete-time G
e
o
/
G
/
1 queue. Such a modified vacation discipline has potentially applications in practical systems [13], for example, in some stochastic production and inventory control systems such as production to orders.This is a continuation of work by Wang et al.(2011) [16] and Luo et al. (2013) [17] where they study the queue size distribution for G
e
o
/
G
/
1 with randomized vacation and at most J vacations by using different methods, respectively. Instead of studying the queue size distribution studied in [16, 17], this paper considers another theme—the departure process in that discrete-time model. The investigation of departure process in a queueing system is primarily motivated by the need to analyze queueing network models, in which the departure process of an upstream queue is the arrival process of the downstream queue. Burke (1956) [18] has proven that the departure process of a M
/
M
/
s queue is a Bernoulli process. However, it is also well known that if one goes beyond the exponential assumption, unfortunately, the departure process does not become renewal and no exact results of departure process are known for FCFS models. Motivated by the applications of queueing networks in manufacturing and communications, most of researchers adopt approximate method; for example, Whitt (1983) [19] proposes a two-moment theory by approximating the process involved by renewal processes; Harrison and Dai (1989) [20] approximate the queueing network model by a Brownian network which they then solve exactly; Zhang et al. (2005) [21] derive the departure process approximations via an exact aggregate solution technique (called ETAQA); Ferng and Chang (2000) [22] obtain the factorial moments and lag n covariance of interdeparture times by proposing a matrix-analytic approach; and so forth.As far as we know, most of the previous works characterize the departure process by paying close attention to interdeparture times. In this paper, being different from the previous works, we aim at the transient departure number during an arbitrary time interval(
0
+
,
n
+
]. Our objective is to present a distinctive analysis of departure process for the discrete-time queue, obtain the transient expression (z-transformation) for expected number of departures during the interval (
0
+
,
n
+
], and subsequently discover the decomposition characteristic of the departure process.The remainder of the paper is organized as follows. Section2 presents the description of the model. Section 3 derives the transient expression for the server busy probability at arbitrary epoch n
+ by using z-transformation. Section 4 gives the transient expression (z-transformation) for the expected number of departures during the arbitrary interval (
0
+
,
n
+
], denoted by M
i
(
n
+
). Section 5 gains the approximate expansion of M
i
(
n
+
). Finally, conclusions are given in Section 7.


## 2. Model Description

Consider a discrete-timeG
e
o
/
G
/
1 queue with randomized vacations. It is assumed that a potential customer arrives in system during time interval (
n
-
,
n
) and a potential departure takes place during time interval (
n
,
n
+
) (LAS-DA) and the input of customers is a Bernoulli process with parameter λ
(
0
<
λ
<
1
). Denoting the interarrival time by τ, then P
{
τ
=
j
}
=
λ
(
1
-
λ
)
j
-
1, j
≥
1. Customers are served according to FCFS discipline and the service times for an accepted customer, denoted by χ, are independent and identically distributed (i.i.d.) random variables with common probability mass function (p.m.f.) g
j
=
P
{
χ
=
j
}, j
≥
1, probability generating function (P.G.F.) G
(
z
)
=
∑
j
=
1
∞
g
j
z
j, and mean service time E
[
χ
]
=
α. After all the customers in the queue are served exhaustively, the server operates a randomized vacation policy with at most J vacations. As soon as the system becomes empty, the server immediately takes a vacation, denoted by V, with p.m.f. v
j
=
P
{
V
=
j
}, j
≥
1 and P.G.F. v
(
z
). If there is no customer in the system when the server returns from the vacation, the server takes another vacation with probability θ or remains dormant within the system with probability θ
-
=
1
-
θ. Otherwise, the server starts to serve the customers immediately if there are some customers waiting for service at the end of vacation. This pattern repeats until the server has taken J successive vacations. If the system remains empty at the end of the Jth vacation, the server keeps idle in the system until a next customer arrives, who evokes immediately service for the arrival. Furthermore, various stochastic processes involved in the system are assumed to be mutually independent. To make it clear, the various time epochs at which events occur are shown in a self-explanatory figure (see Figure 1).Figure 1
Various time epochs in a late arrival system with delayed access (LAS-DA).


## 3. Server Busy Probability at an Arbitrary Epochn
+

Denoting byb the length of server busy period evoked by only one customer with P.G.F. B
(
z
), then it follows the lemma which is also obtained by Bruneel and Kim (1993) [1].Lemma 1.
InG
e
o
/
G
/
1 queue, for |
z
|
<
1, B
(
z
) is the root of the following equation:
(1)
B
(
z
)
=
G
[
z
-
z
λ
(
1
-
B
(
z
)
)
]
,
E
[
b
]
=
α
1
-
ρ
,
ρ
<
1
,
where ρ
=
λ
α.
Letb
<
i
> be the length of server busy period evoked by i customers; thus b
<
i
> can be expressed as b
<
i
>
=
∑
v
=
1
i
b
v, where b
1
,
b
2
,
…
,
b
i are independent of each other and have the identical distribution as b. So the P.G.F. of b
<
i
> is given by B
i
(
z
).
Denote byN
(
n
+
) the queue length at arbitrary epoch n
+. Let ξ
(
n
+
)
=
1 be the server busy state; that is, the server is busy at epoch n
+. Define A
i
(
n
+
)
=
P
{
ξ
(
n
+
)
=
1
∣
N
(
0
+
)
=
i
} with z-transform a
i
(
u
)
=
∑
n
=
0
∞
A
i
(
n
+
)
u
n, |
u
|
<
1; thus the following expression of a
i
(
u
) holds.Theorem 2.
InG
e
o
/
G
/
1 queue with randomized vacations, for |
u
|
<
1 and i
≥
1, one has
(2)
a
0
(
u
)
=
(
(
1
-
λ
-
u
)
[
1
-
(
θ
v
(
λ
-
u
)
)
J
]
i
i
i
i
i
i
×
[
v
(
u
)
-
v
(
λ
u
B
(
u
)
+
λ
-
u
)
]
i
i
i
i
i
i
+
λ
u
(
1
-
B
(
u
)
)
·
y
(
u
)
(
1
-
λ
-
u
)
[
1
-
(
θ
v
(
λ
-
u
)
)
J
]
)
×
(
(
1
-
u
)
[
(
1
-
λ
-
u
)
·
x
(
u
)
-
λ
u
B
(
u
)
·
y
(
u
)
]
)
-
1
,
a
i
(
u
)
=
1
-
B
i
(
u
)
1
-
u
+
B
i
(
u
)
·
a
0
(
u
)
,
and conditioning on ρ
<
1, the steady state probability is given by
(3)
lim
⁡
n
→
∞
A
0
(
n
+
)
=
lim
⁡
n
→
∞
A
i
(
n
+
)
=
ρ
,
where
(4)
x
(
u
)
=
1
-
θ
v
(
λ
-
u
)
-
[
1
-
(
θ
v
(
λ
-
u
)
)
J
]
[
v
(
λ
u
B
(
u
)
+
λ
-
u
)
-
v
(
λ
-
u
)
]
y
(
u
)
=
(
1
-
θ
)
v
(
λ
-
u
)
+
[
θ
v
(
λ
-
u
)
]
J
[
1
-
v
(
λ
-
u
)
]
.Proof.
In consideration that the input process is Bernoulli process, the ending points of a server busy period and a vacation are all renewal points and the system is going between server busy state and unoccupied state (vacation state or potential server idle state). To derive the expressions ofa
i
(
u
), the following notations are introduced:
(5)
S
m
=
∑
k
=
1
m
‍
τ
k
,
S
0
=
0
,
V
<
i
>
=
∑
k
=
1
i
‍
V
k
,
V
<
0
>
=
0
,
where τ
1
,
τ
2
,
…
,
τ
m denote the interarrival times of the Bernoulli process with rate λ. V
1
,
V
2
,
…
,
V
i represent the vacations which are i.i.d. random variables with the same distribution as V. By using renewal process theory and techniques of probability decomposition, it gets
(6)
A
0
(
n
+
)
=
P
{
ξ
(
n
+
)
=
1
∣
N
(
0
+
)
=
0
}
=
P
{
τ
≤
n
+
;
ξ
(
n
+
)
=
1
}
=
∑
i
=
1
J
‍
P
{
τ
≤
n
+
;
ξ
(
n
+
)
=
1
;
V
<
i
-
1
>
<
τ
≤
V
<
i
>
}
iiiiiiiiiiiiiiii
+
P
{
ξ
(
n
+
)
=
1
;
τ
≤
n
+
;
V
<
J
>
<
τ
}
=
∑
i
=
1
J
‍
θ
i
-
1
P
{
ξ
(
n
+
)
=
1
;
V
<
i
>
≤
n
+
;
V
<
i
-
1
>
<
τ
≤
V
<
i
>
}
+
∑
i
=
2
J
‍
θ
i
-
2
(
1
-
θ
)
P
{
ξ
(
n
+
)
=
1
;
τ
≤
n
+
;
V
<
i
-
1
>
<
τ
}
+
θ
J
-
1
∑
i
=
1
n
‍
P
{
τ
=
i
}
P
{
V
<
J
>
<
i
}
·
A
1
(
(
n
-
i
)
+
)
.
In the first item of (6), the “V
<
i
>
≤
n
+
;
V
<
i
-
1
>
<
τ
≤
V
<
i
>” means that the epoch n locates behind the ith vacation and the first customer arrives in system during the ith vacation. So there would be some other potential customers arriving during the time interval [
τ
,
V
<
i
>
]. As a result, the first item of (6) is equal to
(7)
∑
i
=
1
J
‍
θ
i
-
1
∑
m
=
1
∞
‍
P
{
ξ
(
n
+
)
=
1
;
V
<
i
>
≤
n
+
;
V
<
i
-
1
>
<
τ
;
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
τ
+
S
m
-
1
≤
V
<
i
>
<
τ
+
S
m
}
=
∑
i
=
1
J
‍
θ
i
-
1
∑
m
=
1
∞
‍
P
{
ξ
(
n
+
)
=
1
;
V
<
i
>
≤
n
+
;
V
<
i
-
1
>
<
τ
;
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
(
τ
-
V
<
i
-
1
>
)
+
S
m
-
1
≤
V
iiiiiiiiiiiiiiiiiiiiiiiiiiiiii
<
(
τ
-
V
<
i
-
1
>
)
+
S
m
}
=
∑
i
=
1
J
‍
θ
i
-
1
∑
m
=
1
∞
‍
∑
k
=
i
-
1
n
‍
P
{
V
<
i
-
1
>
=
k
}
×
∑
l
=
1
n
-
k
‍
P
{
V
=
l
}
·
P
{
τ
>
k
}
(
l
m
)
λ
m
λ
-
l
-
m
iiiiiiiiiiiiiiiiiiiii
·
A
m
(
(
n
-
k
-
l
)
+
)
.
One should note that the item of “(
τ
-
V
<
i
-
1
>
)” in the above equation represents the remaining interarrival time at the ending epoch of the (
i
-
1
)th vacation. Based on the “lack of memory property” of the Bernoulli process, the “(
τ
-
V
<
i
-
1
>
)” has the same distribution as τ under the condition of V
<
i
-
1
>
=
k
(
k
=
i
-
1
,
i
,
…
).
The second item of (6) is given by
(8)
∑
i
=
2
J
‍
θ
i
-
2
(
1
-
θ
)
∑
k
=
1
n
‍
P
{
τ
=
k
}
P
{
V
<
i
-
1
>
<
k
}
·
A
1
(
(
n
-
k
)
+
)
.
Multiplying (6) by u
n and summing over n after substituting (7) and (8) into (6) gain
(9)
a
0
(
u
)
=
1
-
[
θ
v
(
λ
-
u
)
]
J
1
-
θ
v
(
λ
-
u
)
·
∑
m
=
1
∞
‍
∑
l
=
1
m
‍
P
{
V
=
m
}
u
m
(
m
l
)
λ
l
λ
-
m
-
l
a
l
(
u
)
iiiiiiiiiiiiiiiii
+
a
1
(
u
)
·
λ
u
(
1
-
θ
)
v
(
λ
-
u
)
1
-
λ
-
u
iiiiiiiiiiiiiiiii
·
1
-
[
θ
v
(
λ
-
u
)
]
J
-
1
1
-
θ
v
(
λ
-
u
)
iiiiiiiiiiiiiiiii
+
a
1
(
u
)
·
λ
u
·
θ
J
-
1
[
v
(
λ
-
u
)
]
J
1
-
λ
-
u
.
For 1
≤
i, it gets
(10)
A
i
(
n
+
)
=
P
{
ξ
(
n
+
)
=
1
;
b
<
i
>
>
n
+
}
+
P
{
ξ
(
n
+
)
=
1
;
b
<
i
>
≤
n
+
}
=
1
-
∑
k
=
i
n
‍
P
{
b
<
i
>
=
k
}
+
∑
k
=
i
n
‍
P
{
b
<
i
>
=
k
}
A
0
(
(
n
-
k
)
+
)
.
Multiplying (10) by u
n and summing over n yield
(11)
a
i
(
u
)
=
1
-
B
i
(
u
)
1
-
u
+
B
i
(
u
)
·
a
0
(
u
)
.
Solving the simultaneous equations (9) and (11) leads to the expression of a
i
(
u
) provided in Theorem 2.
Applying the Final Value Theorem (see [23]), it has lim
⁡
n
→
∞
A
i
(
n
+
)
=
lim
⁡
u
→
1
-
(
1
-
u
)
·
a
i
(
u
). By using Lemma 1, the stable result of A
i
(
n
+
) given in Theorem 2 is obtained.Remark 3.
By assumingP
{
V
=
0
}
=
1, the model considered here becomes a special case where the vacation disappears. We can easily derive the corresponding expression of a
i
(
u
) in classical G
e
o
/
G
/
1 queueing model without vacation policy. Consider the following:
(12)
a
0
(
u
)
=
λ
u
(
1
-
B
(
u
)
)
(
1
-
u
)
[
(
1
-
λ
-
u
)
-
λ
u
B
(
u
)
]
,
a
i
(
u
)
=
1
-
B
i
(
u
)
1
-
u
+
B
i
(
u
)
·
a
0
(
u
)
,
lim
⁡
n
→
∞
A
0
(
n
+
)
=
lim
⁡
n
→
∞
A
i
(
n
+
)
=
ρ
.
One may note here that the steady state of A
0
(
n
+
) has nothing to do with the vacation policy.


## 4. Expected Number of Departures during the Arbitrary Time Interval(
0
+
,
n
+
]

Consider a renewal process driven by a list of service times{
χ
i
,
i
≥
1
} defined in Section 1. Let
(13)
U
n
=
∑
i
=
1
n
‍
χ
i
,
U
0
=
0
,
D
(
n
+
)
=
sup
⁡
⁡
{
n
:
U
n
≤
n
+
}
.
Thus, D
(
n
+
) is a renewal process and denotes the number of departures during time interval (
0
+
,
n
+
] contained in the service process {
χ
i
,
i
≥
1
}. Let M
(
n
+
)
=
E
[
D
(
n
+
)
] be the renewal function of D
(
n
+
) with z-transform m
(
u
)
=
∑
n
=
0
∞
M
(
n
+
)
u
n.Lemma 4.
For|
u
|
<
1, it has
(14)
m
(
u
)
=
G
(
u
)
(
1
-
u
)
[
1
-
G
(
u
)
]
,
lim
⁡
n
→
∞
M
(
n
+
)
n
=
1
α
,
where G
(
u
) is the P.G.F. of distribution of service time {
χ
i
,
i
≥
1
} and α
=
E
[
χ
i
].Proof.
One has(15)
M
(
n
+
)
=
E
[
D
(
n
+
)
]
=
∑
k
=
0
∞
‍
k
P
{
D
(
n
+
)
=
k
}
=
∑
k
=
0
∞
‍
k
P
{
χ
1
+
⋯
+
χ
k
≤
n
+
<
χ
1
+
⋯
+
χ
k
+
1
}
=
∑
k
=
0
∞
‍
∑
m
=
k
n
‍
k
P
{
χ
1
+
⋯
+
χ
k
=
m
}
P
{
χ
k
+
1
>
(
n
-
m
)
+
}
.
Taking z-transform on both sides of the above equation yields the expression of m
(
u
). Applying the essential renewal theorem (see [24]), it gets
(16)
lim
⁡
n
→
∞
M
(
n
+
)
n
=
1
E
[
χ
i
]
=
1
α
.
On this basis, we begin to consider the expected number of departures during an arbitrary time interval(
0
+
,
n
+
] in the queue system. For this aim, some additional notations are developed as follows:
(17)
D
-
(
n
+
)
=
{
The number of departures during
iiiiii
general time interval
(
0
+
,
n
+
]
}
,
M
i
(
n
+
)
=
E
[
D
-
(
n
+
)
∣
N
(
0
+
)
=
i
]
,
n
,
i
≥
0
.
So, M
i
(
n
+
) represents the expected departures during (
0
+
,
n
+
] with the initial state of N
(
0
+
)
=
i. One has the following:
(18)
T
i
(
n
+
)
=
E
{
The number of departures during
i
i
i
i
i
i
i
(
0
+
,
b
<
i
>
]
;
b
<
i
>
≤
n
+
}
,
W
i
(
n
+
)
=
E
{
The number of departures during
i
i
i
i
i
i
i
(
0
+
,
n
+
]
;
b
<
i
>
>
n
+
}
,
i
=
1,2
,
…
,
t
i
(
u
)
=
∑
n
=
0
∞
‍
T
i
(
n
+
)
u
n
,
w
i
(
u
)
=
∑
n
=
0
∞
‍
W
i
(
n
+
)
u
n
,
where b
<
i
> denotes the length of a server busy period evoked by i customers waiting for service.Theorem 5.
Letm
i
(
u
)
=
∑
n
=
0
∞
M
i
(
n
+
)
u
n, for |
u
|
<
1, ρ
<
1, and i
≥
0; it has
(19)
m
i
(
u
)
=
m
(
u
)
·
(
1
-
u
)
a
i
(
u
)
,
lim
⁡
n
→
∞
M
i
(
n
+
)
n
=
{
λ
,
ρ
<
0
1
α
,
ρ
≥
1
,
where a
i
(
u
) and m
(
u
) are determined by Theorem 2 and Lemma 4, respectively.Proof.
Since the arrival process is Bernoulli process, the beginning and ending epochs of a server busy period or a vacation are both renewal points. Thus, it can take probability decomposition techniques onM
(
n
+
) by using b
<
i
>. Consider
(20)
M
(
n
+
)
=
E
[
D
(
n
+
)
]
=
E
[
D
(
n
+
)
;
b
<
i
>
>
n
+
]
+
E
[
D
(
n
+
)
;
b
<
i
>
≤
n
+
]
=
W
i
(
n
+
)
+
E
[
D
(
b
<
i
>
)
;
b
<
i
>
≤
n
+
]
+
∑
k
=
i
n
‍
P
{
b
<
i
>
=
k
}
E
[
D
(
(
n
-
k
)
+
)
]
=
W
i
(
n
+
)
+
T
i
(
n
+
)
+
∑
k
=
i
n
‍
P
{
b
<
i
>
=
k
}
M
(
(
n
-
k
)
+
)
.
Taking z-transform on both sides of the above equation and applying Lemma 4 give
(21)
t
i
(
u
)
+
w
i
(
u
)
=
[
1
-
B
i
(
u
)
]
G
(
u
)
(
1
-
u
)
[
1
-
G
(
u
)
]
.
For M
0
(
n
+
), by using the same method used for the solution of a
i
(
u
)
(
i
≥
0
), it gets
(22)
M
0
(
n
+
)
=
E
[
D
-
(
n
+
)
∣
N
(
0
+
)
=
0
]
=
E
[
D
-
(
n
+
)
;
τ
≤
n
+
]
=
∑
i
=
1
J
‍
E
[
D
-
(
n
+
)
;
τ
≤
n
+
;
V
<
i
-
1
>
<
τ
≤
V
<
i
>
]
iiiiiiiii
+
E
[
D
-
(
n
+
)
;
τ
≤
n
+
;
V
<
J
>
<
τ
]
=
∑
i
=
1
J
‍
θ
i
-
1
E
[
D
-
(
n
+
)
;
V
<
i
>
≤
n
+
;
V
<
i
-
1
>
<
τ
≤
V
<
i
>
]
+
∑
i
=
2
J
‍
θ
i
-
2
(
1
-
θ
)
E
[
D
-
(
n
+
)
;
τ
≤
n
+
;
V
<
i
-
1
>
<
τ
]
+
θ
J
-
1
∑
i
=
1
n
‍
P
{
τ
=
i
}
P
{
V
<
J
>
<
i
}
·
M
1
(
(
n
-
i
)
+
)
=
∑
i
=
1
J
‍
θ
i
-
1
∑
m
=
1
∞
‍
∑
k
=
i
-
1
n
‍
P
{
V
<
i
-
1
>
=
k
}
×
∑
l
=
1
n
-
k
‍
P
{
V
=
l
}
·
P
{
τ
>
k
}
(
l
m
)
λ
m
λ
-
l
-
m
iiiiiiiiiiii
·
M
m
(
(
n
-
k
-
l
)
+
)
+
∑
i
=
2
J
‍
θ
i
-
2
(
1
-
θ
)
×
∑
k
=
1
n
‍
P
{
τ
=
k
}
P
{
V
<
i
-
1
>
<
k
}
iiiiiiiiiiiiii
·
M
1
(
(
n
-
k
)
+
)
+
θ
J
-
1
×
∑
i
=
1
n
‍
P
{
τ
=
i
}
P
{
V
<
J
>
<
i
}
·
M
1
(
(
n
-
i
)
+
)
.
Multiplying (22) by u
n and summing over n result in
(23)
m
0
(
u
)
=
1
-
[
θ
v
(
λ
-
u
)
]
J
1
-
θ
v
(
λ
-
u
)
·
∑
m
=
1
∞
‍
∑
l
=
1
m
‍
P
{
V
=
m
}
u
m
(
m
l
)
λ
l
λ
-
m
-
l
m
l
(
u
)
iiiiiiiiiiiiiii
+
m
1
(
u
)
·
λ
u
(
1
-
θ
)
v
(
λ
-
u
)
1
-
λ
-
u
iiiiiiiiiiiiiii
·
1
-
[
θ
v
(
λ
-
u
)
]
J
-
1
1
-
θ
v
(
λ
-
u
)
+
m
1
(
u
)
iiiiiiiiiiiiiii
·
λ
u
·
θ
J
-
1
[
v
(
λ
-
u
)
]
J
1
-
λ
-
u
.
For M
i
(
n
+
)
(
i
≥
1
), it has
(24)
M
i
(
n
+
)
=
E
[
D
-
(
n
+
)
∣
N
(
0
+
)
=
i
]
=
E
[
D
-
(
n
+
)
;
n
+
<
b
<
i
>
]
+
E
[
D
-
(
n
+
)
;
b
<
i
>
≤
n
+
]
=
W
i
(
n
+
)
+
E
{
The number of departures during
(
0
+
,
b
<
i
>
]
;
b
<
i
>
≤
n
+
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
(
0
+
,
b
<
i
>
]
;
b
<
i
>
≤
n
+
}
+
E
{
The number of departures during
(
0
+
,
b
<
i
>
]
;
b
<
i
>
≤
n
+
i
i
i
i
i
i
i
i
i
i
(
b
<
i
>
,
n
+
]
;
b
<
i
>
≤
n
+
}
=
W
i
(
n
+
)
+
T
i
(
n
+
)
+
∑
k
=
i
n
‍
P
{
b
<
i
>
=
k
}
M
0
(
(
n
-
k
)
+
)
.
Taking z-transform on both sides of (24) and applying (21) yield
(25)
m
i
(
u
)
=
[
1
-
B
i
(
u
)
]
G
(
u
)
(
1
-
u
)
[
1
-
G
(
u
)
]
+
B
i
(
u
)
m
0
(
u
)
.
Solving the simultaneous equations (23) and (25), it gets the expression of m
i
(
u
)
(
i
≥
0
). From the expressions of m
i
(
u
)
(
i
≥
0
) given here, a
i
(
u
)
(
i
≥
0
) given by Theorem 2, and m
(
u
) given by Lemma 4, the relation among m
i
(
u
),m
(
u
), and a
i
(
u
) is established as follows:
(26)
m
i
(
u
)
=
m
(
u
)
·
(
1
-
u
)
a
i
(
u
)
.
Applying Theorem 2 and Lemma 4, when condition ρ
<
1 holds, it has the following steady result:
(27)
lim
⁡
n
→
∞
M
i
(
n
+
)
n
=
lim
⁡
u
→
1
-
(
1
-
u
)
2
m
i
(
u
)
=
lim
⁡
u
→
1
-
(
1
-
u
)
2
m
(
u
)
·
lim
⁡
u
→
1
-
(
1
-
u
)
a
i
(
u
)
=
lim
⁡
n
→
∞
M
(
n
+
)
n
·
lim
⁡
n
→
∞
A
(
n
+
)
=
{
1
α
·
ρ
=
λ
,
ρ
<
0
1
α
·
1
,
ρ
≥
1
.
Thus, it finishes the proof of Theorem 5.Remark 6.
Conditioning onP
{
V
=
0
}
=
1, we can obtain the expected number of departures during an arbitrary time interval (
0
+
,
n
+
] in classical G
e
o
/
G
/
1 queue without vacation. Therefore
(28)
m
0
(
u
)
=
m
(
u
)
·
(
1
-
u
)
a
0
(
u
)
=
G
(
u
)
(
1
-
u
)
[
1
-
G
(
u
)
]
·
λ
u
(
1
-
B
(
u
)
)
(
1
-
λ
-
u
)
-
λ
u
B
(
u
)
,
m
i
(
u
)
=
m
(
u
)
·
(
1
-
u
)
a
i
(
u
)
=
G
(
u
)
(
1
-
u
)
[
1
-
G
(
u
)
]
·
[
1
-
B
i
(
u
)
1
-
u
+
B
i
(
u
)
·
a
0
(
u
)
]
,
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
≥
1
.
lim
⁡
n
→
∞
M
i
(
n
+
)
n
=
{
1
α
·
ρ
=
λ
,
ρ
<
0
,
1
α
·
1
,
ρ
≥
1
.


## 5. Approximate Expansion of the Expected Number of Departures during(
0
+
,
n
+
]

In spite of the closed-form formula form
i
(
u
) given by Theorem 5, it seems impossible to get the expected departure number during time interval (
0
+
,
n
+
] (M
i
(
n
+
)) by operating inverse z-transform of m
i
(
u
). For the convenient calculation of M
i
(
n
+
), it is pretty necessary to conduct the approximate expansion of M
i
(
n
+
). Firstly, we give Lemma 7 as follows.Lemma 7.
ForE
[
χ
i
2
]
<
+
∞ and n
→
+
∞, the following approximate expansion of M
(
n
+
) holds
(29)
M
(
n
+
)
-
n
α
≈
E
[
χ
i
2
]
+
α
2
α
2
-
1
,
where {
χ
i
,
i
≥
1
} are service times and α
=
E
[
χ
i
].Proof.
LetS
D
(
n
+
)
+
1
=
∑
i
=
1
D
(
n
+
)
+
1
χ
i; thus S
D
(
n
+
)
+
1 denotes the epoch immediately after the (
D
(
n
+
)
+
1
)th service completion. Denote by X
(
n
+
) the remain service time of a customer being served at epoch n
+ with the corresponding steady state X
+
=
lim
⁡
n
→
∞
X
(
n
+
) and the steady state distribution x
i
=
P
{
X
+
=
i
}, i
≥
1, which has P.G.F. X
*
(
u
)
=
∑
i
=
1
∞
x
i
u
i. From [25], it has
(30)
X
*
(
u
)
=
u
[
1
-
G
(
u
)
]
α
(
1
-
u
)
,
E
[
X
+
]
=
d
X
*
(
u
)
d
u
|
u
=
1
=
E
[
χ
i
2
]
+
α
2
α
.
Since S
D
(
n
+
)
+
1
=
n
+
X
(
n
+
), E
[
S
D
(
n
+
)
+
1
]
=
n
+
E
[
X
(
n
+
)
],
that is,(31)
E
[
∑
i
=
1
D
(
n
+
)
+
1
‍
χ
k
]
=
n
+
E
[
X
(
n
+
)
]
,
E
[
χ
i
]
(
E
[
D
(
n
+
)
]
+
1
)
=
n
+
E
[
X
(
n
+
)
]
,
α
[
M
(
n
+
)
+
1
]
=
n
+
E
[
X
(
n
+
)
]
,
M
(
n
+
)
-
n
α
=
E
[
X
(
n
+
)
]
α
-
1
,
lim
⁡
n
→
∞
[
M
(
n
+
)
-
n
α
]
=
E
[
X
+
]
α
-
1
=
E
[
χ
i
2
]
+
α
2
α
2
-
1
.
Therefore, conditioning on E
[
χ
i
2
]
<
+
∞ and n
→
+
∞, Lemma 7 holds. Now the approximate expansion of M
i
(
n
+
) can be derived by the following theorem.Theorem 8.
ForE
[
χ
i
2
]
<
+
∞ and ρ
<
1, when n
→
+
∞, one has
(32)
M
i
(
n
+
)
≈
{
λ
n
+
ρ
[
E
[
χ
i
2
]
+
α
2
α
2
-
1
]
,
ρ
<
0
,
n
α
+
E
[
χ
i
2
]
+
α
2
α
2
-
1
,
ρ
≥
1
,
where α
=
E
[
χ
i
].Proof.
LetQ
(
n
+
)
*
R
(
n
+
)
=
∑
k
=
0
n
Q
(
k
+
)
*
R
(
(
n
-
k
)
+
) be the fold product of Q
(
n
+
) and R
(
n
+
). Let q
(
u
)
=
Z
[
Q
(
n
+
)
]
=
∑
n
=
0
∞
Q
(
n
+
)
u
n denote the z-transform of Q
(
n
+
); then Z
[
Q
(
n
+
)
*
R
(
n
+
)
]
=
Z
[
Q
(
n
+
)
]
·
Z
[
R
(
n
+
)
]
=
q
(
u
)
·
r
(
u
). Denote the converse z-transform of image function q
(
u
) by Z
-
1
[
q
(
u
)
]
=
Q
(
n
+
). Applying Theorem 5 along with the limitation theory and the properties of z-transform (see [23]), it gets
(33)
lim
⁡
n
→
+
∞
(
M
i
(
n
+
)
-
A
i
(
n
+
)
*
Z
-
1
[
(
1
-
u
)
Z
(
n
α
)
]
)
=
lim
⁡
u
→
1
-
(
1
-
u
)
Z
[
M
i
(
n
+
)
-
A
i
(
n
+
)
[
(
1
-
u
)
Z
(
n
α
)
]
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
*
Z
-
1
[
(
1
-
u
)
Z
(
n
α
)
]
]
=
lim
⁡
u
→
1
-
(
1
-
u
)
[
m
i
(
u
)
-
(
1
-
u
)
Z
(
n
α
)
·
Z
[
A
i
(
n
+
)
]
]
=
lim
⁡
u
→
1
-
(
1
-
u
)
[
(
1
-
u
)
a
i
(
u
)
m
(
u
)
(
n
α
)
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
-
(
1
-
u
)
Z
(
n
α
)
a
i
(
u
)
]
=
lim
⁡
u
→
1
-
(
1
-
u
)
a
i
(
u
)
[
(
1
-
u
)
m
(
u
)
-
(
1
-
u
)
Z
(
n
α
)
]
=
lim
⁡
u
→
1
-
(
1
-
u
)
a
i
(
u
)
lim
⁡
u
→
1
-
[
(
1
-
u
)
m
(
u
)
(
n
α
)
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
-
(
1
-
u
)
Z
(
n
α
)
]
=
lim
⁡
n
→
∞
A
i
(
n
+
)
lim
⁡
n
→
∞
[
M
(
n
+
)
-
n
α
]
=
ρ
[
E
[
χ
i
2
]
+
α
2
α
2
-
1
]
.
Note that the final conclusion in (33) is based on Theorem 2 and (31).
Since(34)
lim
⁡
n
→
+
∞
A
i
(
n
+
)
*
Z
-
1
[
(
1
-
u
)
Z
(
n
/
α
)
]
n
=
lim
⁡
u
→
1
-
(
1
-
u
)
2
Z
[
A
i
(
n
+
)
*
Z
-
1
[
(
1
-
u
)
Z
(
n
α
)
]
]
=
lim
⁡
n
→
+
∞
(
1
-
u
)
a
i
(
u
)
(
1
-
u
)
2
Z
(
n
α
)
=
lim
⁡
n
→
+
∞
A
i
(
n
+
)
·
lim
⁡
n
→
+
∞
n
/
α
n
=
ρ
·
1
α
,
when n
→
+
∞ holds, it has
(35)
A
i
(
n
+
)
*
Z
-
1
[
(
1
-
u
)
Z
(
n
α
)
]
≈
ρ
·
n
α
.
Substituting (35) into (33) yields
(36)
M
i
(
n
+
)
≈
A
i
(
n
+
)
*
Z
-
1
[
(
1
-
u
)
Z
(
n
α
)
]
+
ρ
[
E
[
χ
i
2
]
+
α
2
α
2
-
1
]
≈
{
λ
n
+
ρ
[
E
[
χ
i
2
]
+
α
2
α
2
-
1
]
,
ρ
<
1
,
n
α
+
E
[
χ
i
2
]
+
α
2
α
2
-
1
,
ρ
≥
1
.


## 6. A Numerical Experiment

Based on Theorem8 given above, the expected departure number can be calculated easily. It is one of the main distinctive highlights in the work. For showing this highlight, a numerical experiment concerning the calculation for expected departure number (M
i
(
n
+
)) is carried out here to illustrate the effect of arrival rate (λ) and time interval ((
0
+
,
n
+
]) on the expected departure number (see Figure 2).Figure 2
Effect of arrival rate and time interval on expected departure number.In this numerical operation, some necessary parameters are taken as follows: the service time is arbitrarily distributed and the service rate is1
/
α
=
0.46; the top value of time interval (
0
+
,
n
+
] is valued from n
=
10 to n
=
99; the arrival process is a Bernoulli process and the arrival rate is determined in the range of λ
∈
[
0.1,0.99
] including the special case of ρ
≥
1.From Figure2, we can see the expected departure number is increasing as the length of time interval increases. It is also increasing when the customer improves the arrival rate until it edges up to the service rate 1
/
α. The expected departure number stops increasing and maintains being unchangeable when the arrival rate is greater than the service rate; that is, ρ
≥
1. This is because the server will stay in a busy state permanently conditioning on ρ
≥
1 and in this case the departure rate is just equal to the service rate.


## 7. Conclusions

By using probability decomposition techniques and renewal process, this paper presents an original analysis for the departure process in discrete-time queue with random vacation policy. It gains the following conclusions.(1)
The conclusionlim
⁡
n
→
∞
(
M
i
(
n
+
)
/
n
)
=
λ given by Theorem 5 shows that, conditioning on ρ
<
1, the expected number of departures per unit time (called departure rate) is identical with the input rate and has nothing to do with the service rate or server’s vacation policy.
(2)
From the relation given in Theorem5, that is, m
i
(
u
)
=
m
(
u
)
[
(
1
-
u
)
a
i
(
u
)
], one sees that the expected departure number is decomposed into two parts: one is the server busy probability (A
i
(
n
+
)), and another is the expected departure number during busy period. That is to say, the expected number of departures during arbitrary time interval (
0
+
,
n
+
] is affected by both the service rate and the length of busy period. Furthermore, from Theorems 2 and 5 and Lemma 4, it implies that this decomposition still holds under steady condition; that is,
(37)
lim
⁡
n
→
∞
M
i
(
n
+
)
n
=
lim
⁡
n
→
∞
M
(
n
+
)
n
·
lim
⁡
n
→
∞
A
i
(
n
+
)
=
1
α
·
ρ
.
Our further investigation indicates that this decomposition still holds in most of varieties of G
e
o
/
G
/
1 with exhaustive service.
(3)
The approximate expansion ofM
i
(
n
+
) given by Theorem 8 provides a valid method to calculate the expected departure number during arbitrary time interval (
0
+
,
n
+
].



---

*Source: 738021-2014-05-26.xml*