Systems
arXiv:arXiv:0000.0000
MINIMIZINGTHEMAXIMUMEXPECTEDWAITINGTIMEINAPERIODICSINGLE-SERVERQUEUEWITHA
SERVICE-RATECONTROL
ByNiMa∗,andWardWhitt∗
Weconsiderasingle-serverqueuewithunlimitedwaitingspace,theFCFSdiscipline,aperiodicarrival-ratefunctionandi.i.d.servicerequirements,wheretheservice-ratefunctionissubjecttocontrol.Wepreviouslyshowedthatarate-matchingcontrol,wheretheservicerateismadeproportionaltothearrivalrate,stabilizesthequeuelengthprocess,butnotthe(virtual)waitingtimeprocess.Inordertominimizethemaximumexpectedwaitingtime(andstabilizetheexpectedwaitingtime),wenowconsideramodificationoftheservice-ratecontrolinvolvingtwoparameters:atimelagandadampingfactor.Wedevelopanefficientsimulationsearchalgorithmtofindthebesttimelaganddampingfactor.Thatsimulationalgorithmisanextensionofourrecentrare-eventsimulationalgorithmfortheGIt/GI/1queuetotheGIt/GIt/1queue,allowingthetimevaryingservicerate.Togaininsightintothesecontrols,weestablishaheavy-trafficlimitwithperiodicityinthefluidscale.Thatproducesadiffusioncontrolproblemforthestabilization,whichwesolvenumericallybythesimulationsearchinthescaledfamilyofsystemswithρ↑
1.Thestatespacecollapseinthattheoremshowsthatthereisatime-varyingLittle’slawinheavy-traffic,implyingthatthequeuelengthandwaitingtimecannotbesimultaneouslystabilizedinthislimit.Weconductsimulationexperimentsshowingthatthenewcontroliseffectiveforstabilizingtheexpectedwaitingtimeforawiderangeofmodelparameters,butwealsoshowthatitcannotstabilizetheexpectedwaitingtimeperfectly.
1.Introduction.InthispaperweaddressanopenproblemfromWhitt[31],whichconsideredtheproblemofstabilizingperformanceovertimeinasingle-serverqueuewithunlimitedwaitingspace,thefiefirst-served(FCFS)disciplineandatime-varyingarrival-ratefunction.Thestabilizationistobeachievedwithadeterministicservice-ratefunction,undertheassumptionthatthecustomerservicerequirementsarespecifiedindependentlyoftheservice-ratecontrol. Thereisalargeliteratureonsettingstaffinglevels(thenumberofservers)inamulti-serverqueuetostabilizeperformanceinfaceoftime-varyingde- ∗DepartmentofIndustrialEngineeringandOperationsResearch,ColumbiaUniversityKeywordsandphrases:nonstationaryqueues,queueswithtime-varyingarrivalrate,stabilizingperformance,heavytrafficlimits,serviceratecontrols
1 2
N.MAANDW.WHITT mand,e.g.,[8,13,19,26].Forasingle-serverqueue,thedirectanalogwouldbeturningonandofftheserver,whichhasreceivedconsiderableattentioninthestationarysetting,startingwith[33,14].Asindicatedin[31],controllingtheserviceratetomeettime-varyingdemandisanalogoustoKleinrock’sclassicservice-capacity-allocationprobleminastationaryMarkovianwork[17];weallocateservicecapacityovertimeinsteadoverspace(differentqueueswithinwork). Asexplainedin§1of[31],variantsofthisserviceratecontrolareperformedinresponsetotime-varyingdemand,inmanyserviceoperations,suchashospitalsurgeryroomsandairportinspectionlines,butlittleisknownabouttheidealtimingandextentofserviceratechanges.Serviceratecontrolsforsingle-serverqueuesarealsoofcurrentinterestwithinplexsystems,suchasinenergy-efficientdatacentersinputing[18]andinbusinessprocessmanagement[28]. Giventhattheservicerequirementsarespecifiedindependently,theactualservicetimesresultingfromatime-varyingcontrolareplicated,butaconstructionisgivenin§3.1of[31].In[31],severalcontrolswereconsidered,butmostattentionwasgiventotherate-matchingcontrol,whichchoosestheserviceratetobeproportionaltothearrivalrate;i.e.,foragiventargettrafficintensityρ,theservice-ratefunctionis (1.1) µ(t)≡λ(t)/ρ,t≥
0, with≡denotingequalitybydefinition.In[31],Theorem4.2showsthattherate-matchingcontrolstabilizesthequeue-lengthprocess;Theorem5.1givesanexpressionforthewaiting-timewiththeratematchingcontrol,whileTheorems5.2and5.3establishheavy-trafficlimitsshowingthatthequeue-lengthisasymptoticallystable,butthewaitingtimeisnot,beingasymptoticallyinverselyproportionaltothearrival-ratefunction. 1.1.TheOpenProblem:StabilizingtheWaitingTime.Theopenproblemfrom[31]isdevelopingaservice-ratecontrolthatcanstabilizetheexpectedwaitingtime.(Weonlydiscussthecontinuous-timevirtualwaitingtimeprocessinthispaper,whichisthewaitingtimeofapotentialorhypotheticalcustomerifitweretoarriveatthattime,andsoomit“virtual.”)Towardthatend,wenowstudyamodificationoftherate-matchingcontrol.Withoutlossofgenerality,wewritetheperiodicarrival-ratefunctionas (1.2) λ(t)≡ρ(1+s(t)),t≥
0, where0<ρ<1andsisaperiodicfunctionwithperiodcsatisfying (1.3) s¯≡1cs(u)du≡0.c0 PERIODICSINGLE-SERVERQUEUE
3 Asaregularitycondition,werequirethat (1.4)sL≤s(t)≤sUforalltwith−10,
sothatβistherelativeamplitude,with0≤β<1,andtheperiodisc=2π/γ.
Intheperiodicsettingof(1.2)-(1.4),weconsidertherate-matchingcontrolin(1.1)modifiedbyatimelagηanddampingfactorξ;inparticular,
(1.6)
µ(t)≡1+ξs(t−η)),t≥
0, for0<ξ≤1andη>
0.Thus,theaveragearrivalrateandservicerateareλ¯=ρandµ¯=1,sothatthelong-runtrafficintensityisρ¯≡λ¯/µ¯=ρ.However,theinstantaneoustrafficintensityρ(t)≡λ(t)/µ(t)cansatisfyρ(t)>1forsometineachperiodiccycleifβ>(1−ρ)/ρ. 1.2.FormulationofOptimalControlProblems.Becauseitisdirectlyofinterest,andbecausewewanttoallowforimperfectstabilization,weformulateourcontrolproblemasminimizingthemaximumexpectedwaitingtimeoveraperiodiccycle[0,c].Weformulatethemainoptimizationproblemasamin-maxproblem,i.e., (1.7) w∗≡minmax{E[Wy]}, µ(t)∈M(1)0≤y≤
1 whereE[Wy]istheexpected(periodic)steady-state(virtual)waitingtimestartingattimeycwithinacycleoflengthc,0≤y1.Wehavenotyetsolvedthisgeneraloptimizationproblem.Hereareopenproblems,applyingtotheMarkovianMt/Mt/1modelandgeneralizations:
1.Forthegeneralperiodicproblem,whatisthesolution(valueofw∗andsetofoptimalservice-ratefunctionsµ∗(t)asafunctionofthemodel)?
2.Forthesinusoidalspecialcasein(1.5),whatisthesolution?
3.Towhatextentdotheoptimalsolutionsstabilizetheexpectedwaiting timeE[Wy]overtime?
Inparticular,isitpossibletostabilizeE[Wy]perfectly?
4 N.MAANDW.WHITT Inthispaper,weonlyconsidertherestrictedsetofcontrolsin(1.6).Nowourgoalis (1.8) w∗(η,ξ)≡minmax{E[Wy]}. η,ξ0≤y≤
1 Forpracticalpurposes,thistwo-parametercontrolisappealingforitssimplicity.Wealsofindthatitisquiteeffective,eventhoughitcannotstabilizeE[Wy]perfectly. Wealsoconsidertheassociatedstabilizationcontrol,where(1.8)isreplacedby (1.9) ws∗tab(η,ξ)≡min{max{E[Wy]}−min{E[Wy]}}. η,ξ0≤y≤
1 0≤y≤
1 Inourexamples,wefindthatthesolutionsto(1.8)and(1.9)arethesame(butwehavenoproof),butneitherstabilizesperfectly. 1.3.ThePrimaryTool:ASimulationSearchAlgorithm.Ourprimarytoolforfindinggood(η,ξ)controlsisasimulationsearchalgorithm.Forthatpurpose,weextendtherare-eventsimulationalgorithmforthetime-varyingworkloadprocessintheperiodicGIt/GI/1modelin[21]totheGIt/GIt/1model,wheretheservicerateistime-varyingaswell.(ThenotationGItmeansthattheprocessisadeterministictimetransformationofarenewalprocess;see§
2.)TheworkloadL(t)representstheamountofworkinservicetimeinthesystemattimet,whilethewaitingtimecanberepresentedasthefirst-passagetime (1.10) t+u W(t)=inf{u≥0: µ(s)ds=L(t)}. t ThewaitingtimeW(t)coincideswiththeworkloadL(t)whenµ(t)=1forallt,butnototherwise. Asin[21],therare-eventsimulationalgorithmcalculatestheperiodicsteady-stateworkloadLyandwaitingtimeWy,startingattimeycwithinacycleoflengthc,0≤y<
1.Weemployasearchovertheparameters(η,ξ),asdiscussedin§3,inordertosolvetheoptimizationproblems(1.8)and(1.9).Thesearchpartisrelativelyelementarybecausewehaveonlytwocontrolparameters.Forbackgroundonsimulationoptimization,see[10,16]andthereferencesthere. plexityforonecontrolvector(η,ξ)isessentiallythesameasin[21].Inparticular,theprogramrunningtimetendstobeproportionaltothenumberofreplicationsandnumberofyvalues,which PERIODICSINGLE-SERVERQUEUE
5 forthecaseρ=0.8inFigure1weretakentobe40,000and40,respectively.Thatrequiredabout100minutesonaputer.Asindicatedin§4.7of[21],theruntimetendstobeoforder(1−ρ)−1,sothatthecaseswithhightrafficintensityaremorechallenging.Thesimulationsearchisperformedinstages,withfeweryvaluesandreplicationsintheearlystages,butthefulllongrunattheendtoconfirmperformance. 1.4.SimulationExamplesfortheMt/Mt/1Model.Toillustratetheeffectivenessofournewalgorithm,weshowresultsfortwosimulationexamples.WeconsidertheMarkovianMt/Mt/1modelwiththesinusoidalarrivalratefunctionin(1.2)-(1.5).Thefirstexamplehasmodelparameters(ρ,β,γ)=(0.8,0.2,0.1),sothattheaveragearrivalrateisρ¯=0.8,theaverageservicetimeis1andthecyclelengthisc=2π/γ=62.8.Figure1(left)showsthesteady-statewaitingtimeE[Wy]togetherwiththecorrespondingexpectedworkloadE[Ly]andtheproductλ(y)E[Wy],allfor0≤y<
1.Thesecondexampleontherightdiffersonlybyincreasingρfrom0.8to0.95.(Thecaseρ=0.9isshowninFigure5(right)in§
7.)Figure1alsoshowstheupperandlower95%confidence-intervalboundsforE[Ly]andE[Wy]withblackdashedlines,butthesecanonlybeseenbyzoomingin. 54.84.64.44.2 43.83.63.43.2 30 10 20 30 40 50 60 70 26 25 24 23 22 21 20 19 18 17 16 15
0 10 20 30 40 50 60 70 Fig
1.Estimatesoftheperiodicsteady-statevaluesofE[Wy](bluesolidline),E[Ly](reddashedline)andλ(y)E[Wy](greendottedline)fortheoptimalcontrol(η∗,ξ∗)forthesinusoidalexamplewithparametertriples(ρ,β,γ)=(0.8,0.2,0.1)(left)and(0.95,0.2,0.1)(right),sothatthecyclelengthisc=2π/γ=62.8.Theoptimalcontrolsare(5.84,0.84)forρ=0.8and(15.1,2.13)forρ=0.95. Figure1showsthattheexpectedwaitingtimeE[Wy]iswellstabilizedatavaluesomewhathigherthantheexpectedsteady-statewaitingtimeforthestationaryM/M/1model,whichisρ/(1−ρ)(4ontheleftand19ontheright).Themaximumdeviation(maximum-minimum)overacycleis0.0335isforρ=0.8and0.4653forρ=0.95.Thusthemaximumrelative
6 N.MAANDW.WHITT errorsareabout0.8%forρ=0.8and2.2%forρ=0.95,clearlyadequateforpracticalapplications.Nevertheless,carefulsimulationsandstatisticalanalysisallowustoconcludethatitisimpossibletostabilizetheexpectedwaitingtimeperfectlywiththiscontrol.Toseethecontrastingviewwiththerate-matchingcontrolforthissamemodel,seeFigure5(left)in§7orFigure6of[31]. Remark1.1.(thecostofperiodicity)ThedifferencebetweenthestableaveragewaitingtimeinFigure1andthevalueρ/(1−ρ)forthestationarymodel(4ontheleftand19ontheright)mightbecalled“theaveragecostofperiodicity,”butwepointoutthattheoverallaveragewaitingtimewithaservice-ratecontrolcouldbemuchlessthaninthestationarymodel.SeeExample10.1. Remark1.2.(thesingle-parameteralternative)Itisnaturaltowonderifwecoulduseonlythesinglecontrolparameterη,fixingξ=
1.Ifweletξ=1andoptimizeoverηinthesettingofFigure1,thenforρ=0.8(ρ=0.95)wegetη∗=5.93(η∗=28.3)andamaximumdeviationof0.4109(3.034),whichyieldsabout10%(14%)relativeerrorinsteadof0.8%(2.2%).(Figure7in§7showstheanalogofFigure1.)Hence,weusethetwocontrolparameters. 1.5.GainingAdditionalInsight:Heavy-TrafficLimits.Tobetterunderstandhowthecontrolparametersandperformancedependsonthemodelparameters,weestablishheavy-traffic(HT)limits,whichinvolveconsideringafamilyofmodelsindexedbyρandlettingρ↑1,drawingonourpreviousworkin[30,31,21].Thatpreviousworkshowsthatthescalingisveryimportant,becausethereareseveralpossibilities.WeusetheconventionalHTscalingoftimeby(√1−ρ)−2(usuallydenotedbyn)andspaceby1−ρ(usuallydenotedby1/n),asinChapters5and9of[29],butifwedosowithoutalsoscalingthearrival-ratefunction,thentheHTlimitiseasilyseentobethesameasiftheperiodicitywerereplacedbytheconstantlong-runaverage,asshownbyFalin[7]. Toobtaininsightintotheperiodicdynamics,itisthusimportanttoalsoscalethearrival-ratefunction.However,thepapers[30]and[31]actuallyusetwodifferentHTscalingsofthearrival-ratefunction.OurmainHTscalingin§4follows[31]andhasperiodicityinfluidscale,i.e., (1.11) λρ(t)≡ρ(1+s((1−ρ)2t),t≥
0, butin§8wealsoconsiderthescalingfrom[30]and[21],whichhasthe PERIODICSINGLE-SERVERQUEUE
7 periodicityindiffusionscale,i.e., (1.12) λρ(t)≡ρ(1+(1−ρ)s((1−ρ)2t),t≥
0. Theextentoftheperiodicityisstrongerin(1.11)thanin(1.12).TheworkloadandthewaitingtimehavethesameHTlimitwiththediffusionscalescalingin(1.12),butdifferentlimitswiththefluid-scalescalingin(1.11).TocapturethecleardifferencesshowninFigure1,weobviouslywantthestrongerfluidscalingin(1.11).TheHTfunctionalcentrallimittheorem(FCLT)inTheorem4.2forthescalingin(1.11)in§4helpsinterpretFigure1. Itisimportanttonotethatifwehaveconstantserviceratewiththisscaling,thenthewaitingtimesexplodeasρ↑1,becausetheinstantaneoustrafficintensityρ(t)≡λ(t)>1overintervalsgrowingasρ↑1;thiscaseisanalyzedin[6].WealsoestablishaHTfunctionalweaklawoflargenumbers(FWLLN)inTheorem4.1,butitisnotveryuseful,becauseitshowsthatourproposedcontrolwithξ=1stabilizesthewaitingtimeperfectlyforallηasρ↑1(Butithelpstoseethatnothingbadhappens.) 1.6.OrganizationofthePaper.Weelaborateonthemodelandkeyprocessesrepresentingtheworkloadandthewaitingtimein§
2.Wediscusstheextensionoftherare-eventsimulationalgorithmfrom[21]tooursettinganditsapplicationtoperformsimulationsearchin§
3.Inboth§2and§3wewillbebriefbecausewecandrawupon[31]and[21].Weestablishheavy-trafficlimitsinthediffusionscalingin(1.11)in§
4.Wegivesimulationexamplesinthatsettingin§
5.Wepresenttheproofofthemainheavy-trafficlimit,Theorem4.2,in§
6.Weprovideresultsofadditionalsimulationexperimentsin§
7.Weestablishheavy-trafficlimitsinthediffusionscalingin(1.12)in§8andwegivesimulationexamplesinthatsettingin§
9.Wedrawconclusionsin§10.
2.TheModel.Inthissectionwespecifythegeneralmodel,definingthearrivalprocessin§2.1andthebasicqueueingstochasticprocessesin§2.2.WespecializetotheperiodicGt/Gt/1modelin§2.3.Weshowthattheworkloadisstabilizedbytherate-matchingcontrolin(1.1),extendingtheresultsforthequeue-lengthprocessin[31]. 2.1.TheArrivalProcess.WerepresenttheperiodicarrivalcountingprocessAasadeterministictimetransformationofanunderlyingrate-1countingprocessNby (2.1) A(t)≡N(Λ(t)), t whereΛ(t)≡λ(s)ds,
0 t≥
0.
8 N.MAANDW.WHITT whereλisthearrival-ratefunction.ThisismonrepresentationwhenNisarate-1Poissonprocess;thenAisanonhomogeneousPoissonprocess(NHPP).FortheGt/Gt/1model,Nisunderstoodtobearate-1stationarypointprocess.Hence,fortheGIt/GIt/1model,Nisanequilibriumrenewalprocesswithtimebetweenrenewalshavingmean1,forwhichthefirstinterrenewaltimehastheequilibriumdistribution.Therepresentationin(2.1)hasbeenusedfrequentlyforprocessesNmoregeneralthanNHPP’s,anearlysourcebeingby[22]. Forthesinusoidalarrival-ratefunctionin(1.5),theassociatedcumulativearrival-ratefunctionis (2.2) Λ(t)=ρ(t+(β/γ)(1−cos(γt)),t≥
0. Weonlyconsiderthecaseρ<1,underwhichapropersteady-stateexistsunderregularityconditions(whichwedonotdiscusshere).Behaviordiffersforshortcyclesandlongcycles.Forthecaseofaconstantservicerate,therearetwoimportantcasesfortherelativeamplitude:(i)0<β<ρ−1−1and(ii)ρ−1−1≤β≤
1.Inthefirstcase,wehaveρ(t)<1forallt,whereρ(t)≡λ(t)istheinstantaneoustrafficintensity,butinthesecondcasewehaveintervalswithρ(t)≥1,wheresignificantcongestioncanbuildup.Ifthereisalongcycleaswell,thesystemmaybebetterunderstoodfromfluidanddiffusionlimits,asin[6].However,thatdifficultycanbeavoidedbyaservice-ratecontrol. 2.2.TheGeneralGt/Gt/1ModelwithaService-RateControl.Weconsideramodificationofthestandardsingle-serverqueuewithunlimitedwaitingspacewherecustomersareservedinorderofarrival.Let{Vk}bethesequenceofservicerequirements.Asin[31],weseparatelydefinetherateatwhichserviceisperformedfromtheservicerequirement.GiventhearrivalcountingprocessA(t)definedin§2.1,letthetotalinputofworkovertheinterval[0,t]betherandomsum (2.3) A(t) Y(t)≡Vk, k=
1 t≥
0. Letservicebeperformedattimetatrateµ(t)wheneverthereisworktoperform.ParallelingthecumulativearrivalrateΛ(t)definedin(2.1),letthecumulativeavailableserviceratebe (2.4) t M(t)≡µ(s)ds,
0 t≥
0. PERIODICSINGLE-SERVERQUEUE
9 Let-inputprocessofworkbeX(t)≡Y(t)−M(t),t≥
0.ThenwecanapplythereflectionmaptoinputprocessX(t)torepresenttheworkload(theremainingworkinservicetime)attimet,startingemptyattime0,as L(t)=X(t)−inf{X(s):0≤s≤t}=sup{X(t)−X(s):0≤s≤t},t≥
0. Inthissettingitiselementarythatthecontinuous-timewaitingtimeattimet,whichwedenotebyW(t),canberelatedtoL(t). Lemma2.1.(waitingtimerepresentation)Thewaitingtimeattimetcanberepresentedas (2.5) W(t)=Mt−1(L(t)),t≥
0, whereMt−1istheinverseofMt(u)≡M(t+u)−M(t)forM(t)in(2.4). Proof.Bydefinition, t+u W(t)=inf{u≥0: µ(s)ds=L(t)} t (2.6) =inf{u≥0:M(t+u)−M(t)=L(t)}=Mt−1(L(t)), forMt(u)above,asclaimedin(2.5). 2.3.ThePeriodicGt/Gt/1Model.Asin[21],weconsidertheperiodicsteadystateoftheperiodicGt/Gt/1modelwitharrival-ratefunctionin(1.2).Forthatpurpose,weexploitthearrivalprocessconstructionin(2.1)intermsofthestationaryprocessesN≡{N(t):t≥0}andV≡{Vk:k≥1}in(2.1).Lettheassociatedservice-ratefunctionµ(t)alsobeperiodicwithcyclelengthc,withaverageserviceratebeµ¯=1,andbounds0<µL≤µ(t)≤µU<∞,for0≤t≤c. Asin[21]andearlierin[20]andChapter6in[25],Wenowconvertthestandardrepresentationoftheworkloadprocessin§2toasimplesupremumbyusingareverse-timeconstruction.Todoso,weextendthestationaryprocesses{N(t)}and{Vk}totheentirerealline.Weregardtheperiodicarrival-rateandservice-rateasdefinedontheentirereallineaswell,withthefunctionsfixedbytheirpositionwithintheperiodiccycleattime0.Withthoseconditions,thereverse-timeconstructionisachievedbylettingtheinterarrivaltimesandservicetimesbeorderedinreversetimegoingbackwardsfromtime0.ThenA˜(t)countsthenumberofarrivalsin[−t,0],Y˜(t)isthetotalinputin[−t,0]andX˜(t)isinputin[−t,0],fort≥
0. 10
N.MAANDW.WHITT Toexploitthereverse-timerepresentation,let (2.7) Λ˜y(t)≡Λ(yc)−Λ(yc−t),t≥
0, bethereverse-timecumulativearrival-ratefunctionstartingattimeycwithintheperiodiccycle[0,c],0≤y<1,andΛ˜−y1isitsinversefunction,whichiswelldefinedbecauseΛ˜y(t)iscontinuousandstrictlyincreasing. Asananalogof(2.7)forthecumulativeservicerate,let (2.8) M˜y(t)≡M(yc)−M(yc−t),t≥
0, WelettheservicerequirementsefromageneralstationarysequencewithE[Vk]=
1. Withthisreverse-timerepresentation,theworkloadattimeycinthe systemstartingemptyattimeyc−tcanberepresentedas Ly(t)=(2.9)=d sup{X˜y(s)} 0≤s≤t sup 0≤s≤t N(Λ˜y(s)) Vk−M˜y(s) k=
1 =sup 0≤s≤Λ˜y(t) N(s) Vk−M˜y(Λ˜−y1(s)), k=
1 whereX˜yistheinputofworkstartingattimeycwithinthecycleoflengthc.Theotherquantitiesin(2.9)arethereverse-timecumulativearrival-ratefunctionΛ˜y(t)in(2.7)withinverseΛ˜−y1(t)andthereverse-timecumulativeservice-ratefunctionM˜yin(2.8)withinverseM˜y−
1. Theequalityindistributionin(2.9)holdsbecauseNisastationarypoint process,whichisapointprocesswithstationaryincrementsandaconstant rate. Ast→∞,Ly(t)↑Ly(∞)≡Lyw.p.1ast→∞,for (2.10) Ly=dsup s≥
0 N(s) Vk−M˜y(Λ˜−1(s)), k=
1 0≤y<
1. Eventhough(2.9)isvalidforallt,wethinkofthesystemstartingemptyattimes−kc,fork≥1,sothatweletyc−t=−kcor,equivalently,westipulatethatt=c(k+y),0≤y1.
Wenowobservethatthetimetransformationin(2.9)showsthattheperiodicGt/Gt/1modelisactuallyequivalenttoaG/Gt/1modelwithastationaryarrivalprocessandanewcumulativeserviceratefunctionM˜y(Λ˜−y1(t)).
PERIODICSINGLE-SERVERQUEUE
11
Corollary2.1.(conversionofGt/Gt/1toanequivalentGt/G/1)Inadditiontorepresentingtheperiodicsteady-stateworkloadLyinaperiodicGt/Gt/1modelasaperiodicsteady-stateworkloadinaperiodicG/Gt/1model,whichhasastationarystochasticinputandadeterministicservice
rate,asshownin(2.10)above,wecanrepresentitasaperiodicsteady-state
workloadinaperiodicGt/G/1model,whichhasaperiodicstochasticinputandaconstantservicerate,via
(2.11)
N(Λ˜(M˜−1(s)))
Ly=sup{
Vk−s:s≥0}.
k=
1 Corollary2.2.(theassociatedperiodicsteady-statewaitingtime)Theperiodicsteady-statewaitingtimeassociatedwiththeperiodicsteady-stateworkloadin(2.10)is (2.12) Wy=M˜y−1(Ly),0≤y<
1. Proof.ApplythereasoningofLemma2.1.In[31]weshowedthattherate-matchingservice-ratecontrolin(1.1)sta- bilizesthequeue-lengthprocess.Nowweestablishthecorrespondingresultfortheworkload. Theorem2.1.(stabilizingtheperiodicworkload)Iftherate-matchingcontrolin(1.1)isused,thenLy=dLforLyin(2.10),whereListhesteadystateworkloadintheassociated(stable)stationaryG/G/1model,i.e., (2.13) L=dsup s≥
0 N(s) Vk−ρ−1s, k=
1 whichisindependentofy. Proof.Withtheratematchingcontrol,wehaveM(t)=cΛ(t)andM˜y(t)=cΛ˜y(t),t≥
0.Asaconsequence,M˜y(Λ˜−y1(t)=ct,t≥0,sothat (2.14) N(s) Ly=dsup Vk−M˜y(Λ˜−y1(s) s≥0k=
1 =dsup s≥
0 N(s) Vk−cs k=
1 =dL. 12
N.MAANDW.WHITT
3.TheSimulationSearchAlgorithm.Therare-eventsimulationalgorithmfrom[21]exploitstheclassicrare-eventsimulationalgorithmfortheGI/GI/1queue,exploitingimportancesamplingusinganexponentialchangeofmeasure,asinCh.XIIIof[1]andCh.VIof[2].HenceoursimulationalgorithmappliestotheGIt/GIt/1queue.Itwasshownin[21]thatthealgorithmiseffectiveforestimatingthemeanaswellassmalltailprobabilities. 3.1.TheGIt/GIt/1Model.IntheGIt/GIt/1setting,theunderlyingrate-1processNisanequilibriumrenewalprocess,whichmeansthatU1hasthestationary-excessorequilibriumdistributionUe,whichmaybedifferentfromthei.i.d.distributionsofUk,k≥2,in(2.9).AlsointheGIt/GIt/1setting,theservicetimesVk’sarei.i.d.withdistributionV,andareindependentofthearrivalprocess. Thesimulationalgorithmexploitsthediscrete-timerepresentationofthe workloadLyin(2.10)andthewaitingtimeWy,i.e., (3.1) N(s) Ly=dsup Vk−M˜y(Λ˜−1(s)) s≥0k=
1 =dsup n≥
0 n n Vk−M˜y(Λ˜−1(Uk)), k=
1 k=
1 Wy=dMy−1(Ly),0≤y<
1. whereMyisthesameasMt,whichistheforwardintegraloftheservice ratestartingfrompositionywithinacycle. Wereferto[21]forbackground.Inthatsetting,weusetheunderly- ingmeasurePθ∗determinedforGI/GI/1queue.Weagainusethesame notationsXk(ρ)=Vk−ρ−1UkandpartialsumprocessSn≡ nk=
1 Xk for GI/GI/1anddefinethenewassociatedprocessQn≡ nk=
1 Vk −M˜y (Λ˜−y1 ( nk=
1 Uk )), whichistheprocessinsidethesupremumfunction.Thentheestimatorof therare-eventprobabilityforWycanbederivedasbelow: (3.2) P(Wy>b)=P(My−1(Ly)>b)=P(Ly>My(b)) =P(τMQy(b)<∞)=Eθ∗[LτMQy(b)(θ∗)] = Eθ∗[mX (θ ∗ )m
X (θ ∗ )(τMQ y ( b) − 1) − e θ ∗
S τ QM y ( b) ]
1 θ∗SQ =mX1(θ∗)Eθ∗[eτMy(b)]. PERIODICSINGLE-SERVERQUEUE 13 AgainthefirstX1(ρ)inthepartialsumSτQhasadifferentdistributionMy(b) from{Xk,k≥2}. 3.2.TheExtendedAlgorithmfortheGIt/GIt/1Model.Hereisasummaryoftheextendedalgorithmtoestimatethetailprobabilitiesinthe GIt/GIt/1queuewithaverageservicerate1andaveragearrivalrateρ:
1.Constructatableoftheinversecumulativearrival-ratefunctionρΛ˜−y1(sameasforGIt/GI/1).
2.Determinetherequiredlengthofpartialsums(ns)neededineachapplication(sameasforGIt/GI/1).
3.Foreachreplication,wegeneratetherequiredvectorsofexponentiallytiltedinterarrivaltimesρ−1U˜andservicetimesV˜fromFρ−−θ1∗UandFVθ∗respectively(sameasforGIt/GI/1).
4.CalculatetheassociatedvectorsofSnandQnandfindoutthepingtimeτMQy(b),whichisthehittingtimeofQnatlevelMy(b).ThisstepisdifferentfromforGIt/GI/1inthatfirstweneedtocalculateMy(b)asthehittinglevelinsteadofbandsecondwecalculatevectorQndifferentfromRninanadditionalfunctionM˜yinthesecondterm.
5.UsetheaboveestimatortocalculatethetailprobabilityP(Wy>b)foreachreplication(sameasforGIt/GI/1).
6.RunNi.i.d.replicationsandcalculatethemeanoftheestimatedval- uesofP(Wy>b)(sameasforGIt/GI/1). 3.3.ExplicitrepresentationsfortheSinusoidalCase.Herewesummarizetheexpressionsforallthebasicdeterministicratefunctionsinoursinusoidalexamples,extending(1.5),(1.6)and(2.2): (3.3) Λ˜y(t)=ρ(t+β(cos(γ(t−yc))−cos(γyc)))γ M(t)=t−ξβ(cos(γ(t−η))−cos(γη))γβ My(t)=t−ξγ(cos(γ(t+yc−η))−cos(γ(yc−η)))M˜y(t)=t+ξβ(cos(γ(t+η−yc))−cos(γ(η−yc))). γ 3.4.TheSearchAlgorithm.Weuseanelementaryiterativesearchalgorithm,fixinganinitialvalueofηatthemeanforthesteady-statemodel,ρ/(1−ρ),andsearchingfirstoverξandthenovereachvariableuntilwegetnegligibleimprovement.Thatsimpleapproachissubstantiatedbyestimatingthestructureoftheobjectivefunction.Figure2illustratesbyshowingthe 14
N.MAANDW.WHITT maximumwaitingtimemax0≤y≤c{E[Wy]}inthesettingofFigure1(left).Figure2showsestimatesofthemaximumwaitingtimemax0≤y≤c{E[Wy]}asafunctionof(η,ξ)in[0,20]×[0,5](left)[3,9]×[0.6,1.0](right)inthatsetting.Figure2showsthatthefunctionisnotconvexasafunctionofη,butsuggeststhatitisunimodalwithauniqueglobalminimum,supportingoursimpleprocedure.Similarplotsforthemaximumdeviationmax0≤y≤c{E[Wy]}−max0≤y≤c{E[Wy]}areshowninFigure4in§
7. maximummeanwait 20 18 16 14 12 10
8 6 420 15
5 4 10
3 5
2 1 00 4.6 4.5 4.4 4.3 4.2 4.1 41 0.9
9 8 0.8
7 6 0.7
5 4 0.63 Fig2.Three-dimensionalplotsofestimatesofthemaximumwaitingtimemax0≤y≤c{E[Wy]}for(η,ξ)in[0,20]×[0,5](left)[3,9]×[0.6,1.0](right). Weperformthesearchwithfewerpointsyandreplicationsintheinitialstages,andthenconfirmwithmorepoints,40valuesofyand40,000replications,whichyieldsexcellentstatisticalprecision,ascanbeseenfromthenarrowconfidenceintervalbandsinFigure1.
4.SupportingHeavy-TrafficLimitsforPeriodicQueues.Inthissectionweobtainaheavy-traffic(HT)functionalweaklawoflargenumbers(FWLLN)andaHTfunctionalcentrallimittheorem(FCLT)fortheperiodicGt/Gt/1modelwithageneralservice-ratecontroloftheformin(1.6).TheHTFCLTproducesalimitdependingonanasymptotictimelagη∗anddampingfactorξ∗,whicharisefromHTlimits;seecondition(4.26)inTheorem4.2andtheconclusionin(4.18).Thuswereducetheoptimizationproblemsovertheparameterpairs(ηρ,ξρ)in(1.8)and(1.9),asymptoticallyasρ↑1,todiffusioncontrolproblemswiththeparameterpairs(η∗,ξ∗). 4.1.TheUnderlyingRate-1Processes.AsinmuchoftheHTliterature,westartbyintroducingbasicrate-1stochasticprocesses,buthereweconsiderservicerequirementsinsteadofservicetimes.Weassumethattherate-1arrivalandservice-requirementsprocessesNandVspecifiedin§2areindependentandeachsatisfiesaFCLT.Tostatetheresult,letNˆnaandSˆnvbe PERIODICSINGLE-SERVERQUEUE 15 thescaledprocessesdefinedby(4.1) Nˆna(t)≡n−1/2[Na(nt)−nt]and ⌊nt⌋ Sˆnv(t)≡n−1/2[Vk−nt], i=
1 t≥
0, with≡denotingequalityindistributionand⌊x⌋denotingthegreatestintegerlessthanorequaltox.Weassumethat (4.2) Nˆna⇒caBaandSˆnv⇒csBsinDasn→∞, whereDistheusualfunctionspaceofright-continuousreal-valuedfunctions on[
0,∞)withleftlimitsand⇒denotesconvergenceindistribution,as in[29],whileBaandBsareindependentstandard(mean0,variance1)Brownianmotionprocesses(BM’s).Theassumedindependenceimpliesjoint convergencein(4.2)byTheorem11.4.4of[29]. WeemphasizethatGIassumptionsarenotneeded,butthatisanimpor- tantspecialcase.IftheservicetimesVkarei.i.d.mean-1randomvariableswithvariance,alsothesquaredcoefficientofvariation(scv),c2s,thenthelimitin(4.2)holdswithservicevariabilityparametercs.Similarly,ifthebasearrivalprocessisarenewalprocessoranequilibriumrenewalprocesswithtimesbetweenrenewalshavingmean1andvariance(andscv)c2a,thenthelimitin(4.2)holdswitharrivalvariabilityparameterca.(See[23]fortheoreticalsupportinthecaseofanequilibriumrenewalprocess.) ForthequeueingHTFCLT,wewillapplyTheorem9.3.4of[29],which referstotheconditionsofTheorem9.3.3.Thoseconditionsrequireajoint FCLTforthepartialsumsofthearrivalandserviceprocesses,notably(3.9)onp.295.ThatconvergencefollowsfromtheFCLT’sweassumedforNˆnaandSˆnvin(4.2)above.Inparticular,theassumedFCLTforNnaimpliestheassociatedFCLTforthepartialsumsoftheinterarrivaltimesbyTheorem 7.3.2andCorollary7.3.1of[29]. 4.2.AFamilyofModels.AsabasisfortheHTFCLT,wecreateamodelforeachρ,0<ρ<
1.Wedosobydefiningthearrival-rateandservice-ratefunctions. 4.2.1.TheArrival-RateandService-RateFunctions..Letthearrivalratefunctioninmodelρbeasin(1.11)inthesettingof(1.2)-(1.4).Asafurtherregularitycondition,wealsorequirethatthefunctionsbeanelementofthefunctionspaceD,asin[29].Thentheassociatedcumulativearrival-ratefunctioninmodelρbe (4.3) Λρ(t)≡ρ(t+(1−ρ)−2S((1−ρ)2t),t≥
0, 16
N.MAANDW.WHITT where (4.4) t S(t)≡s(u)du,
0 forsagainbeingtheperiodicfunctionin(1.2)-(1.4).From(4.3)-(4.4),we seethattheassociatedarrival-ratefunctionobtainedbydifferentiationin (4.3)isindeedλρ(t)in(1.11).Thetimescalingin(1.11)and(4.3)impliesthattheperiodinmodelρ witharrival-ratefunctionλρ(t)in(1.11)iscρ=c(1−ρ)−2,wherecistheperiodofs(t)in(1.2)-(1.4).Thustheperiodcρinmodelρisgrowingwithρ.ThisscalingfollowsLemma5.1andTheorem5.2of[31],withntherereplacedby(1−ρ)−
2.Inparticular,thescalinghereisinfluidorFWLLN scale,andthusisdifferentfromthediffusionorFCLTscalinginTheorem 3.2of[30]andTheorem2of[21].LetAρ(t)≡Na(Λρ(t))bethearrivalprocessinmodelρ,whichisobtained byusingthecumulativearrival-ratefunctionΛρin(4.3)inplaceofΛin(2.1).Giventhatdefinition,weseethatthecumulativearrivalrateisindeed (4.5) E[Aρ(t)]=E[Na(Λρ(t))]=Λρ(t),t≥
0. Wenowdefineassociatedscaledtime-varyingservice-ratefunctions.Thesearetherate-matchingservice-ratefunctionsin[31]modifiedbyatimelagandadampingfactor.Inparticular, (4.6) µρ(t)≡1+ξρs((1−ρ)2(t−ηρ))and t Mρ(t)≡ µρ(u)du=t
0 +(1−ρ)−2ξρS((1−ρ)2(t−ηρ)), t≥
0, wheresistheperiodicfunctionwithperiodcin(1.3),whileηρistheρdependenttimelagandξρistheρ-dependentdampingfactor.From(4.6)and(1.3),weseethattheaverageservicerateisµ¯ρ=1forallρ.Asaconsequence,theaveragetrafficintensityisλ¯ρ/µ¯ρ=ρforallρ,whiletheinstantaneoustrafficintensityattimetisλρ(t)/µρ(t),t≥0,whichisaplicatedperiodicfunction,againwithperiodc. 4.2.2.TheAssociatedQueueingProcesses.Havingdefinedthefamilyof arrivalprocessesAρ(t)anddeterministicservice-ratefunctionsMρ(t)above,wedefinetheotherqueueingprocessesYρ(t),Xρ(t),Lρ(t)andWρ(t)asin§2.2.Letpleted-workprocessbedefinedby (4.7) Cρ(t)≡Yρ(t)−Lρ(t),t≥
0. PERIODICSINGLE-SERVERQUEUE 17 WenowcanapplyLemma2.1in§2toexpressthewaitingtimeprocessas (4.8)Wρ(t)≡inf{u≥0:Mρ(t+u)−Mρ(t)≥Lρ(t)},t≥
0. The(virtual)waitingtimeWρ(t)representsthetimethatahypotheticalarrivalattimetwouldhavetowaitbeforestartingservice. Asin(3.7)and(3.8)of[31],wecandefinethequeue-lengthprocess(numberinsystem)andthedepartureprocessinmodelρjointly.Wecanalsoexpressthedepartureprocessintermsoftheworkloadprocessinsteadofthequeue-lengthprocessby (4.9) Dρ(t)≡Ns t µρ(s)1{Lρ(s)>0}ds,
0 t≥
0, butwedonotfocusonthedepartureandqueue-lengthprocesseshere. 4.3.TheScaledQueueingProcesses.WestartwiththeFWLLN-scaledprocesses.Firstletthescaleddeterministicratefunctionsbe(4.10)Λ¯ρ(t)≡(1−ρ)2Λρ((1−ρ)−2t)andM¯ρ(t)≡(1−ρ)2Mρ((1−ρ)−2t),t≥
0, forΛρ(t)in(4.3)andMρ(t)in(4.6).Weimmediatelyseethat (4.11) Λ¯ρ→ΛfinDasρ↑
1, where (4.12) Λf(t)≡t+S(t),t≥
0, forS(t)in(4.4).LettheFWLLN-scaledarrivalarrivalstochasticprocessbedefinedby (4.13) A¯ρ(t)≡(1−ρ)2Aρ((1−ρ)−2t), Lettheinput,-input,workload,pleted-workandponentsoftheFWLLN-scaledthevector(A¯ρ,Y¯ρ,X¯ρ,L¯ρ,C¯ρ,W¯ρ)bedefinedinthesameway. ThenlettheassociatedFCLT-scaleddeterministicratefunctionsbedefinedby (4.14) Λˆρ(t)≡(1−ρ)[Λρ((1−ρ)−2t)−(1−ρ)−2Λf(t)],Mˆρ(t)≡(1−ρ)[Mρ((1−ρ)−2t)−(1−ρ)−2Λf(t)] 18
N.MAANDW.WHITT forΛfin(4.12).LettheassociatedFCLT-scaledstochasticprocessesbedefinedby (4.15) Aˆρ(t)≡(1−ρ)[Aρ((1−ρ)−2t)−(1−ρ)−2Λf(t)],Yˆρ(t)≡(1−ρ)[Yρ((1−ρ)−2t)−(1−ρ)−2Λf(t)],Xˆρ(t)≡(1−ρ)Xρ((1−ρ)−2t),Lˆρ(t)≡(1−ρ)Lρ((1−ρ)−2t),Cˆρ(t)≡(1−ρ)[Cρ((1−ρ)−2t)−(1−ρ)−2Λf(t)],Wˆρ(t)≡(1−ρ)Wρ((1−ρ)−2t),t≥
0. 4.4.TheHTFWLLN.WestartwiththeHTFWLLN.LetDkbethekfoldproductspaceofDwithitself,let⇒denoteconvergenceindistributionandletx◦ybepositionfunctiondefinedby(x◦y)(t)≡x(y(t)). Theorem4.1.(HTFWLLN)Underthedefinitionsandassumptionsin§4above,ifξρ→ξandηρ→ηasρ↑1,andthesystemstartsemptyattime0,then (4.16) M¯ρ→MfinD,whereMf(t)≡t+ξS(t−η) and (4.17)(A¯ρ,Y¯ρ,X¯ρ,L¯ρ,C¯ρ,W¯ρ)⇒(A¯,Y¯,X¯,L¯,C¯,W¯)inD6asρ↑
1 for(A¯ρ,Y¯ρ,X¯ρ,L¯ρ,C¯ρ,W¯ρ)definedin(4.13),where A¯(t)≡Y¯(t)≡Λf(t),X¯(t)≡S(t)−ξS(t−η),t≥η, L¯(t)≡sup{X(t)−X(t−s)},t≥c+η,C¯≡Y¯−L¯,and 0≤s≤c (4.18) W¯(t)≡inf{u≥0:Mf(t+u)−Mf(t)≥L¯(t)},t≥
0. forΛf(t)in(4.12)withS(t)in(4.4),Mf(t)in(4.16)andψbeingthereflectionmap. Proof.Weessivelyapplythecontinuousmappingtheorem(CMT)usingthefunctionsin§12.7and§§13.2-13.6of[29].First,observethat(4.16)isaminormodificationof(4.10).LetN¯ρaandS¯ρdenoteN¯naandS¯nv,respectively,where,paralleling(4.1),weletN¯na(t)≡n−1Na(nt)andS¯nv≡n−1S⌊vnt⌋,t≥0,andthenletn=(1−ρ)−
2.ThenobservethatA¯ρ=N¯ρa◦Λ¯ρandY¯ρ=S¯ρ◦A¯ρ,sothatwecanapplytheCMTwithpositionmap.ThelimitforX¯ρfollowsfromtheCMTwithaddition PERIODICSINGLE-SERVERQUEUE 19 andthenthelimitforL¯ρfollowsfromtheCMTwiththereflectionmap.ToestablishthelimitforthescaledwaitingtimeW¯ρ(t)inDweapplytheCMTwiththeinversefunction.Finally,ThelimitforC¯ρagainfollowsfromtheCMTwithaddition. Weobtainstrongerresultsinspecialcases: Corollary4.1.(FWLLNfortherate-matchingserviceratecontrol)InadditiontotheconditionsofTheorem4.1,ifη=0andξ=1,thenMf(t)=Λf(t),t≥0,andthenX¯(t)=L¯(t)=W¯(t)=0forallt≥0,whileC¯=Y¯=A¯=Λf. Corollary4.2.(stabilizingthewaitingtimeatanypositivevalue)In additiontotheconditionsofTheorem4.1,ξ=1,sothatMf(t)=0,0≤t<η,andMf(t)=Λf(t−η),t≥η,forafixedtimelagη>0,then (4.19) t L¯(t)=X¯(t)≡X¯η(t)=Λf(t)−Λf(t−η)=λf(s)ds>0 t−η and (4.20) W¯(t)=ηforallt≥η. Corollary4.3.(sinusoidalwithdampedtimelag)InadditiontotheconditionsofTheorem4.1,supposethat (4.21) s(t)≡βsin(γt),t≥
0, forpositiveconstantsβandγwithβ<1,sothats(t)isperiodicwithperiodc≡cγ=2π/γ.Then (4.22) S(t)=(β/γ)(1−cos(γt)),t≥η, sothat L¯(t)=(β/γ)([ξcos(γ(t−η))−cos(γt)] +sup{cos(γ(t−s))−ξcos(γ(t−η−s))} 0≤s≤c =(β/γ)([ξcos(γ(t−η))−cos(γt)] (4.23) +sup{cos(γs)−ξcos(γ(s−η))}),t≥c+η. 0≤s≤c Forthespecialcaseξ=
1,W¯(t)=η.Ifinaddition,andη<π/γ,thesupremumin(4.23)isattainedats∗=(π/2γ)−η/2),sothat (4.24)L¯(t)=(β)([cos(γ(t−η))−cos(γt)]+[cos((π/2)−(γη/2))−cos((π/2)+(γη/2))]) γ 20
N.MAANDW.WHITT fort≥c+η.Asη↓
0, (4.25) L¯(t)/η→1+βsin(γt)=1+s(t). 4.5.TheHTFCLT.WenowstatetheFCLT,whichhasperiodicityinfluidscale,asin(1.11).Theproofappearsin§
6. Theorem4.2.(HTFCLT)Inadditiontothedefinitionsandassumptionsin§4above,includingthescaledarrival-ratefunctionin(1.11),assumethattheperiodicfunctions(t)in(1.3)iscontinuousand (4.26) (1−ρ)ηρ→η∗andξρ−1→ξ∗asρ↑1,1−ρ where0≤η∗<∞and0≤ξ∗<∞.Thenthereisalimitforthescaledcumulativeservice-ratefunctionsMρin(4.6)and(4.14);i.e., (4.27) Mˆρ(t)≡(1−ρ)[Mρ((1−ρ)−2t)−(1−ρ)−2(t+S(t))]→Mˆ(t)≡−s(t)η∗+S(t)ξ∗inDasρ↑
1 fors(t)in(1.3)andS(t)in(4.4).If,inaddition,thesystemstartsemptyattime0,then (4.28)(Aˆρ,Yˆρ,Xˆρ,Lˆρ,Wˆρ,Cˆρ)⇒(Aˆ,Yˆ,Xˆ,Lˆ,Wˆ,Cˆ)inD5asρ↑
1 for(Aˆρ,Yˆρ,Xˆρ,Lˆρ,Wˆρ,Cˆρ)definedin(4.15),where Aˆ(t)≡(caBa−e)◦Λf(t),Yˆ(t)≡(cxB−e)◦Λf(t),Xˆ(t)≡Yˆ(t)−Mˆ(t)=Yˆ(t)+s(t)η∗−S(t)ξ∗, =(cxB◦Λf)(t)−Λf(t)+s(t)η∗−S(t)ξ∗,(4.29)Lˆ(t)≡ψ(Xˆ)(t)andWˆ(t)≡Lˆ(t)/µf(t), Cˆ(t)≡Yˆ(t)−Lˆ(t),t≥
0. withcx≡c2a+c2s,BaBMandµf(t)≡λf(t)≡1+s(t),t≥0,thelimitingarrival-ratefunction. Wenowdrawattentiontosomeimportantconsequences.First,Theorem4.2establishesaHTtime-varying(TV)Little’slaw(LL),parallelingthemany-serverheavy-traffic(MSHT)TVLLin[27].Thisisatime-varyingversionofthefamiliarstate-spacecollapse,whichgoesbacktotheearlyHTpapers.Weremarkthattherelationisdifferentfromthetime-varyingLLdiscussedin[3,9]and[32]. PERIODICSINGLE-SERVERQUEUE 21 Corollary4.4.(HTtime-varyingLittle’slaw)UndertheconditionsofTheorem4.2,thelimitprocessesarerelatedby (4.30) Lˆ(t)=λf(t)Wˆ(t),t≥0,w.p.1. Corollary4.5.(thecaseofnovariability)Ifcx=0inadditiontotheconditionsofTheorem4.2,then (4.31) Xˆ(t)=−t+s(t)η∗−S(t)(ξ∗+1),t≥
0, sothatLˆ(t)=Wˆ(t)=0forallt≥0ifXˆ(t)≤0forallt≥
0. Theorem4.2reducesthequestionofasymptoticstabilityoftheprocessesLˆρ(t)andWˆρ(t),andtheexpectedvaluesofvariousfunctionals,suchasE[h(Lˆρ(t))]andE[h(Wˆρ(t))](assumingappropriateuniformintegrability)todiffusioncontrolproblemswiththeobjectivefunctionsin(1.8)and(1.9).Toexpressthestabilizationgoals,wealsoformulatetwodefinitionsofasymptoticstability,whichinvolvebothlargetimetandlargeρ. Evenfortalone,therearemanypossiblydefinitionsofasymptoticstabilityast→∞;e.g.,see[15].Forbothρandt,weomitissuesoflimitinterchangeast→∞andρ↑1,astreatedforexamplein[12],[11]and[5]inothercontexts.SinceourlimitprocessisaMarkovdiffusionprocess,weactuallyobtainastrongerconclusion,forwhichwegiveaseconddefinition. Definition4.1.(asymptoticstabilityforstochasticprocesses)Wesaythatascaledstochasticprocess{Zˆρ(t):t≥0}isasymptoticallystableasρ↑1(inHT)if (4.32)Zˆρ⇒ZˆinDasρ↑1,whereZˆ(t)⇒Zˆ(∞)ast→∞ foraproperrandomvariableZˆ(∞). Definition4.2.(asymptoticallystableandMarkov)Wesaythatascaledstochasticprocess{Zˆρ(t):t≥0}isasymptoticallystableandMarkovasρ↑1if (4.33) Zˆρ⇒ZˆinDasρ↑
1, where{Zˆ(t):t≥0}isaMarkovprocess,forwhichthereexistsaproperinitialdistributionZˆ(0)suchthatthelimitprocess{Zˆ(t):t≥0}isastationaryMarkovprocess. 22
N.MAANDW.WHITT Corollary4.6.(asymptoticallystableandMarkov)UndertheconditionsofTheorem4.2, (a)thescaledworkloadprocess{Lˆρ(t):t≥0}(respectively,waitingtimeprocess{Wˆρ(t):t≥0})isasymptoticallystableandMarkovasρ↑1ifandonlyifthereareasymptoticparametersη∗andξ∗andinitialdistributionsLˆ
(0)(respectively,Wˆ
(0))forthelimitingdiffusionprocessLˆ(respectively,Wˆ)suchthatthelimitprocessisstationary. (b)Ifη∗=ξ∗−1=0,aswiththerate-matchingservice-ratecontrolin[31],thenthescaledworkloadprocess{Lˆρ(t):t≥0}isasymptoticallystableandMarkov.Giventhatλf(t)isperiodicandnotconstant,thescaledwaiting-timeprocessisnotstable,byeitherDefinition4.1orDefinition4.2. (c)Thereexistasymptoticparametersη∗andξ∗satisfying(4.26)suchthatthescaledwaiting-timeprocess{Wˆρ(t):t≥0}isasymptoticallystableandMarkovifandonlyifthescaledworkloadprocess{Lˆρ(t)/λf(t):t≥0}isasymptoticallystableandMarkov. Proof.For(a),observethatthe-inputprocessXˆisXˆ=(cxB−e)◦Λf,whichisthedeterministictimetransformationΛfofordinaryBrownianmotionwithdrift,cxB−e.Thus,Lˆ=ψ(cxB−e)◦Λf)esastationaryprocessifweletLˆ(0)havetheexponentiallimitingdistributionoftheRBM,insteadofLˆ
(0)=0,asassumedforsimplicitytoplicationsinvolvingtheinitialconditions.TheremainingstatementsaredirectconsequencesofTheorem4.2. Wenowestablishconditionsfortheoptimalityofan(η∗,ξ∗)controlforthelimitingdiffusioncontrolproblemforeitherformulation(1.8)or(1.9).Ourproofwillexploituniformintegrability(UI);seep.31of[4]. Corollary4.7.(optimalityforthelimitingdiffusionprocess)ConsiderthespecialcaseoftheGIt/GIt/1modelwithE[Uk2+ǫ]<∞andE[Vk2+ǫ]<∞forsomeǫ>
0.If(ηρ∗,ξρ∗)→(η∗,ξ∗)asρ→1,where(ηρ∗,ηρ∗)istheoptimalcontrolforproblem(1.8)or(1.9),thenthelimitingcontrol(η∗,ξ∗)isoptimalforthecorrespondingdiffusioncontrolproblem. Proof.Welet(η˜,ξ˜)beanyalternativecontrolforthelimitingdiffusioonprocess.Thenlet(η˜ρ,ξ˜ρ)beanassociatedcontrolformodelρ,0<ρ<1,whereη˜ρ≡η˜/(1−ρ)andη˜ρ≡1+(1−ρ)ξ˜.Then,bythisconstruction,condition(4.26)holdsforthefamily(η˜ρ,ξ˜ρ).Wenextwanttoshowthattheconvergenceindistributioncanbeextendedtoconvergenceofthemeansfor PERIODICSINGLE-SERVERQUEUE 23 allt,whichrequiresuniformintegrabilityuniformlyint;seep.31of[4].We usetheboundsonthesecondmomentstoshowthatitholds. Towardthatend,weexploittheupperboundsfortheworkloadprocess intheGt/Gt/1modelintermsoftheassociatedworkloadprocessinthe stationaryG/G/1modelfrom§3of[21].Theseboundsextenddirectlyto theGt/Gt/1modelbyvirtueofCorollary2.1.Theseboundsshowthatthe meanworkloadisboundedaboveuniformlyinyovertheinterval[0,c].These boundsalsoapplytothewaitingtimeprocessbecauseW(t)≤L(t)/µ
L, whereµL>0isalowerboundontheservicerate,whichfollowsfrom (1.4)and(1.6).ForthestationaryGI/GI/1model,finitesecondmoments implytheexistenceofthefirstmomentsofthewaitingtimeanduniform integrabilityneededforconvergence;seep.31of[4]and§X.2andX.7of[1]. Finally, we observe that our optimal policy (ηρ∗ , ξ ∗ρ ) has expected value greaterthanorequaltothealternativepolicy(η˜ρ,ξ˜ρ)forallρ,whileboth convergeasρ→
1.Hence,thelimitoftheoptimalpolicies,(η∗,ξ∗)mustbe atleastasgoodas(η˜,ξ˜). WeapplyCorollary4.6tosupportournumericalcalculationsbyobserv- ing that (ηρ∗ , ξ ∗ρ ) when scaled as in (4.26) converges to a limit. We thus deducethatthelimitmustbetheoptimalpolicyforthediffusion.However, thisnumericalevidenceisnotamathematicalproof.Moreover,whilethe numericalevidenceisgood,itisnotexceptionallygood,especiallyforξρ∗as canbeseenfromTable1in§5below.
5.SimulationExamplesintheSettingof§
4.Inthissectionwereportresultsofsimulationexperimentstoevaluatethenew(ηρ,ξρ)controlsasafunctionofρformodelsscaledordingtoTheorem4.2,specificallyby(1.11),(4.3)and(4.6),sothatwecanseethesystematicbehavior. Table1showsresultsforfourvaluesofthetrafficintensityρwithρ↑1forthesinusoidalmodelin(1.2)-(1.6)withHTscalingin(1.11)withparameters(ρ,βρ,γρ)=(ρ,0.2,2.5(1−ρ)2).Forthiscase,wefoundthatthesolutionstooptimizationproblems(1.8)and(1.9)areidentical,towithinourstatisticalprecision.Hence,oursolutionsareforbothproblems. Table1showstheestimatedcontrolsηρandξρineachcase,plusscaledversionsconsistentwithcondition(4.26).Table1showsthattherelativeerrorisroughlyindependentofρ,beinglessthan1%ineachcase.Table1alsoshowsthatthelimitη∗≈1.45israpidlyapproachedby(1−ρ)ηρ/ρ,whilethelimitξ∗≈1.8isroughlyapproachedby(1−ρ)/ρηρ,bothofwhichareconsistentwithcondition(4.26).TheresultssupportTheorem4.2,butunfortunatelytherateofconvergenceinthecontrolparametersisnotfast.Evidentlythedampingcontrolξρismoreproblematic. 24
N.MAANDW.WHITT Table1 The(identical)solutionstotheminimaxandminimum-deviationoptimizationproblemsin(1.8)and(1.9)forthesinusoidalmodelin(1.2)-(1.6)withHTscalingin(1.11)withparameters(ρ,βρ,γρ)=(ρ,0.2,2.5(1−ρ)2).Thereportedmeanwaitingtimesarewithout spacescaling. ρβρ≡βγρηρ(1−ρ)ηρ/ρξρ(1−ξρ)/(1−ρ)maxE[Wy]min(max−min)averagewaitrelativeerror 0.80.20.15.801.450.8420.794.030.0324.020.8% 0.90.20.02512.941.440.8891.119.100.0919.071.0% 0.950.20.0062527.71.460.9311.3819.290.14319.210.7% 0.9750.20.001562556.61.450.9601.6039.610.36439.470.9% ForthemodelinTable1,Figure3showstheexpectedperiodicsteadystatevirtualwaitingtime(solidblueline),theexpectedsteady-stateworkload(thedashedredline)andarrivalratemultipliedbythemeanwaitingtime(thedottedgreenline)forρ=0.8(left)andρ=0.95(right).AsinFigure1,the95%confidenceintervalbandsareincluded,buttheycanonlybeseenbyzoomingin. Wealsoconsideredalternativevaluesoftherelativeamplitudeβ.Table2showsthesolutionstotheminimum-deviationoptimizationproblemin(1.9)forthesinusoidalmodelinTable1exceptβhasbeenincreasedtoβ=0.8from0.2.Table2showsthattherelativeerrorisroughlyindependentofρ,buttherelativeerrorhasincreasedtoabout10%fromabout1%ininTable1.UnlikeinFigure3,itisev
1.Thestatespacecollapseinthattheoremshowsthatthereisatime-varyingLittle’slawinheavy-traffic,implyingthatthequeuelengthandwaitingtimecannotbesimultaneouslystabilizedinthislimit.Weconductsimulationexperimentsshowingthatthenewcontroliseffectiveforstabilizingtheexpectedwaitingtimeforawiderangeofmodelparameters,butwealsoshowthatitcannotstabilizetheexpectedwaitingtimeperfectly.
1.Introduction.InthispaperweaddressanopenproblemfromWhitt[31],whichconsideredtheproblemofstabilizingperformanceovertimeinasingle-serverqueuewithunlimitedwaitingspace,thefiefirst-served(FCFS)disciplineandatime-varyingarrival-ratefunction.Thestabilizationistobeachievedwithadeterministicservice-ratefunction,undertheassumptionthatthecustomerservicerequirementsarespecifiedindependentlyoftheservice-ratecontrol. Thereisalargeliteratureonsettingstaffinglevels(thenumberofservers)inamulti-serverqueuetostabilizeperformanceinfaceoftime-varyingde- ∗DepartmentofIndustrialEngineeringandOperationsResearch,ColumbiaUniversityKeywordsandphrases:nonstationaryqueues,queueswithtime-varyingarrivalrate,stabilizingperformance,heavytrafficlimits,serviceratecontrols
1 2
N.MAANDW.WHITT mand,e.g.,[8,13,19,26].Forasingle-serverqueue,thedirectanalogwouldbeturningonandofftheserver,whichhasreceivedconsiderableattentioninthestationarysetting,startingwith[33,14].Asindicatedin[31],controllingtheserviceratetomeettime-varyingdemandisanalogoustoKleinrock’sclassicservice-capacity-allocationprobleminastationaryMarkovianwork[17];weallocateservicecapacityovertimeinsteadoverspace(differentqueueswithinwork). Asexplainedin§1of[31],variantsofthisserviceratecontrolareperformedinresponsetotime-varyingdemand,inmanyserviceoperations,suchashospitalsurgeryroomsandairportinspectionlines,butlittleisknownabouttheidealtimingandextentofserviceratechanges.Serviceratecontrolsforsingle-serverqueuesarealsoofcurrentinterestwithinplexsystems,suchasinenergy-efficientdatacentersinputing[18]andinbusinessprocessmanagement[28]. Giventhattheservicerequirementsarespecifiedindependently,theactualservicetimesresultingfromatime-varyingcontrolareplicated,butaconstructionisgivenin§3.1of[31].In[31],severalcontrolswereconsidered,butmostattentionwasgiventotherate-matchingcontrol,whichchoosestheserviceratetobeproportionaltothearrivalrate;i.e.,foragiventargettrafficintensityρ,theservice-ratefunctionis (1.1) µ(t)≡λ(t)/ρ,t≥
0, with≡denotingequalitybydefinition.In[31],Theorem4.2showsthattherate-matchingcontrolstabilizesthequeue-lengthprocess;Theorem5.1givesanexpressionforthewaiting-timewiththeratematchingcontrol,whileTheorems5.2and5.3establishheavy-trafficlimitsshowingthatthequeue-lengthisasymptoticallystable,butthewaitingtimeisnot,beingasymptoticallyinverselyproportionaltothearrival-ratefunction. 1.1.TheOpenProblem:StabilizingtheWaitingTime.Theopenproblemfrom[31]isdevelopingaservice-ratecontrolthatcanstabilizetheexpectedwaitingtime.(Weonlydiscussthecontinuous-timevirtualwaitingtimeprocessinthispaper,whichisthewaitingtimeofapotentialorhypotheticalcustomerifitweretoarriveatthattime,andsoomit“virtual.”)Towardthatend,wenowstudyamodificationoftherate-matchingcontrol.Withoutlossofgenerality,wewritetheperiodicarrival-ratefunctionas (1.2) λ(t)≡ρ(1+s(t)),t≥
0, where0<ρ<1andsisaperiodicfunctionwithperiodcsatisfying (1.3) s¯≡1cs(u)du≡0.c0 PERIODICSINGLE-SERVERQUEUE
3 Asaregularitycondition,werequirethat (1.4)sL≤s(t)≤sUforalltwith−1
0, for0<ξ≤1andη>
0.Thus,theaveragearrivalrateandservicerateareλ¯=ρandµ¯=1,sothatthelong-runtrafficintensityisρ¯≡λ¯/µ¯=ρ.However,theinstantaneoustrafficintensityρ(t)≡λ(t)/µ(t)cansatisfyρ(t)>1forsometineachperiodiccycleifβ>(1−ρ)/ρ. 1.2.FormulationofOptimalControlProblems.Becauseitisdirectlyofinterest,andbecausewewanttoallowforimperfectstabilization,weformulateourcontrolproblemasminimizingthemaximumexpectedwaitingtimeoveraperiodiccycle[0,c].Weformulatethemainoptimizationproblemasamin-maxproblem,i.e., (1.7) w∗≡minmax{E[Wy]}, µ(t)∈M(1)0≤y≤
1 whereE[Wy]istheexpected(periodic)steady-state(virtual)waitingtimestartingattimeycwithinacycleoflengthc,0≤y
1.Forthegeneralperiodicproblem,whatisthesolution(valueofw∗andsetofoptimalservice-ratefunctionsµ∗(t)asafunctionofthemodel)?
2.Forthesinusoidalspecialcasein(1.5),whatisthesolution?
3.Towhatextentdotheoptimalsolutionsstabilizetheexpectedwaiting timeE[Wy]overtime?
Inparticular,isitpossibletostabilizeE[Wy]perfectly?
4 N.MAANDW.WHITT Inthispaper,weonlyconsidertherestrictedsetofcontrolsin(1.6).Nowourgoalis (1.8) w∗(η,ξ)≡minmax{E[Wy]}. η,ξ0≤y≤
1 Forpracticalpurposes,thistwo-parametercontrolisappealingforitssimplicity.Wealsofindthatitisquiteeffective,eventhoughitcannotstabilizeE[Wy]perfectly. Wealsoconsidertheassociatedstabilizationcontrol,where(1.8)isreplacedby (1.9) ws∗tab(η,ξ)≡min{max{E[Wy]}−min{E[Wy]}}. η,ξ0≤y≤
1 0≤y≤
1 Inourexamples,wefindthatthesolutionsto(1.8)and(1.9)arethesame(butwehavenoproof),butneitherstabilizesperfectly. 1.3.ThePrimaryTool:ASimulationSearchAlgorithm.Ourprimarytoolforfindinggood(η,ξ)controlsisasimulationsearchalgorithm.Forthatpurpose,weextendtherare-eventsimulationalgorithmforthetime-varyingworkloadprocessintheperiodicGIt/GI/1modelin[21]totheGIt/GIt/1model,wheretheservicerateistime-varyingaswell.(ThenotationGItmeansthattheprocessisadeterministictimetransformationofarenewalprocess;see§
2.)TheworkloadL(t)representstheamountofworkinservicetimeinthesystemattimet,whilethewaitingtimecanberepresentedasthefirst-passagetime (1.10) t+u W(t)=inf{u≥0: µ(s)ds=L(t)}. t ThewaitingtimeW(t)coincideswiththeworkloadL(t)whenµ(t)=1forallt,butnototherwise. Asin[21],therare-eventsimulationalgorithmcalculatestheperiodicsteady-stateworkloadLyandwaitingtimeWy,startingattimeycwithinacycleoflengthc,0≤y<
1.Weemployasearchovertheparameters(η,ξ),asdiscussedin§3,inordertosolvetheoptimizationproblems(1.8)and(1.9).Thesearchpartisrelativelyelementarybecausewehaveonlytwocontrolparameters.Forbackgroundonsimulationoptimization,see[10,16]andthereferencesthere. plexityforonecontrolvector(η,ξ)isessentiallythesameasin[21].Inparticular,theprogramrunningtimetendstobeproportionaltothenumberofreplicationsandnumberofyvalues,which PERIODICSINGLE-SERVERQUEUE
5 forthecaseρ=0.8inFigure1weretakentobe40,000and40,respectively.Thatrequiredabout100minutesonaputer.Asindicatedin§4.7of[21],theruntimetendstobeoforder(1−ρ)−1,sothatthecaseswithhightrafficintensityaremorechallenging.Thesimulationsearchisperformedinstages,withfeweryvaluesandreplicationsintheearlystages,butthefulllongrunattheendtoconfirmperformance. 1.4.SimulationExamplesfortheMt/Mt/1Model.Toillustratetheeffectivenessofournewalgorithm,weshowresultsfortwosimulationexamples.WeconsidertheMarkovianMt/Mt/1modelwiththesinusoidalarrivalratefunctionin(1.2)-(1.5).Thefirstexamplehasmodelparameters(ρ,β,γ)=(0.8,0.2,0.1),sothattheaveragearrivalrateisρ¯=0.8,theaverageservicetimeis1andthecyclelengthisc=2π/γ=62.8.Figure1(left)showsthesteady-statewaitingtimeE[Wy]togetherwiththecorrespondingexpectedworkloadE[Ly]andtheproductλ(y)E[Wy],allfor0≤y<
1.Thesecondexampleontherightdiffersonlybyincreasingρfrom0.8to0.95.(Thecaseρ=0.9isshowninFigure5(right)in§
7.)Figure1alsoshowstheupperandlower95%confidence-intervalboundsforE[Ly]andE[Wy]withblackdashedlines,butthesecanonlybeseenbyzoomingin. 54.84.64.44.2 43.83.63.43.2 30 10 20 30 40 50 60 70 26 25 24 23 22 21 20 19 18 17 16 15
0 10 20 30 40 50 60 70 Fig
1.Estimatesoftheperiodicsteady-statevaluesofE[Wy](bluesolidline),E[Ly](reddashedline)andλ(y)E[Wy](greendottedline)fortheoptimalcontrol(η∗,ξ∗)forthesinusoidalexamplewithparametertriples(ρ,β,γ)=(0.8,0.2,0.1)(left)and(0.95,0.2,0.1)(right),sothatthecyclelengthisc=2π/γ=62.8.Theoptimalcontrolsare(5.84,0.84)forρ=0.8and(15.1,2.13)forρ=0.95. Figure1showsthattheexpectedwaitingtimeE[Wy]iswellstabilizedatavaluesomewhathigherthantheexpectedsteady-statewaitingtimeforthestationaryM/M/1model,whichisρ/(1−ρ)(4ontheleftand19ontheright).Themaximumdeviation(maximum-minimum)overacycleis0.0335isforρ=0.8and0.4653forρ=0.95.Thusthemaximumrelative
6 N.MAANDW.WHITT errorsareabout0.8%forρ=0.8and2.2%forρ=0.95,clearlyadequateforpracticalapplications.Nevertheless,carefulsimulationsandstatisticalanalysisallowustoconcludethatitisimpossibletostabilizetheexpectedwaitingtimeperfectlywiththiscontrol.Toseethecontrastingviewwiththerate-matchingcontrolforthissamemodel,seeFigure5(left)in§7orFigure6of[31]. Remark1.1.(thecostofperiodicity)ThedifferencebetweenthestableaveragewaitingtimeinFigure1andthevalueρ/(1−ρ)forthestationarymodel(4ontheleftand19ontheright)mightbecalled“theaveragecostofperiodicity,”butwepointoutthattheoverallaveragewaitingtimewithaservice-ratecontrolcouldbemuchlessthaninthestationarymodel.SeeExample10.1. Remark1.2.(thesingle-parameteralternative)Itisnaturaltowonderifwecoulduseonlythesinglecontrolparameterη,fixingξ=
1.Ifweletξ=1andoptimizeoverηinthesettingofFigure1,thenforρ=0.8(ρ=0.95)wegetη∗=5.93(η∗=28.3)andamaximumdeviationof0.4109(3.034),whichyieldsabout10%(14%)relativeerrorinsteadof0.8%(2.2%).(Figure7in§7showstheanalogofFigure1.)Hence,weusethetwocontrolparameters. 1.5.GainingAdditionalInsight:Heavy-TrafficLimits.Tobetterunderstandhowthecontrolparametersandperformancedependsonthemodelparameters,weestablishheavy-traffic(HT)limits,whichinvolveconsideringafamilyofmodelsindexedbyρandlettingρ↑1,drawingonourpreviousworkin[30,31,21].Thatpreviousworkshowsthatthescalingisveryimportant,becausethereareseveralpossibilities.WeusetheconventionalHTscalingoftimeby(√1−ρ)−2(usuallydenotedbyn)andspaceby1−ρ(usuallydenotedby1/n),asinChapters5and9of[29],butifwedosowithoutalsoscalingthearrival-ratefunction,thentheHTlimitiseasilyseentobethesameasiftheperiodicitywerereplacedbytheconstantlong-runaverage,asshownbyFalin[7]. Toobtaininsightintotheperiodicdynamics,itisthusimportanttoalsoscalethearrival-ratefunction.However,thepapers[30]and[31]actuallyusetwodifferentHTscalingsofthearrival-ratefunction.OurmainHTscalingin§4follows[31]andhasperiodicityinfluidscale,i.e., (1.11) λρ(t)≡ρ(1+s((1−ρ)2t),t≥
0, butin§8wealsoconsiderthescalingfrom[30]and[21],whichhasthe PERIODICSINGLE-SERVERQUEUE
7 periodicityindiffusionscale,i.e., (1.12) λρ(t)≡ρ(1+(1−ρ)s((1−ρ)2t),t≥
0. Theextentoftheperiodicityisstrongerin(1.11)thanin(1.12).TheworkloadandthewaitingtimehavethesameHTlimitwiththediffusionscalescalingin(1.12),butdifferentlimitswiththefluid-scalescalingin(1.11).TocapturethecleardifferencesshowninFigure1,weobviouslywantthestrongerfluidscalingin(1.11).TheHTfunctionalcentrallimittheorem(FCLT)inTheorem4.2forthescalingin(1.11)in§4helpsinterpretFigure1. Itisimportanttonotethatifwehaveconstantserviceratewiththisscaling,thenthewaitingtimesexplodeasρ↑1,becausetheinstantaneoustrafficintensityρ(t)≡λ(t)>1overintervalsgrowingasρ↑1;thiscaseisanalyzedin[6].WealsoestablishaHTfunctionalweaklawoflargenumbers(FWLLN)inTheorem4.1,butitisnotveryuseful,becauseitshowsthatourproposedcontrolwithξ=1stabilizesthewaitingtimeperfectlyforallηasρ↑1(Butithelpstoseethatnothingbadhappens.) 1.6.OrganizationofthePaper.Weelaborateonthemodelandkeyprocessesrepresentingtheworkloadandthewaitingtimein§
2.Wediscusstheextensionoftherare-eventsimulationalgorithmfrom[21]tooursettinganditsapplicationtoperformsimulationsearchin§
3.Inboth§2and§3wewillbebriefbecausewecandrawupon[31]and[21].Weestablishheavy-trafficlimitsinthediffusionscalingin(1.11)in§
4.Wegivesimulationexamplesinthatsettingin§
5.Wepresenttheproofofthemainheavy-trafficlimit,Theorem4.2,in§
6.Weprovideresultsofadditionalsimulationexperimentsin§
7.Weestablishheavy-trafficlimitsinthediffusionscalingin(1.12)in§8andwegivesimulationexamplesinthatsettingin§
9.Wedrawconclusionsin§10.
2.TheModel.Inthissectionwespecifythegeneralmodel,definingthearrivalprocessin§2.1andthebasicqueueingstochasticprocessesin§2.2.WespecializetotheperiodicGt/Gt/1modelin§2.3.Weshowthattheworkloadisstabilizedbytherate-matchingcontrolin(1.1),extendingtheresultsforthequeue-lengthprocessin[31]. 2.1.TheArrivalProcess.WerepresenttheperiodicarrivalcountingprocessAasadeterministictimetransformationofanunderlyingrate-1countingprocessNby (2.1) A(t)≡N(Λ(t)), t whereΛ(t)≡λ(s)ds,
0 t≥
0.
8 N.MAANDW.WHITT whereλisthearrival-ratefunction.ThisismonrepresentationwhenNisarate-1Poissonprocess;thenAisanonhomogeneousPoissonprocess(NHPP).FortheGt/Gt/1model,Nisunderstoodtobearate-1stationarypointprocess.Hence,fortheGIt/GIt/1model,Nisanequilibriumrenewalprocesswithtimebetweenrenewalshavingmean1,forwhichthefirstinterrenewaltimehastheequilibriumdistribution.Therepresentationin(2.1)hasbeenusedfrequentlyforprocessesNmoregeneralthanNHPP’s,anearlysourcebeingby[22]. Forthesinusoidalarrival-ratefunctionin(1.5),theassociatedcumulativearrival-ratefunctionis (2.2) Λ(t)=ρ(t+(β/γ)(1−cos(γt)),t≥
0. Weonlyconsiderthecaseρ<1,underwhichapropersteady-stateexistsunderregularityconditions(whichwedonotdiscusshere).Behaviordiffersforshortcyclesandlongcycles.Forthecaseofaconstantservicerate,therearetwoimportantcasesfortherelativeamplitude:(i)0<β<ρ−1−1and(ii)ρ−1−1≤β≤
1.Inthefirstcase,wehaveρ(t)<1forallt,whereρ(t)≡λ(t)istheinstantaneoustrafficintensity,butinthesecondcasewehaveintervalswithρ(t)≥1,wheresignificantcongestioncanbuildup.Ifthereisalongcycleaswell,thesystemmaybebetterunderstoodfromfluidanddiffusionlimits,asin[6].However,thatdifficultycanbeavoidedbyaservice-ratecontrol. 2.2.TheGeneralGt/Gt/1ModelwithaService-RateControl.Weconsideramodificationofthestandardsingle-serverqueuewithunlimitedwaitingspacewherecustomersareservedinorderofarrival.Let{Vk}bethesequenceofservicerequirements.Asin[31],weseparatelydefinetherateatwhichserviceisperformedfromtheservicerequirement.GiventhearrivalcountingprocessA(t)definedin§2.1,letthetotalinputofworkovertheinterval[0,t]betherandomsum (2.3) A(t) Y(t)≡Vk, k=
1 t≥
0. Letservicebeperformedattimetatrateµ(t)wheneverthereisworktoperform.ParallelingthecumulativearrivalrateΛ(t)definedin(2.1),letthecumulativeavailableserviceratebe (2.4) t M(t)≡µ(s)ds,
0 t≥
0. PERIODICSINGLE-SERVERQUEUE
9 Let-inputprocessofworkbeX(t)≡Y(t)−M(t),t≥
0.ThenwecanapplythereflectionmaptoinputprocessX(t)torepresenttheworkload(theremainingworkinservicetime)attimet,startingemptyattime0,as L(t)=X(t)−inf{X(s):0≤s≤t}=sup{X(t)−X(s):0≤s≤t},t≥
0. Inthissettingitiselementarythatthecontinuous-timewaitingtimeattimet,whichwedenotebyW(t),canberelatedtoL(t). Lemma2.1.(waitingtimerepresentation)Thewaitingtimeattimetcanberepresentedas (2.5) W(t)=Mt−1(L(t)),t≥
0, whereMt−1istheinverseofMt(u)≡M(t+u)−M(t)forM(t)in(2.4). Proof.Bydefinition, t+u W(t)=inf{u≥0: µ(s)ds=L(t)} t (2.6) =inf{u≥0:M(t+u)−M(t)=L(t)}=Mt−1(L(t)), forMt(u)above,asclaimedin(2.5). 2.3.ThePeriodicGt/Gt/1Model.Asin[21],weconsidertheperiodicsteadystateoftheperiodicGt/Gt/1modelwitharrival-ratefunctionin(1.2).Forthatpurpose,weexploitthearrivalprocessconstructionin(2.1)intermsofthestationaryprocessesN≡{N(t):t≥0}andV≡{Vk:k≥1}in(2.1).Lettheassociatedservice-ratefunctionµ(t)alsobeperiodicwithcyclelengthc,withaverageserviceratebeµ¯=1,andbounds0<µL≤µ(t)≤µU<∞,for0≤t≤c. Asin[21]andearlierin[20]andChapter6in[25],Wenowconvertthestandardrepresentationoftheworkloadprocessin§2toasimplesupremumbyusingareverse-timeconstruction.Todoso,weextendthestationaryprocesses{N(t)}and{Vk}totheentirerealline.Weregardtheperiodicarrival-rateandservice-rateasdefinedontheentirereallineaswell,withthefunctionsfixedbytheirpositionwithintheperiodiccycleattime0.Withthoseconditions,thereverse-timeconstructionisachievedbylettingtheinterarrivaltimesandservicetimesbeorderedinreversetimegoingbackwardsfromtime0.ThenA˜(t)countsthenumberofarrivalsin[−t,0],Y˜(t)isthetotalinputin[−t,0]andX˜(t)isinputin[−t,0],fort≥
0. 10
N.MAANDW.WHITT Toexploitthereverse-timerepresentation,let (2.7) Λ˜y(t)≡Λ(yc)−Λ(yc−t),t≥
0, bethereverse-timecumulativearrival-ratefunctionstartingattimeycwithintheperiodiccycle[0,c],0≤y<1,andΛ˜−y1isitsinversefunction,whichiswelldefinedbecauseΛ˜y(t)iscontinuousandstrictlyincreasing. Asananalogof(2.7)forthecumulativeservicerate,let (2.8) M˜y(t)≡M(yc)−M(yc−t),t≥
0, WelettheservicerequirementsefromageneralstationarysequencewithE[Vk]=
1. Withthisreverse-timerepresentation,theworkloadattimeycinthe systemstartingemptyattimeyc−tcanberepresentedas Ly(t)=(2.9)=d sup{X˜y(s)} 0≤s≤t sup 0≤s≤t N(Λ˜y(s)) Vk−M˜y(s) k=
1 =sup 0≤s≤Λ˜y(t) N(s) Vk−M˜y(Λ˜−y1(s)), k=
1 whereX˜yistheinputofworkstartingattimeycwithinthecycleoflengthc.Theotherquantitiesin(2.9)arethereverse-timecumulativearrival-ratefunctionΛ˜y(t)in(2.7)withinverseΛ˜−y1(t)andthereverse-timecumulativeservice-ratefunctionM˜yin(2.8)withinverseM˜y−
1. Theequalityindistributionin(2.9)holdsbecauseNisastationarypoint process,whichisapointprocesswithstationaryincrementsandaconstant rate. Ast→∞,Ly(t)↑Ly(∞)≡Lyw.p.1ast→∞,for (2.10) Ly=dsup s≥
0 N(s) Vk−M˜y(Λ˜−1(s)), k=
1 0≤y<
1. Eventhough(2.9)isvalidforallt,wethinkofthesystemstartingemptyattimes−kc,fork≥1,sothatweletyc−t=−kcor,equivalently,westipulatethatt=c(k+y),0≤y
1 Corollary2.2.(theassociatedperiodicsteady-statewaitingtime)Theperiodicsteady-statewaitingtimeassociatedwiththeperiodicsteady-stateworkloadin(2.10)is (2.12) Wy=M˜y−1(Ly),0≤y<
1. Proof.ApplythereasoningofLemma2.1.In[31]weshowedthattherate-matchingservice-ratecontrolin(1.1)sta- bilizesthequeue-lengthprocess.Nowweestablishthecorrespondingresultfortheworkload. Theorem2.1.(stabilizingtheperiodicworkload)Iftherate-matchingcontrolin(1.1)isused,thenLy=dLforLyin(2.10),whereListhesteadystateworkloadintheassociated(stable)stationaryG/G/1model,i.e., (2.13) L=dsup s≥
0 N(s) Vk−ρ−1s, k=
1 whichisindependentofy. Proof.Withtheratematchingcontrol,wehaveM(t)=cΛ(t)andM˜y(t)=cΛ˜y(t),t≥
0.Asaconsequence,M˜y(Λ˜−y1(t)=ct,t≥0,sothat (2.14) N(s) Ly=dsup Vk−M˜y(Λ˜−y1(s) s≥0k=
1 =dsup s≥
0 N(s) Vk−cs k=
1 =dL. 12
N.MAANDW.WHITT
3.TheSimulationSearchAlgorithm.Therare-eventsimulationalgorithmfrom[21]exploitstheclassicrare-eventsimulationalgorithmfortheGI/GI/1queue,exploitingimportancesamplingusinganexponentialchangeofmeasure,asinCh.XIIIof[1]andCh.VIof[2].HenceoursimulationalgorithmappliestotheGIt/GIt/1queue.Itwasshownin[21]thatthealgorithmiseffectiveforestimatingthemeanaswellassmalltailprobabilities. 3.1.TheGIt/GIt/1Model.IntheGIt/GIt/1setting,theunderlyingrate-1processNisanequilibriumrenewalprocess,whichmeansthatU1hasthestationary-excessorequilibriumdistributionUe,whichmaybedifferentfromthei.i.d.distributionsofUk,k≥2,in(2.9).AlsointheGIt/GIt/1setting,theservicetimesVk’sarei.i.d.withdistributionV,andareindependentofthearrivalprocess. Thesimulationalgorithmexploitsthediscrete-timerepresentationofthe workloadLyin(2.10)andthewaitingtimeWy,i.e., (3.1) N(s) Ly=dsup Vk−M˜y(Λ˜−1(s)) s≥0k=
1 =dsup n≥
0 n n Vk−M˜y(Λ˜−1(Uk)), k=
1 k=
1 Wy=dMy−1(Ly),0≤y<
1. whereMyisthesameasMt,whichistheforwardintegraloftheservice ratestartingfrompositionywithinacycle. Wereferto[21]forbackground.Inthatsetting,weusetheunderly- ingmeasurePθ∗determinedforGI/GI/1queue.Weagainusethesame notationsXk(ρ)=Vk−ρ−1UkandpartialsumprocessSn≡ nk=
1 Xk for GI/GI/1anddefinethenewassociatedprocessQn≡ nk=
1 Vk −M˜y (Λ˜−y1 ( nk=
1 Uk )), whichistheprocessinsidethesupremumfunction.Thentheestimatorof therare-eventprobabilityforWycanbederivedasbelow: (3.2) P(Wy>b)=P(My−1(Ly)>b)=P(Ly>My(b)) =P(τMQy(b)<∞)=Eθ∗[LτMQy(b)(θ∗)] = Eθ∗[mX (θ ∗ )m
X (θ ∗ )(τMQ y ( b) − 1) − e θ ∗
S τ QM y ( b) ]
1 θ∗SQ =mX1(θ∗)Eθ∗[eτMy(b)]. PERIODICSINGLE-SERVERQUEUE 13 AgainthefirstX1(ρ)inthepartialsumSτQhasadifferentdistributionMy(b) from{Xk,k≥2}. 3.2.TheExtendedAlgorithmfortheGIt/GIt/1Model.Hereisasummaryoftheextendedalgorithmtoestimatethetailprobabilitiesinthe GIt/GIt/1queuewithaverageservicerate1andaveragearrivalrateρ:
1.Constructatableoftheinversecumulativearrival-ratefunctionρΛ˜−y1(sameasforGIt/GI/1).
2.Determinetherequiredlengthofpartialsums(ns)neededineachapplication(sameasforGIt/GI/1).
3.Foreachreplication,wegeneratetherequiredvectorsofexponentiallytiltedinterarrivaltimesρ−1U˜andservicetimesV˜fromFρ−−θ1∗UandFVθ∗respectively(sameasforGIt/GI/1).
4.CalculatetheassociatedvectorsofSnandQnandfindoutthepingtimeτMQy(b),whichisthehittingtimeofQnatlevelMy(b).ThisstepisdifferentfromforGIt/GI/1inthatfirstweneedtocalculateMy(b)asthehittinglevelinsteadofbandsecondwecalculatevectorQndifferentfromRninanadditionalfunctionM˜yinthesecondterm.
5.UsetheaboveestimatortocalculatethetailprobabilityP(Wy>b)foreachreplication(sameasforGIt/GI/1).
6.RunNi.i.d.replicationsandcalculatethemeanoftheestimatedval- uesofP(Wy>b)(sameasforGIt/GI/1). 3.3.ExplicitrepresentationsfortheSinusoidalCase.Herewesummarizetheexpressionsforallthebasicdeterministicratefunctionsinoursinusoidalexamples,extending(1.5),(1.6)and(2.2): (3.3) Λ˜y(t)=ρ(t+β(cos(γ(t−yc))−cos(γyc)))γ M(t)=t−ξβ(cos(γ(t−η))−cos(γη))γβ My(t)=t−ξγ(cos(γ(t+yc−η))−cos(γ(yc−η)))M˜y(t)=t+ξβ(cos(γ(t+η−yc))−cos(γ(η−yc))). γ 3.4.TheSearchAlgorithm.Weuseanelementaryiterativesearchalgorithm,fixinganinitialvalueofηatthemeanforthesteady-statemodel,ρ/(1−ρ),andsearchingfirstoverξandthenovereachvariableuntilwegetnegligibleimprovement.Thatsimpleapproachissubstantiatedbyestimatingthestructureoftheobjectivefunction.Figure2illustratesbyshowingthe 14
N.MAANDW.WHITT maximumwaitingtimemax0≤y≤c{E[Wy]}inthesettingofFigure1(left).Figure2showsestimatesofthemaximumwaitingtimemax0≤y≤c{E[Wy]}asafunctionof(η,ξ)in[0,20]×[0,5](left)[3,9]×[0.6,1.0](right)inthatsetting.Figure2showsthatthefunctionisnotconvexasafunctionofη,butsuggeststhatitisunimodalwithauniqueglobalminimum,supportingoursimpleprocedure.Similarplotsforthemaximumdeviationmax0≤y≤c{E[Wy]}−max0≤y≤c{E[Wy]}areshowninFigure4in§
7. maximummeanwait 20 18 16 14 12 10
8 6 420 15
5 4 10
3 5
2 1 00 4.6 4.5 4.4 4.3 4.2 4.1 41 0.9
9 8 0.8
7 6 0.7
5 4 0.63 Fig2.Three-dimensionalplotsofestimatesofthemaximumwaitingtimemax0≤y≤c{E[Wy]}for(η,ξ)in[0,20]×[0,5](left)[3,9]×[0.6,1.0](right). Weperformthesearchwithfewerpointsyandreplicationsintheinitialstages,andthenconfirmwithmorepoints,40valuesofyand40,000replications,whichyieldsexcellentstatisticalprecision,ascanbeseenfromthenarrowconfidenceintervalbandsinFigure1.
4.SupportingHeavy-TrafficLimitsforPeriodicQueues.Inthissectionweobtainaheavy-traffic(HT)functionalweaklawoflargenumbers(FWLLN)andaHTfunctionalcentrallimittheorem(FCLT)fortheperiodicGt/Gt/1modelwithageneralservice-ratecontroloftheformin(1.6).TheHTFCLTproducesalimitdependingonanasymptotictimelagη∗anddampingfactorξ∗,whicharisefromHTlimits;seecondition(4.26)inTheorem4.2andtheconclusionin(4.18).Thuswereducetheoptimizationproblemsovertheparameterpairs(ηρ,ξρ)in(1.8)and(1.9),asymptoticallyasρ↑1,todiffusioncontrolproblemswiththeparameterpairs(η∗,ξ∗). 4.1.TheUnderlyingRate-1Processes.AsinmuchoftheHTliterature,westartbyintroducingbasicrate-1stochasticprocesses,buthereweconsiderservicerequirementsinsteadofservicetimes.Weassumethattherate-1arrivalandservice-requirementsprocessesNandVspecifiedin§2areindependentandeachsatisfiesaFCLT.Tostatetheresult,letNˆnaandSˆnvbe PERIODICSINGLE-SERVERQUEUE 15 thescaledprocessesdefinedby(4.1) Nˆna(t)≡n−1/2[Na(nt)−nt]and ⌊nt⌋ Sˆnv(t)≡n−1/2[Vk−nt], i=
1 t≥
0, with≡denotingequalityindistributionand⌊x⌋denotingthegreatestintegerlessthanorequaltox.Weassumethat (4.2) Nˆna⇒caBaandSˆnv⇒csBsinDasn→∞, whereDistheusualfunctionspaceofright-continuousreal-valuedfunctions on[
0,∞)withleftlimitsand⇒denotesconvergenceindistribution,as in[29],whileBaandBsareindependentstandard(mean0,variance1)Brownianmotionprocesses(BM’s).Theassumedindependenceimpliesjoint convergencein(4.2)byTheorem11.4.4of[29]. WeemphasizethatGIassumptionsarenotneeded,butthatisanimpor- tantspecialcase.IftheservicetimesVkarei.i.d.mean-1randomvariableswithvariance,alsothesquaredcoefficientofvariation(scv),c2s,thenthelimitin(4.2)holdswithservicevariabilityparametercs.Similarly,ifthebasearrivalprocessisarenewalprocessoranequilibriumrenewalprocesswithtimesbetweenrenewalshavingmean1andvariance(andscv)c2a,thenthelimitin(4.2)holdswitharrivalvariabilityparameterca.(See[23]fortheoreticalsupportinthecaseofanequilibriumrenewalprocess.) ForthequeueingHTFCLT,wewillapplyTheorem9.3.4of[29],which referstotheconditionsofTheorem9.3.3.Thoseconditionsrequireajoint FCLTforthepartialsumsofthearrivalandserviceprocesses,notably(3.9)onp.295.ThatconvergencefollowsfromtheFCLT’sweassumedforNˆnaandSˆnvin(4.2)above.Inparticular,theassumedFCLTforNnaimpliestheassociatedFCLTforthepartialsumsoftheinterarrivaltimesbyTheorem 7.3.2andCorollary7.3.1of[29]. 4.2.AFamilyofModels.AsabasisfortheHTFCLT,wecreateamodelforeachρ,0<ρ<
1.Wedosobydefiningthearrival-rateandservice-ratefunctions. 4.2.1.TheArrival-RateandService-RateFunctions..Letthearrivalratefunctioninmodelρbeasin(1.11)inthesettingof(1.2)-(1.4).Asafurtherregularitycondition,wealsorequirethatthefunctionsbeanelementofthefunctionspaceD,asin[29].Thentheassociatedcumulativearrival-ratefunctioninmodelρbe (4.3) Λρ(t)≡ρ(t+(1−ρ)−2S((1−ρ)2t),t≥
0, 16
N.MAANDW.WHITT where (4.4) t S(t)≡s(u)du,
0 forsagainbeingtheperiodicfunctionin(1.2)-(1.4).From(4.3)-(4.4),we seethattheassociatedarrival-ratefunctionobtainedbydifferentiationin (4.3)isindeedλρ(t)in(1.11).Thetimescalingin(1.11)and(4.3)impliesthattheperiodinmodelρ witharrival-ratefunctionλρ(t)in(1.11)iscρ=c(1−ρ)−2,wherecistheperiodofs(t)in(1.2)-(1.4).Thustheperiodcρinmodelρisgrowingwithρ.ThisscalingfollowsLemma5.1andTheorem5.2of[31],withntherereplacedby(1−ρ)−
2.Inparticular,thescalinghereisinfluidorFWLLN scale,andthusisdifferentfromthediffusionorFCLTscalinginTheorem 3.2of[30]andTheorem2of[21].LetAρ(t)≡Na(Λρ(t))bethearrivalprocessinmodelρ,whichisobtained byusingthecumulativearrival-ratefunctionΛρin(4.3)inplaceofΛin(2.1).Giventhatdefinition,weseethatthecumulativearrivalrateisindeed (4.5) E[Aρ(t)]=E[Na(Λρ(t))]=Λρ(t),t≥
0. Wenowdefineassociatedscaledtime-varyingservice-ratefunctions.Thesearetherate-matchingservice-ratefunctionsin[31]modifiedbyatimelagandadampingfactor.Inparticular, (4.6) µρ(t)≡1+ξρs((1−ρ)2(t−ηρ))and t Mρ(t)≡ µρ(u)du=t
0 +(1−ρ)−2ξρS((1−ρ)2(t−ηρ)), t≥
0, wheresistheperiodicfunctionwithperiodcin(1.3),whileηρistheρdependenttimelagandξρistheρ-dependentdampingfactor.From(4.6)and(1.3),weseethattheaverageservicerateisµ¯ρ=1forallρ.Asaconsequence,theaveragetrafficintensityisλ¯ρ/µ¯ρ=ρforallρ,whiletheinstantaneoustrafficintensityattimetisλρ(t)/µρ(t),t≥0,whichisaplicatedperiodicfunction,againwithperiodc. 4.2.2.TheAssociatedQueueingProcesses.Havingdefinedthefamilyof arrivalprocessesAρ(t)anddeterministicservice-ratefunctionsMρ(t)above,wedefinetheotherqueueingprocessesYρ(t),Xρ(t),Lρ(t)andWρ(t)asin§2.2.Letpleted-workprocessbedefinedby (4.7) Cρ(t)≡Yρ(t)−Lρ(t),t≥
0. PERIODICSINGLE-SERVERQUEUE 17 WenowcanapplyLemma2.1in§2toexpressthewaitingtimeprocessas (4.8)Wρ(t)≡inf{u≥0:Mρ(t+u)−Mρ(t)≥Lρ(t)},t≥
0. The(virtual)waitingtimeWρ(t)representsthetimethatahypotheticalarrivalattimetwouldhavetowaitbeforestartingservice. Asin(3.7)and(3.8)of[31],wecandefinethequeue-lengthprocess(numberinsystem)andthedepartureprocessinmodelρjointly.Wecanalsoexpressthedepartureprocessintermsoftheworkloadprocessinsteadofthequeue-lengthprocessby (4.9) Dρ(t)≡Ns t µρ(s)1{Lρ(s)>0}ds,
0 t≥
0, butwedonotfocusonthedepartureandqueue-lengthprocesseshere. 4.3.TheScaledQueueingProcesses.WestartwiththeFWLLN-scaledprocesses.Firstletthescaleddeterministicratefunctionsbe(4.10)Λ¯ρ(t)≡(1−ρ)2Λρ((1−ρ)−2t)andM¯ρ(t)≡(1−ρ)2Mρ((1−ρ)−2t),t≥
0, forΛρ(t)in(4.3)andMρ(t)in(4.6).Weimmediatelyseethat (4.11) Λ¯ρ→ΛfinDasρ↑
1, where (4.12) Λf(t)≡t+S(t),t≥
0, forS(t)in(4.4).LettheFWLLN-scaledarrivalarrivalstochasticprocessbedefinedby (4.13) A¯ρ(t)≡(1−ρ)2Aρ((1−ρ)−2t), Lettheinput,-input,workload,pleted-workandponentsoftheFWLLN-scaledthevector(A¯ρ,Y¯ρ,X¯ρ,L¯ρ,C¯ρ,W¯ρ)bedefinedinthesameway. ThenlettheassociatedFCLT-scaleddeterministicratefunctionsbedefinedby (4.14) Λˆρ(t)≡(1−ρ)[Λρ((1−ρ)−2t)−(1−ρ)−2Λf(t)],Mˆρ(t)≡(1−ρ)[Mρ((1−ρ)−2t)−(1−ρ)−2Λf(t)] 18
N.MAANDW.WHITT forΛfin(4.12).LettheassociatedFCLT-scaledstochasticprocessesbedefinedby (4.15) Aˆρ(t)≡(1−ρ)[Aρ((1−ρ)−2t)−(1−ρ)−2Λf(t)],Yˆρ(t)≡(1−ρ)[Yρ((1−ρ)−2t)−(1−ρ)−2Λf(t)],Xˆρ(t)≡(1−ρ)Xρ((1−ρ)−2t),Lˆρ(t)≡(1−ρ)Lρ((1−ρ)−2t),Cˆρ(t)≡(1−ρ)[Cρ((1−ρ)−2t)−(1−ρ)−2Λf(t)],Wˆρ(t)≡(1−ρ)Wρ((1−ρ)−2t),t≥
0. 4.4.TheHTFWLLN.WestartwiththeHTFWLLN.LetDkbethekfoldproductspaceofDwithitself,let⇒denoteconvergenceindistributionandletx◦ybepositionfunctiondefinedby(x◦y)(t)≡x(y(t)). Theorem4.1.(HTFWLLN)Underthedefinitionsandassumptionsin§4above,ifξρ→ξandηρ→ηasρ↑1,andthesystemstartsemptyattime0,then (4.16) M¯ρ→MfinD,whereMf(t)≡t+ξS(t−η) and (4.17)(A¯ρ,Y¯ρ,X¯ρ,L¯ρ,C¯ρ,W¯ρ)⇒(A¯,Y¯,X¯,L¯,C¯,W¯)inD6asρ↑
1 for(A¯ρ,Y¯ρ,X¯ρ,L¯ρ,C¯ρ,W¯ρ)definedin(4.13),where A¯(t)≡Y¯(t)≡Λf(t),X¯(t)≡S(t)−ξS(t−η),t≥η, L¯(t)≡sup{X(t)−X(t−s)},t≥c+η,C¯≡Y¯−L¯,and 0≤s≤c (4.18) W¯(t)≡inf{u≥0:Mf(t+u)−Mf(t)≥L¯(t)},t≥
0. forΛf(t)in(4.12)withS(t)in(4.4),Mf(t)in(4.16)andψbeingthereflectionmap. Proof.Weessivelyapplythecontinuousmappingtheorem(CMT)usingthefunctionsin§12.7and§§13.2-13.6of[29].First,observethat(4.16)isaminormodificationof(4.10).LetN¯ρaandS¯ρdenoteN¯naandS¯nv,respectively,where,paralleling(4.1),weletN¯na(t)≡n−1Na(nt)andS¯nv≡n−1S⌊vnt⌋,t≥0,andthenletn=(1−ρ)−
2.ThenobservethatA¯ρ=N¯ρa◦Λ¯ρandY¯ρ=S¯ρ◦A¯ρ,sothatwecanapplytheCMTwithpositionmap.ThelimitforX¯ρfollowsfromtheCMTwithaddition PERIODICSINGLE-SERVERQUEUE 19 andthenthelimitforL¯ρfollowsfromtheCMTwiththereflectionmap.ToestablishthelimitforthescaledwaitingtimeW¯ρ(t)inDweapplytheCMTwiththeinversefunction.Finally,ThelimitforC¯ρagainfollowsfromtheCMTwithaddition. Weobtainstrongerresultsinspecialcases: Corollary4.1.(FWLLNfortherate-matchingserviceratecontrol)InadditiontotheconditionsofTheorem4.1,ifη=0andξ=1,thenMf(t)=Λf(t),t≥0,andthenX¯(t)=L¯(t)=W¯(t)=0forallt≥0,whileC¯=Y¯=A¯=Λf. Corollary4.2.(stabilizingthewaitingtimeatanypositivevalue)In additiontotheconditionsofTheorem4.1,ξ=1,sothatMf(t)=0,0≤t<η,andMf(t)=Λf(t−η),t≥η,forafixedtimelagη>0,then (4.19) t L¯(t)=X¯(t)≡X¯η(t)=Λf(t)−Λf(t−η)=λf(s)ds>0 t−η and (4.20) W¯(t)=ηforallt≥η. Corollary4.3.(sinusoidalwithdampedtimelag)InadditiontotheconditionsofTheorem4.1,supposethat (4.21) s(t)≡βsin(γt),t≥
0, forpositiveconstantsβandγwithβ<1,sothats(t)isperiodicwithperiodc≡cγ=2π/γ.Then (4.22) S(t)=(β/γ)(1−cos(γt)),t≥η, sothat L¯(t)=(β/γ)([ξcos(γ(t−η))−cos(γt)] +sup{cos(γ(t−s))−ξcos(γ(t−η−s))} 0≤s≤c =(β/γ)([ξcos(γ(t−η))−cos(γt)] (4.23) +sup{cos(γs)−ξcos(γ(s−η))}),t≥c+η. 0≤s≤c Forthespecialcaseξ=
1,W¯(t)=η.Ifinaddition,andη<π/γ,thesupremumin(4.23)isattainedats∗=(π/2γ)−η/2),sothat (4.24)L¯(t)=(β)([cos(γ(t−η))−cos(γt)]+[cos((π/2)−(γη/2))−cos((π/2)+(γη/2))]) γ 20
N.MAANDW.WHITT fort≥c+η.Asη↓
0, (4.25) L¯(t)/η→1+βsin(γt)=1+s(t). 4.5.TheHTFCLT.WenowstatetheFCLT,whichhasperiodicityinfluidscale,asin(1.11).Theproofappearsin§
6. Theorem4.2.(HTFCLT)Inadditiontothedefinitionsandassumptionsin§4above,includingthescaledarrival-ratefunctionin(1.11),assumethattheperiodicfunctions(t)in(1.3)iscontinuousand (4.26) (1−ρ)ηρ→η∗andξρ−1→ξ∗asρ↑1,1−ρ where0≤η∗<∞and0≤ξ∗<∞.Thenthereisalimitforthescaledcumulativeservice-ratefunctionsMρin(4.6)and(4.14);i.e., (4.27) Mˆρ(t)≡(1−ρ)[Mρ((1−ρ)−2t)−(1−ρ)−2(t+S(t))]→Mˆ(t)≡−s(t)η∗+S(t)ξ∗inDasρ↑
1 fors(t)in(1.3)andS(t)in(4.4).If,inaddition,thesystemstartsemptyattime0,then (4.28)(Aˆρ,Yˆρ,Xˆρ,Lˆρ,Wˆρ,Cˆρ)⇒(Aˆ,Yˆ,Xˆ,Lˆ,Wˆ,Cˆ)inD5asρ↑
1 for(Aˆρ,Yˆρ,Xˆρ,Lˆρ,Wˆρ,Cˆρ)definedin(4.15),where Aˆ(t)≡(caBa−e)◦Λf(t),Yˆ(t)≡(cxB−e)◦Λf(t),Xˆ(t)≡Yˆ(t)−Mˆ(t)=Yˆ(t)+s(t)η∗−S(t)ξ∗, =(cxB◦Λf)(t)−Λf(t)+s(t)η∗−S(t)ξ∗,(4.29)Lˆ(t)≡ψ(Xˆ)(t)andWˆ(t)≡Lˆ(t)/µf(t), Cˆ(t)≡Yˆ(t)−Lˆ(t),t≥
0. withcx≡c2a+c2s,BaBMandµf(t)≡λf(t)≡1+s(t),t≥0,thelimitingarrival-ratefunction. Wenowdrawattentiontosomeimportantconsequences.First,Theorem4.2establishesaHTtime-varying(TV)Little’slaw(LL),parallelingthemany-serverheavy-traffic(MSHT)TVLLin[27].Thisisatime-varyingversionofthefamiliarstate-spacecollapse,whichgoesbacktotheearlyHTpapers.Weremarkthattherelationisdifferentfromthetime-varyingLLdiscussedin[3,9]and[32]. PERIODICSINGLE-SERVERQUEUE 21 Corollary4.4.(HTtime-varyingLittle’slaw)UndertheconditionsofTheorem4.2,thelimitprocessesarerelatedby (4.30) Lˆ(t)=λf(t)Wˆ(t),t≥0,w.p.1. Corollary4.5.(thecaseofnovariability)Ifcx=0inadditiontotheconditionsofTheorem4.2,then (4.31) Xˆ(t)=−t+s(t)η∗−S(t)(ξ∗+1),t≥
0, sothatLˆ(t)=Wˆ(t)=0forallt≥0ifXˆ(t)≤0forallt≥
0. Theorem4.2reducesthequestionofasymptoticstabilityoftheprocessesLˆρ(t)andWˆρ(t),andtheexpectedvaluesofvariousfunctionals,suchasE[h(Lˆρ(t))]andE[h(Wˆρ(t))](assumingappropriateuniformintegrability)todiffusioncontrolproblemswiththeobjectivefunctionsin(1.8)and(1.9).Toexpressthestabilizationgoals,wealsoformulatetwodefinitionsofasymptoticstability,whichinvolvebothlargetimetandlargeρ. Evenfortalone,therearemanypossiblydefinitionsofasymptoticstabilityast→∞;e.g.,see[15].Forbothρandt,weomitissuesoflimitinterchangeast→∞andρ↑1,astreatedforexamplein[12],[11]and[5]inothercontexts.SinceourlimitprocessisaMarkovdiffusionprocess,weactuallyobtainastrongerconclusion,forwhichwegiveaseconddefinition. Definition4.1.(asymptoticstabilityforstochasticprocesses)Wesaythatascaledstochasticprocess{Zˆρ(t):t≥0}isasymptoticallystableasρ↑1(inHT)if (4.32)Zˆρ⇒ZˆinDasρ↑1,whereZˆ(t)⇒Zˆ(∞)ast→∞ foraproperrandomvariableZˆ(∞). Definition4.2.(asymptoticallystableandMarkov)Wesaythatascaledstochasticprocess{Zˆρ(t):t≥0}isasymptoticallystableandMarkovasρ↑1if (4.33) Zˆρ⇒ZˆinDasρ↑
1, where{Zˆ(t):t≥0}isaMarkovprocess,forwhichthereexistsaproperinitialdistributionZˆ(0)suchthatthelimitprocess{Zˆ(t):t≥0}isastationaryMarkovprocess. 22
N.MAANDW.WHITT Corollary4.6.(asymptoticallystableandMarkov)UndertheconditionsofTheorem4.2, (a)thescaledworkloadprocess{Lˆρ(t):t≥0}(respectively,waitingtimeprocess{Wˆρ(t):t≥0})isasymptoticallystableandMarkovasρ↑1ifandonlyifthereareasymptoticparametersη∗andξ∗andinitialdistributionsLˆ
(0)(respectively,Wˆ
(0))forthelimitingdiffusionprocessLˆ(respectively,Wˆ)suchthatthelimitprocessisstationary. (b)Ifη∗=ξ∗−1=0,aswiththerate-matchingservice-ratecontrolin[31],thenthescaledworkloadprocess{Lˆρ(t):t≥0}isasymptoticallystableandMarkov.Giventhatλf(t)isperiodicandnotconstant,thescaledwaiting-timeprocessisnotstable,byeitherDefinition4.1orDefinition4.2. (c)Thereexistasymptoticparametersη∗andξ∗satisfying(4.26)suchthatthescaledwaiting-timeprocess{Wˆρ(t):t≥0}isasymptoticallystableandMarkovifandonlyifthescaledworkloadprocess{Lˆρ(t)/λf(t):t≥0}isasymptoticallystableandMarkov. Proof.For(a),observethatthe-inputprocessXˆisXˆ=(cxB−e)◦Λf,whichisthedeterministictimetransformationΛfofordinaryBrownianmotionwithdrift,cxB−e.Thus,Lˆ=ψ(cxB−e)◦Λf)esastationaryprocessifweletLˆ(0)havetheexponentiallimitingdistributionoftheRBM,insteadofLˆ
(0)=0,asassumedforsimplicitytoplicationsinvolvingtheinitialconditions.TheremainingstatementsaredirectconsequencesofTheorem4.2. Wenowestablishconditionsfortheoptimalityofan(η∗,ξ∗)controlforthelimitingdiffusioncontrolproblemforeitherformulation(1.8)or(1.9).Ourproofwillexploituniformintegrability(UI);seep.31of[4]. Corollary4.7.(optimalityforthelimitingdiffusionprocess)ConsiderthespecialcaseoftheGIt/GIt/1modelwithE[Uk2+ǫ]<∞andE[Vk2+ǫ]<∞forsomeǫ>
0.If(ηρ∗,ξρ∗)→(η∗,ξ∗)asρ→1,where(ηρ∗,ηρ∗)istheoptimalcontrolforproblem(1.8)or(1.9),thenthelimitingcontrol(η∗,ξ∗)isoptimalforthecorrespondingdiffusioncontrolproblem. Proof.Welet(η˜,ξ˜)beanyalternativecontrolforthelimitingdiffusioonprocess.Thenlet(η˜ρ,ξ˜ρ)beanassociatedcontrolformodelρ,0<ρ<1,whereη˜ρ≡η˜/(1−ρ)andη˜ρ≡1+(1−ρ)ξ˜.Then,bythisconstruction,condition(4.26)holdsforthefamily(η˜ρ,ξ˜ρ).Wenextwanttoshowthattheconvergenceindistributioncanbeextendedtoconvergenceofthemeansfor PERIODICSINGLE-SERVERQUEUE 23 allt,whichrequiresuniformintegrabilityuniformlyint;seep.31of[4].We usetheboundsonthesecondmomentstoshowthatitholds. Towardthatend,weexploittheupperboundsfortheworkloadprocess intheGt/Gt/1modelintermsoftheassociatedworkloadprocessinthe stationaryG/G/1modelfrom§3of[21].Theseboundsextenddirectlyto theGt/Gt/1modelbyvirtueofCorollary2.1.Theseboundsshowthatthe meanworkloadisboundedaboveuniformlyinyovertheinterval[0,c].These boundsalsoapplytothewaitingtimeprocessbecauseW(t)≤L(t)/µ
L, whereµL>0isalowerboundontheservicerate,whichfollowsfrom (1.4)and(1.6).ForthestationaryGI/GI/1model,finitesecondmoments implytheexistenceofthefirstmomentsofthewaitingtimeanduniform integrabilityneededforconvergence;seep.31of[4]and§X.2andX.7of[1]. Finally, we observe that our optimal policy (ηρ∗ , ξ ∗ρ ) has expected value greaterthanorequaltothealternativepolicy(η˜ρ,ξ˜ρ)forallρ,whileboth convergeasρ→
1.Hence,thelimitoftheoptimalpolicies,(η∗,ξ∗)mustbe atleastasgoodas(η˜,ξ˜). WeapplyCorollary4.6tosupportournumericalcalculationsbyobserv- ing that (ηρ∗ , ξ ∗ρ ) when scaled as in (4.26) converges to a limit. We thus deducethatthelimitmustbetheoptimalpolicyforthediffusion.However, thisnumericalevidenceisnotamathematicalproof.Moreover,whilethe numericalevidenceisgood,itisnotexceptionallygood,especiallyforξρ∗as canbeseenfromTable1in§5below.
5.SimulationExamplesintheSettingof§
4.Inthissectionwereportresultsofsimulationexperimentstoevaluatethenew(ηρ,ξρ)controlsasafunctionofρformodelsscaledordingtoTheorem4.2,specificallyby(1.11),(4.3)and(4.6),sothatwecanseethesystematicbehavior. Table1showsresultsforfourvaluesofthetrafficintensityρwithρ↑1forthesinusoidalmodelin(1.2)-(1.6)withHTscalingin(1.11)withparameters(ρ,βρ,γρ)=(ρ,0.2,2.5(1−ρ)2).Forthiscase,wefoundthatthesolutionstooptimizationproblems(1.8)and(1.9)areidentical,towithinourstatisticalprecision.Hence,oursolutionsareforbothproblems. Table1showstheestimatedcontrolsηρandξρineachcase,plusscaledversionsconsistentwithcondition(4.26).Table1showsthattherelativeerrorisroughlyindependentofρ,beinglessthan1%ineachcase.Table1alsoshowsthatthelimitη∗≈1.45israpidlyapproachedby(1−ρ)ηρ/ρ,whilethelimitξ∗≈1.8isroughlyapproachedby(1−ρ)/ρηρ,bothofwhichareconsistentwithcondition(4.26).TheresultssupportTheorem4.2,butunfortunatelytherateofconvergenceinthecontrolparametersisnotfast.Evidentlythedampingcontrolξρismoreproblematic. 24
N.MAANDW.WHITT Table1 The(identical)solutionstotheminimaxandminimum-deviationoptimizationproblemsin(1.8)and(1.9)forthesinusoidalmodelin(1.2)-(1.6)withHTscalingin(1.11)withparameters(ρ,βρ,γρ)=(ρ,0.2,2.5(1−ρ)2).Thereportedmeanwaitingtimesarewithout spacescaling. ρβρ≡βγρηρ(1−ρ)ηρ/ρξρ(1−ξρ)/(1−ρ)maxE[Wy]min(max−min)averagewaitrelativeerror 0.80.20.15.801.450.8420.794.030.0324.020.8% 0.90.20.02512.941.440.8891.119.100.0919.071.0% 0.950.20.0062527.71.460.9311.3819.290.14319.210.7% 0.9750.20.001562556.61.450.9601.6039.610.36439.470.9% ForthemodelinTable1,Figure3showstheexpectedperiodicsteadystatevirtualwaitingtime(solidblueline),theexpectedsteady-stateworkload(thedashedredline)andarrivalratemultipliedbythemeanwaitingtime(thedottedgreenline)forρ=0.8(left)andρ=0.95(right).AsinFigure1,the95%confidenceintervalbandsareincluded,buttheycanonlybeseenbyzoomingin. Wealsoconsideredalternativevaluesoftherelativeamplitudeβ.Table2showsthesolutionstotheminimum-deviationoptimizationproblemin(1.9)forthesinusoidalmodelinTable1exceptβhasbeenincreasedtoβ=0.8from0.2.Table2showsthattherelativeerrorisroughlyindependentofρ,buttherelativeerrorhasincreasedtoabout10%fromabout1%ininTable1.UnlikeinFigure3,itisev
声明：
该资讯来自于互联网网友发布，如有侵犯您的权益请联系我们。
