STEADY-STATE ANALYSIS OF THE GI/M/1 QUEUE WITH MULTIPLE VACATIONS AND SET-UP TIME

STEADY-STATE ANALYSIS OF THE GI/M/1 QUEUE WITH MULTIPLE VACATIONS AND

SET-UP TIME

ZHAO Guohui¹ DU Xinxin² TIAN Naishuo³ ZHAO Xiaohua⁴ ZHAO Dongmei⁵

Abstract: In this paper, we consider a GI/M/1 queueing model with multiple vacations and set-up time. We derive the distribution and the generating function and the stochastic decomposition of the steady-state queue length, meanwhile, we get the waiting time distributions.

Key words: multiple vacations, set-up time, stochastic decomposition

1 College of Science, Yanshan University, Qinhuangdao 066004, China.

E-mail: [email protected]

2College of Science, Yanshan University, Qinhuangdao 066004, China.

3College of Science, Yanshan University, Qinhuangdao 066004, China

4College of Science, Yanshan University, Qinhuangdao 066004, China

5College of Science, Yanshan University, Qinhuangdao 066004, China

* Received 28 February 2008; accepted 26 May 2008

INTRODUCTION

Vacation queues servers to stop the customers’ service at some periods, and the time during which the service is interrupted is called the vacation time. Vacation queue research originated from Levy and Yechial, then many researchers on queuing theory deal with this fields. So far, the theory frame whose core is the stochastic decomposition is developed and vacation queues have been applied successfully to many fields, such as computer systems, communication networking, flexible manufacture, electronic and call centers. Details can be seen in the surveys of Doshi and the monographs of Tian. For GI/M/1 type queues with server vacations, Tian used the matrix geometric solution method to analyze and obtained the expressions of the rate matrix and proved the stochastic decomposition properties for queue length and waiting time in a GI/M/1 vacation model with multiple exponential vacations. Using matrix-geometric approach, we give expressions of distributions for queue length at an arrival epoch and the steady-state distribution for the waiting time.

/Management Science and Engineering Vol.2 No.2 2008 36-42

1. DESCRIPTION OF THE MODEL

Consider a classical GI/M/1 queue, inter-arrival times are i.i.d.r.vs. Let

A ( x )

_and

a

^*

( s )

_{be the}

distribution function and L.S transform of the inter-arrival time

A

of customers. The mean inter-arrival

time is

′ =

−

= ( 0 ) )

(

A a^*

E

λ

⁻¹,Service times during service period, vacation times and set-up times are assumed to be exponentially distributed with rate

μ

_,

θ

_,

β

, respectively. We assume that the service discipline is FCFS.

Suppose

τ

_n be the arrival epoch of nth customers with

τ

₀=0. Let

L

_n

= L

_v

( τ

_n⁻

)

be the number of the customers before the nth arrival. Define

=

= (

_n

)

n

J

J τ

0, the nth arrival occurs during a service period, 1, the nth arrival occurs during a set - up period, 2, the nth arrival occurs during a vacation period.

⎧ ⎪

⎨ ⎪

⎩

The process

{ ( L

_n

, J

_n

), n ≥ 1 }

is a Markov chain with the state space

{ (0, 2) ( , ),

^{k j k}

1,

^j

0,1, 2 . }

Ω =

U

≥ =

Meanwhile, we introduce the expressions below

,

0 ),

! ( ) (

0

≥

=

^∞

∫

_k^{t e− dA t k}

a ^t

k k

μ

μ

[ ]

( )

0 0

( )

( ), 0,

!

t k

x t x

k

t x

b e e dxdA t k

k

β

μ

μ

∞

β

−

−

− −

= ∫∫ ≥

[ ]

( )

0 0 0

( )

( ), 0.

!

t y k t

x y t x y

k

t x y

c e e e dxdydA t k

k

θ β

μ

μ

θ β

−

∞

− −

− −

− − −

= ∫∫ ∫ ≥

First, the transition from

( , 0) i

to

( j , 0 )

occur if

i + 1 − j

services complete during an inter-arrival time. Therefore, we have

. 1 , , 1 , 1

1

,

) 0 , )(

0 ,

(

= a

₊₋

i ≥ j = i +

p

_{i j i j}

L

Similarly,

p

_{( ,1)( ,0)i j}

= b

_{i+ −1 j}

, i ≥ 1, j = 1, L , i + 1.

2

* 0

) 1 , 1 )(

1 ,

( ⁺

= ∫

^∞e−βdA

(

^t

) =

^a

( β ) = γ

p_{i i} ^t .

*

( ,2)( 1,2) 3

0

( ) ( )

t

i i

p

₊

=

^∞

∫ e−θdA t = a θ = γ . p( ,2)( ,0)i j = ci+ −1 j, i ≥ 0, j = 1, L , i + 1.

( )

( )

( ,2)( 1,1) 2 3

0 0

( ) ( ( ) ( )) ( )

t

x t x

i i

p

₊

=

^∞

∫∫ θ e−θ e−β − dA t = θ a∗ β − a∗ θ θ β − = α γ − γ .

The transition matrix of

( L J

_n

,

_n

)

can be written as the Block-Jacobi matrix

/Management Science and Engineering Vol.2 No.2 2008 36-42

⎥ ⎥

⎥ ⎥

⎥ ⎥

⎦

⎤

⎢ ⎢

⎢ ⎢

⎢ ⎢

⎣

⎡

=

O M M M M M

0 1 2 3 3

0 1 2 2

0 1 1

01 00

~

A A A A B

A A A B

A A B

A B P

where

B

₀₀

= − − 1 c

₀

α γ (

₂

− γ

₃

) − γ

₃,

A

₀₁

= ( , ( c

₀

α γ

₂

− γ γ

₃

),

₃

),

0

0 0 2

0 2 3 3

0 0

0 ,

( )

a

A b

c

γ

α γ γ γ

⎛ ⎞

⎜ ⎟

= ⎜ ⎟

⎜ − ⎟

⎝ ⎠

0 0

0 0 , 1

0 0

k

k k

k

a

A b k

c

⎛ ⎞

⎜ ⎟

= ⎜ ⎟ ≥

⎜ ⎟

⎝ ⎠

0

2 0

2 3 3

0

1

1 , 1,

1 ( ) )

k i i k

k i

i k

i i

a

B b k

c

γ α γ γ γ

=

=

=

⎛ − ⎞

⎜ ⎟

⎜ ⎟

⎜ ⎟

= ⎜ − − ⎟ ≥

⎜ ⎟

⎜ ⎟

− − − −

⎜ ⎟

⎝ ⎠

∑

∑

∑

The matrix

P ~

is a GI/M/1 type matrix.

2. STEADY-STATE DISTRIBUTION

Lemma1. If

ρ = λμ

⁻¹

< 1

,

θ

,

β

>0, then

δ > 0 , θβ δ ( ) 0.

θ β − − Δ >

where

) 1 ( ))

( 1 (

) (

2 2 1

*

* 1

γ μ β

γ γ β

μ β

β δ γ

−

−

= −

−

−

= −

a

a

，

*

1 3

1

*

3

( )

[1 ( )] (1 )

a a

γ γ

γ θ

θ μ θ θ μ γ

−

Δ = − =

− − − −

^{. (1)}

Theorem 1. If

ρ < 1

,

θ

,

β

>0, then the matrix equation _k

k k

A R R ∑∞

=

=

0

has the minimal non-negative solution

1

2

2 3 3

0 0

0

( ) ( )

R

γ

βδ γ

αβ δ α γ γ γ

⎛ ⎞

⎜ ⎟

= ⎜ ⎟

⎜ − Δ − ⎟

⎝ ⎠

where

γ

₁is the unique roots in the range

0 < <

z

1

of the equation z = a^*(

μ

(1− z)).

( )

α θ θ β = −

,

δ

and

Δ

are defined as in (1).

≥

/Management Science and Engineering Vol.2 No.2 2008 36-42

⎟ ⎟

⎟

⎠

⎞

⎜ ⎜

⎜

⎝

⎛

=

33 32 31

22 21 11

0 0 0

r r r

r r r R

we easily obtain

*

11 11 11 22 2 33 3

0

1 1

21 21 11 22 22 32 2 3

1 0 0

1 2 2

1 2

31 31 11 33 32 21 11 22 33

1 0 2 0 0

( (1 )), ,

, ( )

k k k

k

i k i k

k k

k i k

k k k i

i k i i j k i j

k k

k i k i j

r r a a r r r

r r r r a r b r

r r r r a r r r r r a

μ γ γ

α γ γ

∞

=

∞ − ∞

− −

= = =

∞ − ∞ − − −

− − − − −

= = = = =

= = − = =

⎛ ⎞

= ⎜ ⎝ ⎟ ⎠ + = −

⎛ ⎞

⎛ ⎞

= ⎜ ⎟ + ⎜ ⎟

⎝ ⎠ ⎝ ⎠

+

∑

∑ ∑ ∑

∑ ∑ ∑ ∑ ∑

1 1

32 22 33 33

1 0 0

k

i k i k

k k

k i k

r r r b r c

∞ − ∞

− −

= = =

⎧ ⎪

⎪ ⎪

⎪ ⎪

⎨ ⎪

⎪ ⎪

⎪ ⎛ ⎜ ⎞ + ⎟

⎪ ⎝ ⎠

⎩ ∑ ∑ ∑

(2)

As we known, if

ρ < 1

,

θ

>0, the first equation has the unique roots r₁₁=

γ

₁ in the range

0 < r

₁₁

< 1

. We can compute

* *

22 22 2 2

22

0 22 2

[ ( (1 )) ] [ ( (1 )) ]

(1 ) (1 ) ,

k k k

a r r a

r b r

β μ β μ γ γ

β μ β μ γ

∞

=

− − − −

= =

− − − −

∑

1 *

1 1 2 1 2

11 22

1 0 1 1 2 1 2

( (1 ))

1 1 1

k k

k

i k i

k k

k i k

r r a γ γ a γ a μ γ

γ γ γ γ

∞ − ∞

− −

= = =

− − −

⎛ ⎞

− ∑ ∑ ⎜ ⎝ ⎟ ⎠ = − ∑ − = − −

^{* 2 2}

1 2

( (1 )) a μ γ γ ,

γ γ

− −

= −

Finally, we obtain

r

₂₁

= βδ

,

r

₃₁=αβ δ − Δ( )and the expression for

R

.

Theorem 2. The Markov chain

( L J

_n

,

_n

)

is positive recurrent if and only if

ρ < 1

,

θ

,

β > 0

. Proof. Based on Neuts, the Markov chain

( L J

_n

,

_n

)

is positive recurrent if and only if the spectral radius SP(R)=max

{ γ

₁

, γ

₂

, γ

₃

}

of

R

is less than 1, and the matrix

⎟⎟

⎟

⎠

⎞

⎜⎜

⎜

⎝

⎛

= ∑ ∑

^+∞

=

∞ − +

=

−

k k

k k

k

k B R A

R

A B

R B

1 1 1

1

01 00

] [

has a positive left invariant vector. Evidently, SP(R)=max

{ γ

1

, γ

2

, γ

3

}

<1. Substituting the expressions for

R A ,

_kand

B

_kin B[R]，we obtain

0 0

0 0

1 1

0 0 0 0

1 2 2 1 2 2

1 0 0

1 0 0

[ ] 1 0 0

c c

a a

B R a b a b

γ γ

βδ βδ

γ γ γ γ γ γ

⎛ − ⎞

⎜ ⎟

⎜ − ⎟

⎜ ⎟

⎜ ⎟

= ⎜ − + − ⎟

⎜ ⎟

⎜ ⎟

/Management Science and Engineering Vol.2 No.2 2008 36-42

Where

(

2 3

)

2 3 0 2 3

0

1 3 1 2 3 2 3 3 3

A αβ δ δ γ γ a α γ γ c α γ γ

γ γ γ γ γ γ γ γ γ

−

⎛ − Δ ⎞ − −

= − ⎜ + ⎟ − + −

⎝ ⎠

(

2 3

)

2 3 0

0

1 3 1 2 3 2 3 3

B

αβ δ δ γ γ

a

α γ γ

c

γ γ γ γ γ γ γ γ

−

⎛ − Δ ⎞ −

= ⎜ + ⎟ + −

⎝ ⎠

^.

It can be verify that B[R]has the left invariant vector

π

₀=

K (1, αβ δ ( − Δ ), ( α γ

₂

− γ γ

₃

),

₃

)

. （3）

Thus, if

ρ < 1

,

θ

,

β

>0, the Markov chain

( L J

_n

,

_n

)

is positive recurrent.

If

ρ < 1

,

θ

,

β

>0, let

( L

v

, J )

be the stationary limit of the process

( L

n

, J

n

)

.Let

02

;

0

π

π =

π

_k

= ( π

_k0

, π

_k1

, π

_k2

), k ≥ 1

,

. ) , ( }, ,

{ lim } ,

{ = = = = = ∈ Ω

= P L k J j

→∞

P L

_n

k J

_n

j k j

kj n

π

Theorem 3. If

ρ < 1

, the stationary probability distribution of

( L

_v

, J )

is

1 3

1 2

0

1 2 1 3

1 2 3

2 3

, 1,

( ), 1,

, 0,

k k

k k

k

k k

k

k k

K k

K k

K k

γ γ

γ γ

π αβ δ

γ γ γ γ

π α γ γ

π γ

⎧ = ⎛ − − − Δ⎞ ≥

⎪ ⎜⎝ − − ⎟⎠

⎪⎪ = − ≥

⎨⎪ = ≥

⎪⎪⎩

where

( )( )( )

(

3

) (

2

)

¹

(

2² 3

)(

³ 1

) (

1

)(

2

)

1 1 1

1 1 1 1 1

K γ γ γ

α β γ δ γ α γ γ γ γ γ

− − −

= ⎡⎣ − − − Δ +⎤⎦ − − + − −

Proof.

( π

₀₂

, π

₁₀

, π

₁₁

, π

₁₂

)

is given by the positive left invariant vector (3) and satisfies the normalizing condition

π

02+

( π

_k0

, π

_k1

, π

_k2

)( I − R )

⁻¹

e = 1

Then, we get

( )( )( )

(

3

) (

2

)

¹

(

2² 3

)(

³ 1

) (

1

)(

2

)

1 1 1

1 1 1 1 1

K γ γ γ

α β γ δ γ α γ γ γ γ γ

− − −

= ⎡⎣ − − − Δ +⎤⎦ − − + − −

. We obtain

02

K ,

π = ( π

₁₀

, π

₁₁

, π

₁₂

) = K ( αβ δ ( − Δ ), ( α γ

₂

− γ γ

₃

),

₃

)

. We have

1 12 11 10 2

1

0

, , ) ( , , )

( =

⁻

=

_{k k k} ^k

k

π π π π π π R

π

,

k ≥ 1 ,

Finally, we easily obtain the theorem.

Theorem 4. If

ρ < 1

, the stationary queue length

L

_vcan be decomposed into the sum of two independent random variables:

L = L + L

, where

L

is the stationary queue length of a classical

/Management Science and Engineering Vol.2 No.2 2008 36-42

3 1

2 1

1 2 3

( 1)( )

1 1 1

K γ γ βδ α γ γ αβ

ϕ α

γ γ γ

⎛ − + − − + Δ ⎞

= − ⎜⎝ − − − ⎟⎠

, 3

1 1

ϕ K

= γ

− , ²

3

T γ

γ

⎛ ⎞

= ⎜ ⎟

⎝ ⎠, ^{0 2}

3

1

T 1 γ

γ

⎛ − ⎞

= ⎜⎝ − ⎟⎠ Proof. The PGF of

L

_vis as follows:

∑

^∞

=

=

=

0

) (

) (

k

v k

v z z P L k

L

= 3

( ) (

1 2

) (

1 3

)

2 3

1 2 1 3

k k k k

k k

k k k k k

Kα z γ γ γ z β δ γ γ z β γ γ z

α γ γ γ γ

⎡ − Δ − ⎤

⎢ + − + − ⎥

− −

⎢ ⎥

⎣ ⎦

= ^{1 1 1}

1 1 2 3

1 1 ( 1)(1 )

1 1 1 1

z z z z

K

z z z

γ α γ β δ α γ α β

γ γ γ γ

⎛ ⎞

− ⎜ − + − − − + Δ⎟

− − ⎝ − − ⎠

=L(z)L_d(z) Where

L (z )

is the PGF of

L

of a classical GI/M/1queue without vacation.

) (z

L_d = ^{1 1}

1 2 3

1 ( 1)(1 )

1 1 1

z z z z

K

z z

γ βδ α γ αβ

γ α γ γ

⎛ − + − − − + Δ⎞

⎜ ⎟

− ⎝ − − ⎠ (4)

2 1

1 1

γ βδ γ

z z z

− +

−

=

( ) ∑∞

=

+

−

0 2

1

1

k k k

z z

z γ βδ γ

=1+

( ) ∑∞

=

−

−

+

1 1 2 1 2

k

k

k

z

γ γ βδ

γ

.

Substituting the above equation into (4)，we obtain the distribution of

L

_d. We can easily get means

3 1

1 2 1

2 2

1 1 2 3

( 1)( )

( )

1 1 (1 ) (1 )

v

E L γ K α γ γ β δ α γ γ α β

γ γ γ γ

⎡ − + − − + Δ⎤

= − + − ⎢⎣ − − − ⎥⎦

.

3. WAITING TIME DISTRIBUTION

Let W and

~ ( ) s

W

be the steady-state waiting time and its LST, respectively. Firstly, let

H

0,H₁,H₂be the probability that the server is in the service(set-up, vacation) period when a new customer arrives. We can compute

( ) ( )

( ) ( )

³

( )(

²

) ( )( )

0

3 2 2 3 1 1 2

1 1

1 1 1 1 1

H α β γ δ γ

α β γ δ γ α γ γ γ γ γ

− − − Δ

⎡ ⎤

⎣ ⎦

= ⎡⎣ − − − Δ +⎤⎦ − − + − −

,

( )( )

( ) ( )

²

(

³

)(

¹

) ( )( )

1

3 2 2 3 1 1 2

1

1 1 1 1 1

H α γ γ γ

α β γ δ γ α γ γ γ γ γ

− −

= ⎡⎣ − − − Δ +⎤⎦ − − + − −

,

( )( )

( ) ( )

¹

(

²

)( ) ( )( )

2

3 2 2 3 1 1 2

1 1

1 1 1 1 1

H γ γ

α β γ δ γ α γ γ γ γ γ

− −

= ⎡⎣ − − − Δ +⎤⎦ − − + − −

. Theorem 5. If

ρ < 1

,

θ

,

β

>0, the LST of stationary waiting time Wis

)

~( s

W =

s s

s H s

+

−

− +

−

− +

+ (1 )

) 1 ( )

1 (

) 1 )(

(

3 3 2

2

1 μ γ

γ μ γ

μ

γ μ

β

β + ³

2

3

(1 )

(1 )

H s s s

μ γ

θ β

θ μ γ β

−

+ − + +

+ ^{1 2 3}

0

3 2 1 2 3

(1 )

( )(1 ) (1 )

( )

(1 ) (1 ) (1 ) (1 ) (1 )

s H s

s s s

μ γ

μ γ γ

μ δ

δ γ γ μ γ μ γ μ γ

⎡ + − Δ ⎤ + − − −

⎢ − − Δ − ⎥ − + − + − +

⎣ ⎦

/Management Science and Engineering Vol.2 No.2 2008 36-42

∑

^∞ =

=1 0 ~ 0( )

k

k

k W s

π

^{1 2 1 3}

1 1 2 1 3

k k k

k k

k

K s

γ γ

γ γ μ

α β δ

γ γ γ γ μ

∞

=

⎛ − − − Δ⎞⎛ ⎞

⎜ − − ⎟ ⎜⎝ + ⎟⎠

⎝ ⎠

∑

3

1 2

0

3 2 1 2 3

(1 )

( )(1 ) (1 )

( )

(1 ) (1 ) (1 ) (1 ) (1 )

s H s

s s s

μ γ

μ γ γ

μ δ

δ γ γ μ γ μ γ μ γ

⎡ − Δ ⎤ + − − −

= ⎢⎣ + − − Δ − ⎥⎦ − + − + − + (5)

When a new customer arrives, if there are kcustomers and the server is in the set-up period, the waiting time is the sum of the residual set-up time andkservice times by the rate

μ

. Then, we have

∑

^∞ =

=1 1~ 1( )

k

k

kW s

π

_{2 3}

1

( )

k

k k

k

K s s

β μ

α γ γ

β μ

∞

=

⎛ ⎞

− ⎜ ⎟

+

∑

⎝ + ⎠

= s s

s H s

+

−

− +

−

− +

+ ( 1 )

) 1 ( )

1 (

) 1 )(

(

3 3 2

2

1

μ γ

γ μ γ

μ

γ μ

β

β

. (6) Similarly,

3

2 2

1 1

( )

k

k k

k k

W s K

s s s

μγ β θ

π μ β θ

∞ ∞

= =

⎛ ⎞

= ⎜⎝ + ⎟⎠ + +

∑

^%

∑

⁼ 2 ³

3

(1 )

(1 )

H s s s

μ γ

θ β

θ μ γ β

−

+ − + + . (7) From (5)-(7), we have the result in Theorem 4.

With the structure in Theorem 4, we can get the expected waiting time )

(W

E =

2

3

1 1 1

(1 )

H θ μ γ β

⎡ ⎤

+ +

⎢ − ⎥

⎣ ⎦

+ _⎥

⎦

⎢ ⎤

⎣

⎡ +

+ −

−γ μ γ β

μ

γ 1

) 1 (

1 )

1

( _{2 3}

2

H1

+

[ ]

1 0

1 3 2 2 3

1 1

(1 ) (1 ) (1 ) (1 ) (1 )

H γ δ

μ γ μ δ γ γ μ γ μ γ

⎡ − Δ ⎤

− + +

⎢ − − − Δ − − − ⎥

⎣ ⎦

.

REFERENCES

Doshi, B.T.(1986). Queuing systems with vacations-a survey. Queuing Syst, 1, 29-66

Qin, X. (2006). GI/Geo/1 discrete-time queue with set-up period and multiple vacations. Operation Research, 15, 52-57.

Tian, N.S. (2006). Vacation Queueing Models: Theory and Application. New York: Springer-Verlag.

Tian, N.S. (1989). The GI/M/1queue with exponential vacations. Queueing Syst, 5 331-344.

Tian, N.S.(2002). The discrete time GI/Geo/1 queue with multiple vacations. Queueing Syst, 40 283-294.

Neuts, M. (1981). Matrix-Geometric Solutions in Stochastic models. Baltimore: Johns Hopkins University Press.