On the Optimal Policy for Deterministic and Expone

TI2005-066/4TinbergenInstituteDiscussionPaperOntheOptimalPolicyforDeterministicandExponentialPollingSystemsBrunoGaujal1ArieHordijk2DinardvanderLaan31INRIARhône-Alpes,MontbonnotSaintMartin,France,2DeptofMathematics,LeidenUniversity,Leiden,3DeptofEconometrics&OperationsResearch,VrijeUniversiteitAmsterdam,andTinbergenInstitute.TinbergenInstituteTheTinbergenInstituteistheinstituteforeconomicresearchoftheErasmusUniversiteitRotterdam,UniversiteitvanAmsterdam,andVrijeUniversiteitAmsterdam.TinbergenInstituteAmsterdamRoetersstraat311018WBAmsterdamTheNetherlandsTel.:[phone]Fax:[phone]TinbergenInstituteRotterdamBurg.Oudlaan503062PARotterdamTheNetherlandsTel.:[phone]Fax:[phone]Pleasesendquestionsand/[e-mail]nbedownloadedat∗BrunoGaujal†ArieHordijk‡DinardvanderLaan§April26,2005AbstractInthispaper,weconsiderdeterministic(bothfluidanddiscrete)pollingsystemswithNqueueswithinfinitebuffersandweshowhowtocomputethebestpollingsequence(minimizingtheaveragetotalworkload).Withtwoqueues,thebestpollingsequenceisalwaysperiodicwhenthesystemisstableandformsaregularsequence.Thefractionoftimespentbytheserverinthefirstqueueishighlynoncontinuousintheparametersofthesystem(arrivalrateandservicerate)andshowsafractalbehavior.ConvexitypropertiesareshowninAppendixaswellasageneralizationofthecomputationstothestochasticexponentialcase.KeywordsPollingsystems,regularsequences,multimodularity,optimalcontrol.1IntroductionInthispaperweconsiderapollingsystemwithNqueueswithinfinitebuffers.Timeisslottedandthetime-slotsizesareeitherdeterministicwithunitsizeorexponentialdistributedwithmeanone.Ineachqueueonecustomerarrivesineachtime-slot,weassumethatitsrequiredservicetimeisqueuedependent,itisafixedamountinthedeterministicpollingmodelanditisexponentiallydistributedintheexponentialmodel.Forthedeterministicmodelwealsoconsiderthemodelwithfluidinput.Thereisoneserver,andatthebeginningofeachtime-slotthedecisionhastobemadewhichqueueisbeingservedduringthenexttime-slot,weassumezeroswitchingtimesasisusualintheperformanceanalysisofcommunicationnetworks.Theservice-disciplineisfirst-in-first-outforeachqueueanditiswork-conservative.Thecontroloftheserverisanopen-loopcontrol,whichmeansthatthedecision,whichqueuetobeservedinthenexttime-slotisindependentoftheactualworkloadsinthenodes.Theopen-looppollingsequenceisaninfinitesequencewhereitsn−thelementgivesthequeuewhichisservedduringthen−thtime-slot.Wederiveanefficientalgorithmforcomputingtheoptimalopen-looppollingsequencewithobjectivethesumoftheaverageworkloadsinthequeues,forthedeterministicandfortheexponentialpollingmodelwithN=2queues.Weexploitthetheoryonmultimodularityoftheaverageworkloadandtheoptimalityofregularsequencesasithasbeenderivedinrecentpapers(see[1]and[2]).ItfollowsfromthistheorythatforN=2queuestheoptimalpollingpolicyassignstime-slotstothefirstqueue(servicesequenceofthefirstqueueaswewillcallit)asa∗ThisworkwaspartiallysupportedbytheVanGoghgrantondiscreteeventsystems†Lab.ID-IMAG,(INRIA,CNRS,INPG,UJF)51avenueJeanKuntzmann,38330MontbonnotSaintMartin,France.E-mail:[e-mail]:([phone]‡DepartmentofMathematics,LeidenUniversity,NielsBohrweg1,P.O.Box9512,2300RALeiden,TheNetherlands.E-mail:[e-mail]:([phone]§FacultyofEconomicsandBusinessAdministration,DepartmentofEconometrics,VrijeUniversiteit,DeBoelelaan1105,1081HVAmsterdam,TheNetherlands.E-mail:[e-mail]:([phone]regularsequence,saywithdensityˆd1(andalsotheservicesequenceforthesecondqueueisalsoregularwithdensityˆd2=1−ˆd1).AsweshowinAppendixA,thesum(ingeneralofanylinearcombination)oftheaverageworkloadsinbothqueuessayB(d1,d2)isaconvexfunctionofthedensities(d1,d2)iftheservicesequencesareregularforbothqueues.Ouralgorithmscomputethisconvexfunctionforthedeterministicandfortheexponentialmodel,anditfindstheoptimaldensities(ˆd1,ˆd2)forbothmodels.Inthesections2to4weanalyzethetwodeterministicmodelswithdiscreteandfluidinput.Forfixeddensities(d1,d2)theaverageworkloadsinbothqueuesbecomeindependentofeachotherandtheaverageworkloadscanbestudiedseparately.InSection3theaverageworkloadforonequeuewithregularservicesequenceasfunctionofitsdensityisanalyzed,itisshownthatitisaconvexpiecewise-linearfunction.Usingresultsfromnumbertheorywederiveexplicitformulaefortheaverageworkloadincasetheservicedensityisabestapproximationpointoftheinputrate.Withtheuseofthecontinuedfractionexpansionoftheinputratewethenderiveanefficientalgorithmforcalculatingtheaverageworkloadforanydensity.Doingthesecalculationsforbothqueuesgivesanefficientalgorithmforcalculatingmind1+d2=1B(d1,d2),whichprovidestheexactoptimalpollingpolicy.Insection4weillustratethealgorithmwithnumericalexperiments.Alsoinsection4wederiveresultsonthestructureoftheoptimalpolicy.WeprovethatfordeterministicpollingsystemswithN≥2queuesandrationalinputratesthereisalwaysanperiodicoptimalpolicy.InAppendixB,thealgorithmforcalculatingtheopti