by
JosephAbate1andWardWhitt2
April15,1996
Revision:January2,1997
OperationsResearchLetters20(1997)199–206
Abstract
Weprovideadditionaldescriptionsofthesteady-statewaiting-timedistributionintheM/G/1queuewiththelast-infirst-out(LIFO)servicediscipline.Weestablishheavy-trafficlimitsforboththecumulativedistributionfunction(cdf)andthemoments.Wedevelopanapproximationforthecdfthatisasymptoticallycorrectbothasthetrafficintensityρ→1foreachtimetandast→∞foreachρ.WeshowthatinheavytraffictheLIFOmomentsarerelatedtotheFIFOmomentsbytheCatalannumbers.Wealsodevelopanewrecursivealgorithmforcomputingthemoments.
KeyWords:M/G/1queue;Last-infirst-outservicediscipline;Waitingtime;HeavyTraffic;
Asymptotics;Asymptoticnormalapproximation;Moments;Catalannumbers
1.Introduction
Thepurposeofthispaperistodeduceadditionalpropertiesofthesteady-statewaiting-timedistribution(untilbeginningservice)intheM/G/1queuewiththelast-infirst-out(LIFO)servicediscipline.Weobtainourresultsherebyapplyingresultsinourpreviouspapers[1]–[6].OurresultsherecomplementpreviousM/G/1LIFOresultsbyVaulot[17],Wishart[19],Riordan[13],[14],Tak´acs[16]andIliadisandFuhrmann[10].
WestartinSection2byestablishingaheavy-trafficlimittheoremfortheM/G/1LIFOsteady-statewaiting-timedistribution.InSection3wegiveanewderivationforthelarge-timeasymptoticsoftheLIFOsteady-statewaiting-timedistribution,complementingourrecentresultin[1].InSection4wethendevelopanapproximationfortheLIFOwaiting-timedistribution,calledtheasymptoticnormalapproximation,andshowthatitisasymptoticallycorrectbothastimet→∞foreachvalueofthetrafficintensityρandasρ→1foreacht.OurapproximationgeneralizesanapproximationsuggestedfortheM/M/1modelbyRiordan[14],p.109.Sections2–4parallelanddrawonourpreviouslimitingresultsfortheM/G/1busy-perioddistributionin[5].InSection5wegiveanumericalexampleshowingthattheasymptoticnormalapproximationfortheLIFOsteady-statewaiting-timecdfperformsverywell.Weshowthatitismuchbetterthanthelarge-timelimit(thelimitast→∞foreachfixedρ).
InSection6wedevelopanewrecursivealgorithmforcomputingtheM/G/1LIFOwaiting-timemoments.WebelievethatthisalgorithmisanattractivealternativetopreviousalgorithmsdevelopedbyTak´acs[16]andIliadisandFuhrmann[10].Thefirstfourmomentsaregivenexplicitly.InSection7weshowthatthemomentshaveaverysimpleasymptoticforminheavytraffic.2.Heavy-TrafficLimitfortheLIFOCDF
Inthissectionweestablishaheavy-trafficlimitfortheLIFOsteady-statewaiting-timecdf,denotedbyWL.Forthispurpose,weestablishheavy-trafficlimitsfortheM/G/1workloadprocessmomentcdf’s.TheseworkloadresultsextendpreviousresultsfortheM/M/1specialcaseinCorollary5.22of[3].Theheavy-trafficlimitsfortheworkloadprocessarelocal-limitrefinements(versionsfordensities)totheoremsthatcanbededuceddirectlyfromolderheavy-trafficlimittheorems,e.g.,inWhitt[18].
Weusethefollowingnotation.Foranycumulativedistributionfunction(cdf)F,letfbetheassociatedprobabilitydensityfunction(pdf)andletmk(F)bethekthmoment.LetFc(t)≡1−F(t)
1
betheassociatedcomplementarycdf(ccdf)andlettheassociatedequilibriumexcessccdfbe
cFe(t)
=m1(F)
−1
∞
t
Fc(u).
(2.1)
ThepdfofFeisfeanditskthmomentismk(Fe).
Fork≥1,letHkbethekthmomentcdfofcanonical(drift1,diffusioncoefficient1)reflectedBrownianmotion(RBM){R(t):t≥0},i.e.,
Hk(t)=
E[R(t)k|R(0)=0]
E[Vρ(∞)k]
,t≥0,(2.5)
see[4].JustaswithHk(t)in(2.2),Hρk(t)asafunctionoftissimultaneouslytheexpectationofastochasticprocessandacdfforeachρ.AlsoletHρ0bethe0th-momentcdforserver-occupancycdf,definedby
Hρ0(t)=(1−P00(t))/ρ,
t≥0,
(2.6)
whereP00(t)istheprobabilityofemptinessattimetstartingemptyattime0(witharrivalrateρ),asin(23)of[4].
2
ThekeyformulaconnectingtheseexpressionstotheLIFOcdfWLis
ccWL(t)=P00(t)−(1−ρ)=ρHρ0(t),
(2.7)
duetoTak´acs[16];see(36)of[1]and(78)onp.500of[16].ThenexttheoremdescribestheLIFOsteady-statewaiting-timecdfWLinheavytraffic.Theorem2.1Foreacht>0,
c(tm(G)(1−ρ)−2)limρ→12(1−ρ)−1WL2
c(tm(G)(1−ρ)−2)=limρ→12(1−ρ)−1Hρ20
=limρ→1m2(G)(1−ρ)−2hρ1(tm2(G)(1−ρ)−2)=h1(t)
forh1in(2.3).
Proof.By(2.7),thefirstlimitisequivalenttothesecond.ByTheorem2(b)of[4],hρ0e(t)=Hρ1(t),sothathρ1(t)=Hρ0(t)/hρ01.ByTheorem6(b)of[4],hρ01=ρ−1vρ1=m2(G)/2ρ(1−ρ).Hencethethirdlimitisequivalenttothesecond.
ByTheorems3(a)and4(b)of[4],
ˆρ1(s)=h
1−ˆbρe(s)
s(1−ρ+ρˆbρe(cs))
.
Sincewehaveexpressionsforthetransforms,weestablishtheconvergenceusingthem.ByThe-ˆ1(s)asρ→1.(Equations(2.9)of[5]shouldreadhρ(t)≡m2(1−ρ)−2orem1of[5],ˆbρe(cs)→h
c(tm(1−e)−2),withmtherebeingm(G)here.Incidentally,bρe(tm2(1−ρ)−2)=m2(1−ρ)−1Bρ222∗(dt(1−ρ)−2)inaspacenormalization—typicallyc(1−ρ)foraconstantc—ismissingbeforeWρ
ConditionC2onp.589in[5]aswell.)Hence,
ˆ1(s)]2[1−hˆhρ1(cs)→
ˆ1(s)h
ˆ1(s),=h
withthelaststepfollowingfrom(2.6)of[5]orp.568of[2].
TheLIFOapproximationobtainedfromTheorem2.1is
c
(t)≈WL
(1−ρ)
TheM/M/1specialcaseofTheorem2.1forhρ1(t)isgiveninCorollary5.2.2of[3].In[3]thetimescalingisdoneattheoutset;see(2.2)there.
Thelimitforthedensityhρ1impliesacorrespondinglimitfortheassociatedcdfHρ1,byScheff´e’stheorem,p.224ofBillingsley[7].Thefollowingresultcouldalsobededucedfromstandardheavy-trafficlimitsfortheworkloadprocess[18].Corollary.Foreacht>0,
limHρ1(tm2(G)(1−ρ)−2)=H1(t)=1−2(1+t)[1−Φ(t1/2)]+2t1/2φ(t1/2).
ρ→1
3.Large-TimeAsymptotics
In[1]weused(2.7)andanintegralrepresentationforP00(t)toestablishtheasymptoticbehavior
c(t)ast→∞.HerewegiveanalternativederivationbasedonasymptoticsforthedensityofWL
wL(t).Letf(t)∼g(t)ast→∞meanthatf(t)/g(t)→1ast→∞.
WestartwiththeelementaryobservationthattheconditionalLIFOsteady-statewaitingtimegiventhatitispositivecoincideswiththebusyperiodgeneratedbytheequilibriumexcessofaservicetime.Letb(t,θ)bethedensityofabusyperiodstartingwithaservicetimeoflengthθ.ThentheLIFOwaiting-timedistributionhasanatomofsize1−ρattheoriginandadensity
wL(t)=ρ
∞
0
b(t,θ)ge(θ)dθ,t>0.(3.1)
From(3.1),wereasonasinCoxandSmith[8]and[1]toobtainthefollowingasymptoticresult.Theorem3.1Ast→∞,
wL(t)∼(ω/τ)(πt3)−1/2e−t/τ
and
c
WL(t)∼ω(πt3)−1/2e−t/τ,
(3.2)
(3.3)
whereτ−1istheasymptoticdecayrate(reciprocaloftherelaxationtime),givenby
τ−1=ρ+ζ−ρgˆ(−ζ),
(3.4)
ζistheuniquerealnumberutotheleftofallsingularitiesoftheservice-timemomentgeneratingfunctiongˆ(−s)(assumedtoexist)suchthat
gˆ′(−u)=−ρ−1,
4
(3.5)
ω=ρα/ζ2,α=[2ρ3gˆ′′(−ζ)]−1/2.
Proof.Weapply(19)of[1]with(3.1)toobtaintheintegralrepresentation
′
wL(t)=(ρ/t)L−1(−gˆe(s)exp(−ρt(1−gˆ(s))),
(3.6)(3.7)
(3.8)
whereL−1istheLaplacetransforminversionoperator(Bromwichcontourintegral)
L−1(ˆg(s))(t)=
1
ζ2τ
obtain(3.3);seep.17ofErd´elyi[9].
b(t)ast→∞.(3.12)
Hence,wecaninvoketheknownasymptoticsforb(t)in(5)of[1].Finally,weintegrate(3.2)to
4.TheAsymptoticNormalApproximation
In[5]wefoundthatthetailoftheM/G/1busy-periodccdfiswellapproximatedbyanasymp-toticnormalapproximation,whichisasymptoticallycorrectasρ→1foreachtandast→∞foreachρ.WenowapplyessentiallythesamereasoningtodevelopasimilarapproximationfortheLIFOsteady-statewaiting-timeccdf.
ParallelingTheorem2of[5],wecanexpresstheasymptoticrelationin(3.3)intermsofh1(t),because
h1(t)∼2t−1γ(t)ast→∞,
(4.1)
forγin(2.4).Thefollowingisourasymptoticnormalapproximation,obtainedbycombining(2.4),(3.1)and(4.1).TheM/M/1specialcasewasproposedfortheM/M/1queuebyRiordan[14],p.109.
5
Theorem4.1If(3.3)holds,then
cWL(t)∼2ωτ−3/2h1(2t/τ)ast→∞.
forh1(t)in(2.3),τin(3.4)andωin(3.6).
Theorem4.1directlyshowsthattheasymptoticnormalapproximationisasymptoticallycorrectast→∞foreachρ.Previousasymptoticrelationsforτandωshowthatitisalsoasymptoticallycorrectasρ→1foreacht.Inparticular,by(14)and(40)of[1],
τ
−1
=
(1−ρ)2
2
2
(1+O(1−ρ))asρ→1,(4.3)
whichisconsistentwith(2.9).Fortheconstant,notethat
2ωτ
−3/2
∼
2
asρ→1.(4.4)
5.ANumericalExample
InthissectionwecomparetheapproximationsfortheM/G/1LIFOsteady-statewaiting-time
c(t)toexactvaluesobtainedbynumericaltransforminversion.WeconsiderthegammaccdfWL
service-timedistributionwithshapeparameter1/2,denotedbyΓ1/2,whichhaspdfgin(2.4)andLaplacetransform
√
gˆ(s)=1/
s+ρgˆ(1/ρˆ00(s))
integralrepresentation
,(5.2)
see(37)of[4],andthenuse(2.7).However,thereisamoredirectapproachusingthecontour
c
WL(t)=t−1L−1(s−2exp(−ρt(1−gˆ(s))))−(1−ρ),
(5.3)
6
whereL−1istheinverseLaplacetransformoperator;see(34)of[1].Equation(3.8)aboveisasimilarrepresentationforthedensity.
c(t)forthecaseρ=0.75.InTable1wealsodisplayresultsTable1givestheresultsforWL
forthreeapproximations:(i)thestandardasymptoticapproximationin(3.1),(ii)theheavy-trafficapproximationin(2.9)and(iii)theasymptoticnormalapproximationinTheorem3.1.
Forthestandardasymptoticapproximation,weneedtoderivetheasymptoticparametersωandτ−1.Forthisexample,wefindfromtherootequation(3.5)that
ζ=
1
2
−
3
√√
time
t
exactbynumericalinversion
asymptoticnormalapproximation,Theorem4.1heavy-traffic
approximation,
(2.8)standardasymptoticapproximation,
(3.3)
Table1showsthattheasymptoticnormalapproximationisremarkablyaccuratefortnottoosmall,e.g.,fort≥5.Moreover,theasymptoticnormalapproximationismuchbetterthanthestandardasymptoticapproximationbasedon(3.3).Theheavy-trafficapproximationisquitegoodthoughfortneithertoolargenortoosmall,e.g.,for1.0≤t≤120.Thestandardasymptoticapproximationisnotgooduntiltisverylarge.FromTable1,notethatthestandardasymptoticapproximationforthetailprobabilityisconsistentlyhigh,whereastheheavy-trafficapproximation(2.8)crossestheexactcurvetwice.
6.ARecursiveAlgorithmfortheLIFOMoments
Inthissectionwerelatethekthmomentsofthesteady-stateFIFOandLIFOwaiting-timedistributions,denotebyvkandwk,respectively.Forpreviousrelatedwork,seeTak´acs[16]andIliadisandFuhrmann[10].IliadisandFuhrmannshowthatthesamerelationshipbetweenLIFOandFIFOholdsforalargeclassofmodelswithPoissonarrivals.
Leth0kbethekthmomentoftheserver-occupancycdfHρ0in(2.6).By(2.7),
wk=ρh0kforallk≥1.
(6.1)
Theorem6of[4]givesanexpressionforthemomentsh0kintermsofthemomentsbekofthebusy-periodequilibriumexcessdistribution,whileTheorem5of[4]givestherecursiveformulaforthebusy-periodequilibrium-excessdistributionmomentsbekintermsofthemomentsvk.ThesetworesultsgivearecursivealgorithmforcomputingtheLIFOmomentswkintermsoftheFIFOmomentsvk.
First,asin(43)of[4],wecanrelatetheFIFOwaiting-timemomentstotheservice-timemomentsviaarecursion.Letthekthservice-timemomentbedenotedbygk.Therecursionis
vk=
ρ
j+1
vk−j,
(6.2)
wherev0=1,sothattheFIF0momentsvkarereadilyavailablegiventheservice-timemomentsgk.
ˆByTheorem3aof[4],theequilibrium-timetoemptinesstransformfǫ0(s)canbeexpressedas
ˆˆfǫ0(s)=1−ρ+ρbe(s),
sothattheirmomentsarerelatedby
fǫ0k=ρbek,
8
k≥1.
(6.4)(6.3)
Theorem5of[4]showsthatthesemomentscanbecomputedrecursively,giventhemomentsvk.Toemphasizetherecursivenature,foranyLaplacetransform
ˆ(s)=f
∞0
e−stf(t)dt,
(6.5)
ˆ)bethetruncatedpowerseriesdefinedbyletTn(f
ˆ)(s)=Tn(f
nfk
k=0
dsk
|s=0,
(6.7)
whichiswelldefinedassumingthattheintegralsin(6.7)arefinite.ThenTheorem5(a)of[4]canberestatedas
fǫ0k=
kkvj
j=1
j
w3=
v3+3v2v1
1−ρ
(6.10)
,
(1−ρ)3
whichisconsistentwithTheorem6of[4].Inthecase(e)ofTheorem6in[4]thereisatypographicalerrorinh04;allfourtermsthereshouldbedividedbyρ(1−ρ)3.
9
7.Heavy-TrafficLimitsfortheLIFOMoments
WenowshowthattheLIFOwaiting-timemomentshaveasimpleasymptoticforminheavytraffic.AsinSection6,letgkandwkbethekthmomentsoftheservicetimeandLIFOwaitingtime,respectively.
Theorem7.1Assumethatgn+2<∞.Thenwn+1<∞and
wn∼
(2n−2)!
(1−ρ)n−1
asρ→1.
(7.1)
ToputTheorem7.1inperspective,itshouldbecontrastedwiththeknownheavytrafficre-sultsforfirst-infirst-out(FIFO)andrandomorderofservice(ROS).ForFIFO,thewaiting-timedistributionisasymptoticallyexponentiallydistributedasρ→1,sothat
n
vn∼n!v1asρ→1.
(7.2)
ForROS,withWRasthecdf,Kingman[11]showedthat
1−WR(t)≈2
whereK1istheBesselfunction,sothat
nwRn∼(n!)2wR1asρ→1.
t/wR1)
(7.3)
Ofcourse,w1=wR1=v1.Itisinterestingthat,asρ→1,thenthmomentsvn,wRNandwnin
ntimesn!,(n!)2and(2n−2)/(n−1)!(1−ρ)n−1,respectively.Hence,vandw(7.1)–(7.3)arev1nRN
areO((1−ρ)−n)asρ→1,whilewnisO((1−ρ)−(2n−1)).
WegiveanotherexpressionusingtheCatalannumbers.LetCnbethenthCatalannumber,i.e.,
Cn=
1
Corollary.UndertheconditionsofTheorem7.1,
wn∼Cn−1
vn
(n+1)!2n
Combining(7.6)and(7.7)givestheformula.
.(7.7)
Theextramomentconditionthatgn+2befiniteisusedtoestablishtherequireduniforminte-grability.From(6.2),(6.4),(6.8)and(6.9)weseethatvk,fǫ0k,bekandwkareallfinitefork≤nwhengk+1<∞.Toestablishupperboundsimplyinguniformintegrability,notethatby(6.2),
vk≤
gk+12k
(1−ρ)2k
whereKkisαconstantindependentofρ.Finally,by(6.9)and(7.9),
wk≤
Mk
(7.9)
(1−ρ)n
From(6.9),(7.5)and(7.11),wegettheconclusion.
11
asρ→1.(7.11)
References
[1]J.Abate,G.L.ChoudhuryandW.Whitt,“CalculatingtheM/G/1busy-perioddensityand
LIFOwaiting-timedistributionbydirectnumericaltransforminversion,”Opns.Res.Letters18,113–119(1995).
[2]J.AbateandW.Whitt,“TransientbehaviorofregulatedBrownianmotion,I:startingatthe
origin,”Adv.Appl.Prob.19,560–598(1987).
[3]J.AbateandW.Whitt,“TransientbehavioroftheM/M/1queueviaLaplacetransforms,”
Adv.Appl.Prob.20,145–178(1988).
[4]J.AbateandW.Whitt,“TransientbehavioroftheM/G/1workloadprocess,”Opns.Res.42,
750–764(1994).
[5]J.AbateandW.Whitt,“Limitsandapproximationsforthebusy-perioddistributioninsingle-serverqueues,”Prob.Engr.Inf.Sci.9,581–602(1995).
[6]J.AbateandW.Whitt,“AnoperationalcalculusforprobabilitydistributionsviaLaplace
transforms,”Adv.Appl.Prob.,28,75–113(1996).
[7]P.Billingsley,ConvergenceofProbabilityMeasures,Wiley,NewYork,1968.[8]D.R.CoxandW.L.Smith,Queues,Methuen,London,1961.[9]A.Erd´elyi,AsymptoticExpansions,Dover,NewYork,1956.
[10]I.IliadisandS.W.Fuhrmann,“MomentrelationshipsforqueueswithPoissoninput,”Queue-ingSystems12,243–256(1992).
[11]J.F.C.Kingman,“Queuedisciplinesinheavytraffic,”Math.Opns.Res.7,262–271(1982).[12]F.W.J.Olver,AsymptoticsandSpecialFunctions,AcademicPress,NewYork,1974.[13]J.Riordan,“Delaysforlast-comefirst-servedserviceandthebusyperiod,”BellSystemTech.
J.40,785–793(1961).
[14]J.Riordan,StochasticServiceSystems,Wiley,NewYork,1962.[15]J.Riordan,CombinatorialIdentities,Wiley,NewYork,1968.
12
[16]L.Tak´acs,“DelaydistributionsforonelinewithPoissoninput,generalholdingtimes,and
variousordersofservice,”BellSystemTech.J.42,487–503(1973).
[17]E.Vaulot,“Delaisd’attentedesappelstelephoniquesdansl’ordreinversedeleurarrive,”C.
R.Acad.Sci.Paris238,1188–1189(1954).
[18]W.Whitt,Weakconvergencetheoremsforpriorityqueues:preemptive-resumediscipline,J.
Appl.Prob.8(1971)74–94.
[19]D.M.Wishart,“Queueingsystemsinwhichthedisciplineislast-comefirst-served,”Oper.
Res.8,591–599(1960).
13
因篇幅问题不能全部显示，请点此查看更多更全内容