WORDS FLOW

Internat. J. Math. & Math.

VOL. 15 NO. 3 (1992) 593-600

ON A SINGLE-SERVER

^QUEUE

WITH FIXED ACCUMULATION LEVEL, STATE DEPENDENT SERVICE, AND SEMI-MARKOV

MODULATEO INPUT FLOW

JEWGENI H. DSHALALOW and

GARYRUSSELL

Department

of Applied

Mataematics

FloridaInstituteofTechnology

Melbourne,

FL

32901,

USA (Received

^July

29,1991)

ABSTRACT.

The authors study the queueingprocess inasingle-server queueingsystemwith statedependent service and withthe input modulated byasemi-Markovprocessembedded in thequeueingprocess.

It

isalso assumed that theservercapacityis r

>

1 and thatany service act will not begin untilthe queue accumulates at least runits.

In

this

model, therefore,

^idle periods alsodependuponthe queuelength.

The authors establish an ergodicity ^criterion for the queueing process and evaluate explicitlyitsstationary distribution and other characteristics of thesystem, suchas themean service cycle, intensity of the system, intensity of the input stream, distribution of the idle period,and themeanbusyperiod. Variousspecialcasesaretreated.

KEY

WORDS

AND PHRASES.

Queueingprocess, semi-Markov process, semi-regenerative pro- cess, embedded Markov chain, semi-Markov modulated Poisson process, equilibrium, conti- nuoustimeparameterprocess,servicecycle,idleperiod, busyperiod, intensity of theprocess.

1991 AMS

SUBJECT CLASSIFICATION CODES.

Primary60KI0, 60K15, 60K25, Secondary 90B22,90B25.

i.

INTRODUCTION.

Many

standard queueing systems operate on the assumption that input and service parameters are independent of the state of the system; to assume otherwise is frequently

regarded

^astoounwieldy.

In

this articleweproposeaclassofqueueingsystems which^canbe analyzed rather

thoroughly

^even

though

theinput andserviceparametersarestate

dependent.

We

add the provision that the service is delayed until the service batch size reaches the

server’s

capacity.

We

will show that such a class of systems readily avails itself to the appropriateanalyticaltechniques.

Allowingstatedependencemakes the modelmore versatile. Also,if thedelayinservice seems too restrictive, models that do not make ^this assumption are already available.

However,

for the class of systems under consideration, we assume that r

(_> 1)

units are necessary forservice, and if fewerare availabletheserver waitsfor moreunits to arrive. The different possible values of r,aswellasthe formation of theidleperiod

(which

in our casedoes not necessarily end with the arrival ofthe next

unit),

allows our system to encompass more situations. Applicationsin transportationseemprobable.

Otherauthors, suchas

Neuts,

Sumita, and Takahashi

(see [4]),

have studiedaPoisson processmodulated byaMarkovprocess.

In

thisarticleweconsiderthemoregeneralcaseofa Poisson process modulated bya semi-Markov process.

We

alsoassumethe service process is statedependent. Afteraformaldescriptionwestudytheembeddedqueueing process construc- tedoverthe sequence ofinstantsofservicecompletion

(under

^norestriction to service time dis-

tributions). ^We

^{extend the result for the} continuous timeparameter process by using tech- niques appropriate forsemi-regenerativeprocesses.

We

establishanecessary andsufficient cri- terionforergodicity and giveexplicit formulas for the limiting distributions of the processes.

We

derivethemean servicecycle, intensity ofthe system,intensity of the inputstream,distri- bution oftheidleperiod, and the mean busyperiod. Examplesare presented throughout the paper.

2.

FORMAL DESCRIPTION OF THE SYSTEM

Let {ft, , (P=)feE, Q(t)

^t>_

0} E {0,1,...}

denote thenumber ^of units in a

single-serverqueueingsystemattimet,let

{T.

ⁿE

N, To ^0,}

be the sequence ofsuccessive instantsofservicecompletion,let

Q. Q(T. + ^0),

^let

^C(-)

be the countingmeasureassociated with the point process

{T.},

and let

(t)= Q(Tc(t)+ ^{0), >_}

^{O. Then theinput is a Poisson}

process modu2atedby

{(t)}

^{due toa}definition to follow.

Let

(t)

^bean integer-valuedjump process

(with

successivejumps at

T,

ⁿE

N,

noting that 0 is theincrementofajump inthecaseof

Q.-1 Q.)

and let

{T;

k

N}

^{be a}non-sta- tionaryorderly Poissonpoint process withitsintensity function

A(t).

Thenwecall thedoubly stochastic Poisson point process with intensity

A((t))

the Poisson process modulated by the jmp process

{(t)}

and it is denoted by

{,}. Let Ne(

denote the associated counting measure.

[For

^aformal definition of modulated processesseeDshalalow

[3].]

Ifthe queuelength

Q.

isatleast r,thenattime

T. +

0 the server takesabatch ofunits ofsize rfrom the queue (according ^{to the}

FIFO discipline)

and servesit fora random time

r.

+^1. Otherwise, theserveridles until the queue

length Q(t)

first reaches levelrafter

T.

^and

then it begins to process a groupof runits taken fromthe waiting roomof infinite capacity

(again,

according ^to the

FIFO

discipline) ^with actual service time again equal to

.+

^1.

^In

bothcases we assume that

.

^{+ has a}probabilitydistribution function

B. ^{{B0, B1 ,...}, Bi}

beinganarbitrarydistribution function with finitemean bi.

3.

EMBEDDED PROCESS {Q.}.

Let V. ^Ne(a.).

^{Thentheprocess}

^{Q.}

^isdefinedrecursively by

Q.+I=(Q.-r)+ + V.+, ^(3.1),

whereoperator

(f)

^{+ isdefinedas}

(f)

⁺

sap{f,0}. From

relation

(3.1)

^{andthe natureofthe}

input process itfollowsthat theprocess

{ft,5,(P=)=g, Q(t);t >_ 0}

^---,

^E

^{has at}

Tn,

ⁿ

_

^1,the

locally

strong

Markov property

(see

^definition A.3 in

Appendix)

and that

QUEUEING PROCESS IN A SINGLE-SERVER QUEUEING SYSTEM 595

Q,

;n6

No} -- ^E

^{is a}homogeneousMarkovchainwith transitionprobability matrix

T (Po)"

Let

A,(z)

denote the generatingfunction ofith row of matrix T.

From A,(z)= E’[z Q*]

and

(3.1)

^weobtain

Ai(z)

^z(’-")+

l,(A, A,z), e E (3.2),

where

(8), Re(8)>0,

^is the Laplace-Stieltjes transform of the probability distribution function

B

and

A, A(i).

Foranalyticaladvantageand with verylittle sacrifice ofgenerality we drop the modulation and service control when the _queue length exceeds a fixed

(perhaps

very

large)

^level

N. In

otherwords,weassumethat

B,(z) S(z), fl,(O)= (0), b, b,A, A,

i>N

(AS).

Withoutloss ofgeneralitywealsoassumethatN

>

r-1.

Given assumption

(AS),

^{we can} show that the transition probability matrix

T

is reducedtoaform ofthe

A,.N-matrix

^introducedand studiedin

[1].

Accordingtotheorem A.1

(see

^Appendix),the Markov chain

{Q.}

^isrecurrent-positive if andonlyif

z ^{Ai(z) <}

^{oo, 0,1}

^..,N,

lira

z--,lzeB(O,I)

and

(3.3)

"---:(A

Az) <

^r

(3.4).

zl:zB(O,

Condition

(3.3)

^isobviouslymet andcondition

(3.4)

^isequivalentto

p Ab

<

r

(3.5).

Given that p

<

r, the Mkov chin

{Q}

^is

ergc.

Let

P (p=

;x

E)

^{denote the}

invit probability meure ofoperator

T

d let

P(z)

^be the generatingfunctionof vector P. Nowweformulate the

mMn

result ofthis section.

THEOREM 1. The embedded queueing process

Q,}

is ergodic if and only if p

<

r.

Underthiscondition,

P(z)

^satisfiesthe equation

(Po,’",PN) lz)

o

z

(A- lz) (3.6a),

with

A(z)

^determinedby

(3.2).

Probabilities _{Po, ...,PN}form the uniquesolutiontothe follow- ing system oflinearequations:

EN=op,-z{A,(z)-

^z

^}

^{0, k 0,...,}

^ko

^1,s

^{1,...,S (3.6b),}

E,N=oP, tp,-

p

+ (r- i)+1

^r-p

(3.6c),

where p

b, z

^{aretherootsof zN+ zN+}

^{-/( z)in}

^{the region}

^B(0,1)\{I}

^{with their}

multiplicities

ko

^{such that s}

k

^N.

PROOF.

Formula

(3.6a)

follows from

P(z) E ,EP, A(z)

^and

(3.2).

Itis easyto modify formula

(3.6a)

^into

=N+,pz_(N+I) _zN

₊

^=oP{A(z) _zN

₊

_{-,(_}

^z

^i} _z) ^(3.6d).

Obviously,

:=N

^+,

^p,z’

^{(N+1) is analyticin}

^B(0,1)

^andcontinuous on

OB(0,1).

According totheoremA.2, ^{thefunction z z}

-(A- Az)

^{must haveexactlyrzeros}

(counted

^{with their}

multiplicities)

in

i’(0,1),

^{andallzeros on}the boundary

0B(0,1),

including the root 1, must be simple after we meet the ergodicitycondition p

<

r. Therefore, the denominator intheright handsideof

(3.6d)

^hasexactly groots intheregion

(0,1)\{1}

^andthis, along with

(P,1)=

¹

(which

^{isequivalent to}

(3.6c)),

yields the equationsin

(3.65)

^and

(3.6c).

Now we prove the uniqueness of

{Po,...,PN}. ^Suppose

that the system of equations

(3.6b)

and

(3.6c)

^{has another solution}

p: {p:; i-0,...,N}.

We substitute

p*

into

(3.6a)

^to

obtain the generating function

P*(z).

^Then,

P*(z)

^{is analytic in}

B(0,1)

^{and continuous on}

0B(0,1). Therefore,

P*

{p

;iG

}

G

(l , )-

Obviously, equations

P’(z) ,pA,(z)

and

,N__

0

{A,()- ^(- )}

P.() ,_ _{(- )}

are equivalent. The last equation is also equivalent to P*

P’A.

Since p* satisfies

(3.6c)

^it

follows that

(P’,I)=

^{1. Thus,} the system of equations z=

zA, (z,1)=

1 has two different

solutionsin

(l , -II)

^whichisimpossible. ^[’1

4.

EXAMPLES AND APPLICATIONS.

DEFINITIONS

2.

(i)

^Let

/j EJ[T],

^{the mean} sojourn time ofthe process

{(t)}

^instate {j}, and let j

(/;j

E

E) T.

Then

PJ

^{is the mean service cycle}

of

^{the system, where}

^P

denotes the stationaryprobabilitydistributionvectorofthe embedded queueingprocess

(ii)

Let

,=(x;zEE)

^{T and let}

p=.

be the HaAamard

(entry-wise)

product of

vectors/

^and

.

^{Wecall thescalarproduct}

^Pp

^theintensity

^of

^thesystem.

The concept of "intensity of the system goes back to the classical

M/G/1

^system,

where

Pp

reduces to p Ab. It is worth noting that the intensity of the system and the capacity of theserver

(in

^{our case}

r)

coincide,asstated in proposition4andproved thereafter.

PROPOSITION

3. Given the equilibrium condition p

<

r, the mean service cycle satisfies thefollowingequation:

P-

^b/

=opj[(b,-b)/ (r- ⁱ⁾

⁺

^(4.1).

PROOF.

Obviously,

/j b ^{+ (r}

^j)

^+/A.

The statement is now due to elementary

algebraictransformations. ¹³

PROPOSITION

4. Giventheergodicitycondition p

<

r, the intensity ofthe systemand and the capacity of theservercoincide.

PROOF. From

definitionof

Pp

and considerationsasinpropositi.on^3itfollowsthat

Pp= p+ N=op[(pj--p)+ (r-i) +] (4.2).

The statementisdue to relation

(3.6c)

^andelementary algebraictransformations. ¹³ EXAMPLES5.

(i)

^{Consideraspecial caseofourmodelwithr}

2, N

^{4 andwith}

B

as anegative^ex- ponential distribution with parameter

}. ^However,

^{weretain all other}assumptions aboutthe modulation andservice control having

Bo,...,B

4arbitrary.

For

thiscase we

obtain/(- z) (1 +

^p-

^pz)-

^anditfollows thatthe onlyroot of the equationz

-/(A- z)

^insidethe ball

B(0,1)

^is

zx

^{2p Thus for equation}

^(3.6b)

^wewill be using

z

^with multiplicity^one and 0 withmultiplicitythree. This willgive4 of total 5equations in the unknownsP0,.-.,P4:

E’

,=o

^(z

^‘-)+

,(,- ,)- },

⁰

’(o)o + ,, (,), + [’() 2] 2S() + ^2,(,),

⁰

o;(o)po-[,(,) + 1,- ()p + ^()p o

[/o(Ao) lip

o

+/,(,)p, +/2()p

O.

QUEUEING PROCESS IN A SINGLE-SERVER

The fifth equation will be

(3.6c)

^{with r 2 and N 4. This system can be solved by}

elementary algebraic methods. The solution of this system will then be put ^into equation

(3.6a)

^{tohave thegeneratingfunction}

P(z)

^inanexplicit form.

(ii) By

dropping the modulation and servicecontrol and settingr 1, weimmediately arriveatthe classical formulabyKendall establishedfor the model

M/G/1.

5. CONTINUOUS

TIME PARAMETER

PROCESS

Q(t)}.

In

this sectionour mainobjective will be the derivation of thestationary distributionof the queueingprocess with continuous timeparameter. Priortothis,wewill be concerned with somepreliminaries.

From section 3 and definition A.4, it follows that

{fl,J,(P=)=,E, Q(t);

t>_

0}

^---,

(E, (E))

^{is a} semi-regenerative process with conditional regenerations at points

T.,

nE

N. Let

f,,

(P=)=,E, Q,, T,:

^{n 0,1,...}

(E

^x

^R

+,

9(E

x

R

₊

))

^be the associated Markov renewal processand let

Y(t)

be thecorrespondingsemi-Markovkernel. With avery mild restrictionto the probability distributionfunctions

B,

^{we can}specify that the elements of

Y(t)

^arenot step functionsand thus

{Q., T,}

^is aperiodic.

By

proposition 3, ^themeanservice cycle

Pfl,

which jsalso themean inter-renewal timeofthe Markov renewal process, isobviouslyfinite. There- fore, followingdefinitionA.5andgiventhat p

<

r, theMarkovrenewal process isergodic.

It also follows that the jump process

{f,,(

p

)E, f(t); _> 0}

^--,

E,

definedin section 2, is theminimal semi-Markov process associated with the Markov renewal process

{Q. ,T.}

and therefore, following the definition in section2,the input process

{f,,(P)=,E, Ne} - ^E

isaPoissonprocess modulatedbythe semi-Markov process

{f(t)}.

Let

g(t)= (g,k(t);j,

^k

e E)

be thesemi-regenerative kernel

(see

^definition

A.6).

^The

following statement holdstrue.

LEMMA

6. The semi-regenerative kernel^satisfiesthe following equations:

(,

^j,

,)(1 B())

^{d 0}

^<

^j<,

^<

gjk (t) Io u)Aju(k-- _(5.1)

,,,(k- ^{)[1 B()], < <}

^k

O,

O<k<j,

with

(;

^y

^e R+

^{the Poisson}semi-group and

e(,n,-)

^the Erlang-n probabilitydensity func- tionwith parameter

.

PROOF. The aboveassertionfollows fromstraightforwardprobabilityarguments. ^[’l

Now

wearereadytoapplytheMain

Convergence

Theorem to thesemi-regenerativeker- nelinthe formofcorollary A.8, thereby arrivingat the stationary distribution of the queueing process

{Q(t)}.

THEOREM 7. Given the equilibrium condition p

<

^r for the embedded process

{Q.},

the stationary distribution

(r;x e E)

of the queueing process

{Q(t)}

exists; it is indepen- dent ofanyinitialdistribution andisexpressedinterms of thegenerating function

r(z)

^{of by}

the following formula:

PflrCz)(1 z) i ^{f (A Az)]P(z) +} v=

^o

p,z/(

where

P(z)

^is the generating function of

P, Pfl

^is determined in proposition 3, and

A(z)

^is

defined in

(3.2).

PROOF.

Recall that the Markov renewal process

{Qn,Tn}

^is ergodic if p

<

r.

By

corollary A.8 the semi-regenerative process

provided that p

<

r.

We

cansee thatthe semi-regenerative kernelis Riemann integrableover

[+. Thus,

following corollary

A.8,

weneed tofindthe integrated semi-regenerative kernel

H (which

^{is done}with routine

calculus)

and then thegeneratingfunction

h(z)

^{foreachrowofH.}

First wefind that

zp

h(z), i >

r

(5.2b).

Then,

j()

¹

’- ^{%(A- )}

A,(1 ^z)

^,0

^{_< i <}

^r

^(5.2c).

Formula

(5.2a)

^nowfollows fromcorollary A.8,equations

(5.2b)

^and

(5.2c)

^andsomealgebraic transformations.

EXAMPLES

8.

(i) By

dropping the^modulation of the input process^weobtainfrom proposition4 that

Pfl, -- ^{(ii) By ands(z)}

using obvious probability

^rl_z)P(z).

argumentswe derive the probability density function of

anidleperiodin thesteady state:

: ^0P

U- r--1

oP

Themeanidle period inthesteadystateisthen

s (s.3)

0p,

(iii)

^Formula

(5.3a)

and theorem 7 allowustoderivethemeanbusy period

B

inequilib-

,-I

r

^is the probability that the server idles.

On

the other hand, it also rium. Clearly

0

equals_j

. ^.

^{Thuswehave -1}

(iv)

Nowweturntothe specialcaseinexample5

(i)

applyingitsresultsfor the process with continuous time parameter.

We

use probabilities P0,--.,P4, substituting ^{them into} formulas

(5.2a)

^and

(4.1)

forr 2 andN 4,thereby reducingthegeneratingfunction

r(z)

^to

anexplicitform.

(v)

^{Ifthe inputisastationaryPoisson}process thenitsintensityis

A,

which isalso the meannumber of arrivals per unittime.

In

thecaseofamodulatedinput processitsintensityis nolongeratrivialfact.

We

definethe intensity of any countingmeasure

N

by the formula where

pt(z)= E=[N([0,])]. ^We

^will apply ergodic theorem3.9 established inDshalalow

[3]

^for

moregeneralPoisson processmodulatedbyasemi-Markov process:

:

P/P/

wherebyproposition 4.3

P

^rand

P

satisfies equation

(4.1)

^{and thuswehave:}

- ^(s.3).

A

trivial special case appears when we drop the modulation of the input and therefore use

formula

(4.1)

combiningit withformula

(5.3b).

Then:

A,

^asitshould be.

Another interesting special caseisdue to the assumption that b b andr

(observe

that we only require that the service means

bo, b,..,

^are equal but do not restrict the corresponding

distributions).

^Thenwehave that requalsthe reciprocal of

Pfl

^b

+

Po

o

APPENDIX

THEOREM

A.1

(Abolnikov

^and Dukhovny

[1]).

^Let

{Q,,}

^{be an} irreducible aperiodic Markov chain with the transition probability matrix

A

in the

form of

^a

Ar,v-matrix.

^Then

{Q,}/s

recurrent-positive

if

^andonly

if

lira

z ^{A(z) < ,}

^i=O,1,...,N,

^(A.la)

z-.1:zB(O,

and

lira

d-/(A ^{Az) <}

^r

^{(A. b).}

z-,l:zeB{o, 1}

THEOREM

A.2

(Abolnikov

^and Dukhovny

[1]).

Under the condition

of (A.lb)

^the

function

^z

- ^(A-Az)

^{has exactly r} roots belonging to the closed ^unit ball

B(0,1)= {ze

C:

< 1}.

Tho oot oth

o=d=, 0(0,X) =

DEFINITION A.3. Let

T

be a stopping time for a stochtic process

{,, (P=)=,, Z(t); t0} (E, (E)).

The process

{Z(t)}

^{is sMd to} have the locally strong Markov

propey

at

T

if for each bounded random viable

(: E

d for ech

BMre

function

f:

E R,

r 1,2,...,itholdstruethat

E’[f

^o

(

^oO_T

IT] EZr[f

^o

(] ^P’-a.s.

^on

{T < },

where is theshiftoperator.

DEFINITION A.4.

A

stochtic process

{fl,,(P=)=,e, Z(t);t 0} (E, (E))

^with

E 5 N

^is cMledsemi-regenerative if

a)

^thereisapointpreeNS

{T,}

^on

R+

^{such that}

^{T, (n)}

d such that each

T

isastoppingtimerelative to theconicfiltering

a(Z;y t),

b)

^theprocess

{Z(t)}

^{h the}locMly strongMkov property at

T,,

ⁿ 1,2,...,^d

c) {Z(T, +0),T,;

ⁿ

0,1,...}

^isaMkov

^renewM

^preens.

DEFINITION A.5. Let

{X, ,T}

irreducible aperiic Mkov

renewM

process with discrete state space

E. t E=[T]

be themesojourntimeofthe Mkov

renewM

preens instate

{x}

^{d let}

fl= ^{(=;x E)T. Suppose}

^{that the}

emded

Mkov chMn is ergicwith stationydistributionP. WecMl

Pfl

^themeaninter-renewdtime. WecMl the Mkov

renewM

process recuent-positive if its me inter-renewM time is finite.

An

ieducible

ariodic

^d

recurrent-sitive

^Mkov

^renewM

^processis cMled ergodic.

DEFINITION

A.6.

Let {fl,, (P=)=,E, Z(t);t 0} (E, (E))

^beasemi-regenerative process relativetothe sequence

{T}

^ofstoppingtimesd let

r(t) P,{Z(t) t,T > t}, , ^e

^E.

WewillcM1 thefunctionM matrix

K(t) (K#(t)

^j,k

e E)

the semi-regenerative keel.

THEOREM

A.7

(The MMn Convergence

Whrem,

cf. inl ^[2],

^p.

^{347). Let}

{,, (P=).,, z(t); e 0} (E, (E)) i-#=ti

^tohti=

e

sequence

{ Tn} of

stopping timesand let

K(t)

be the coespondingsemi-regenerative keel.

Suppose

that the sociated Markov renewalprocess ergodic and

at e

semi-regenerative keel Riemann integrable over

R

_+. Then the

stationa

^dtbution

process

{Z(t)}

^ezistaandit is determined

from

^the

formula:

rk

E,,EP, f

_o

K,k(t)dt,

^ke

^E (A.Ta).

COROLLARY

A.8.Let

H= (hj;j, kE E)= fo K(t)dt (the

integratedsemi-regenerative

kernel),

^let

h(z)

be the generating

function of

^{th row}

of

^matri

H,

and let

x(z)

^{be the}

generating

function of

^{vectorz. Then}

1

h(z) ^(A.Sa)

() P--B ^E

^,E

^V

PROOF. From (A.Ta)

^wegetanequivalent formulain matrixform, r

-.

^Finally,

formula

(A.Sa)

istheresult ofelementary algebraictransformations. ^!’!

REFERENCES

[1]. ABOLNIKOV, L.

and

DUKHOVNY, A.,

Markov chains with transition delta-matrix:

ergodicity conditions, invariant probability measures and applications,

Journ.

AppI.

Math. Stoch.Anal., 4, No. 4, 335-355, 1991.

[2]. QINLAR, ^E.,

Introduction to Stochastic

Processes,

Prentice

Hall,

Englewood Cliffs,

N.J.,

1975.

I3]. ^DSHALALOW, J., On

modulatedrandom measures.

Journ. AppI.

Math. Stoch.

Anal.,

4, No.4, 305-312, 1991.

[4]. NEUTS,

^M.

^F., SUMITA, U.,

and

TAKAHASHI, Y.,

Renewal characterization of Markov modulatedPoissonprocesses,

Journ.

Appl. Math.Simul.,2,

No.

1,53-70, 1989.