On the conservation law and the performance space of single server systems

SingleServerSystems

LeonidasGeorgiadis

HighPerformanceComputingandCommunications

IBMT.J.WatsonResearchCenter,YorktownHeights,NY10598

IoannisViniotis1

DepartmentofElectricalandComputerEngineeringCenterforCommunicationsandSignalProcessingNorthCarolinaStateUniversity,Raleigh,NC27695

supportedbyIBM,whiletheauthorwasavisitingscientistattheIBMT.J.Watson

ResearchCenter.

1Work

Abstract

WeconsideramulticlassGI|G|1queueingsystem,operatingunderanarbitrarywork-conservingschedulingpolicyπ.WederiveaninvariancerelationfortheCesarosumsofwaitingtimesunderπ,whichdoesnotrequiretheexistenceoflimitsoftheCesarosums.Thisallowsustoincludeinthesetofadmissiblepoliciesimportantclasses,suchastime-dependentandadaptivepolicies.Fortheseclassesofpolicies,ergodicityisnotknownaprioriandmaynotevenexist.Therefore,theclassicalinvariancerelations,involvingstatisticalaveragesdonothold.ForanM|G|1system,wederiveinequalitiesinvolvingtheCesarosumsofwaitingtimes,thatfurthercharacterizetheachievableperformanceregionofthesystem.

1Introduction.

Conservationlaws(i.e.,invariancerelations,)regardingaveragewaitingtimesandaveragenumberofcustomersinthesystemhavebeenknownforalongtime.Mostoftheconservationlawspresentedsofar[13,12],dealwithsingleserver,workconservingsystems,ormultipleserver,stronglyworkconservingsystems[12,6].Roughlyspeaking,insuchsystems,nowork(servicetime)iscreatedordestroyedwithinthesystem(e.g.,customersdonotbalk,theservermaintainsalwaysthesamespeed,etc.)Forsuchsystems,underergodicityassumptions(thatis,undertheassumptionthatlimitsofsampleaveragesofwaitingtimesexistunderaschedulingpolicyπ,)onecanproveinvariancerelationsoftheform(seee.g.,[12],)

NXi=1

ρiWi(π)=F,(1)

whereNisthenumberofclasses,Wi(π)isthelimitofthesampleaveragewaitingtimeforcustomersofclassi,ρiistheutilizationofclassiandFisaconstant,independentoftheschedulingpolicy.Relativelylittlecanbesaidaboutmultipleserversystems[6].

Theequationin(1)constrainstheaveragewaitingtimesunderanergodicschedulingpolicytolieonanN-dimensionalplane.Anumberofinequalities[8]furtherconstrainthesetofachievableaveragewaitingtimes(i.e.,theperformanceregion)tobeaconvexpolygon.Theseinequalitiestaketypicallytheform

X

ρiWi(π)≥F(R),(2)

i∈R

whereR⊂{1,2,···,N}andF(R)isafunctionindependentofthepolicyπ.Forfurtherdetails,thereadermayconsult[8].

Inpractice,workcanbecreatedand/ordestroyed,withinthesystem,inaschedulingpolicy-dependentfashion.Forexample,whenpreemptivepriorityrulesareconsidered,interruptionofalowprioritycustomerintroducesanoverhead.Sincethisoverheaddependsonthepriorityruleinhand,aninvariancerelationisnolongerpossible.Policy-dependentoverheadisalsogeneratedinpollingsystems,whenevertheserverspendsanonzerotimetoswitchfromastation

1

toanother(nonzeroserverwalkingtime.)Forsuchnonwork-conservingsystems,anumberofpseudoconservationlawshaveappeared(seeforexample[2]).Suchlawsexpressarelationbetweenwaitingtimes,akintothatofeq(1),butwithpolicy-dependentrighthandsides.Ergodicityoftheschedulingpolicyusedisakeyassumptionforalltheabovestudies.Infact,manyauthors(anexceptionbeing[12,Theorem11-13])constrainfurthertheclassofwork-conservingpoliciestopoliciesthathaveregenerativestructure[4],[8],[6].However,foralarge(andratherimportantforapplications,)classofpolicies,namelyadaptive[1],andingeneral,policiesthatbasetheirdecisionsontheentirehistoryofthesystem,convenientregenerationpointsmaynotexist.Moreoveritmaynotbeaprioriclearthatlimitsofsampleaveragesexistundersuchpolicies.

Themotivationtostudyexistenceofinvariancerelationswithoutergodicityassumptionscamefromtheapplicationstudiedin[1].Briefly,theproblemconsideredin[1]isthefollowing:requestsbelongingtoNclassesarriveforserviceatasingleserverqueue.Witheachclass,thereisanassociatedresponsetimeobjectivegi.Thegoalistodetermineaschedulingpolicyπsuchthat

P∆¯k(π)=limsupk→∞kWm=1Wim(π)/k,whereWim(π)istheresponsetimeofthemthserved

¯k(π)isthecustomerfromclassi,iskeptbelowtheobjectivegi.Notethatforanergodicpolicy,W

limitofthesampleaverageofthewaitingtimesofcustomersfromclassi.Noaprioriknowledgeofsystemstatisticswasassumed.Thisrestrictionexcludedrandomizedpolicies[8]andleadtothedesignofanadaptivepolicy.Inaddition,inthisframework,thequestionarosewhetherbyusingnonergodicpoliciesonecanimprovetheperformanceofthesystem.Thisquestionraisestheissueofwhatequalities/inequalitiesthesampleaveragesofwaitingtimesundergeneralnonpreemptivework-conservingpoliciesmaysatisfy.Usingtheresultsofthecurrentpaper,itwasshownthat,withinthewholeclassof(bothergodicandnonergodic)nonpreemptive,work-conservingpolicies,thepolicyproposedin[1]achievedtheabovementionedgoal.

Thepaperisorganizedasfollows:inSection2wedefinetheGI|G|1modelforwhichtheconservationlawholdsandspecifytheclassofadmissiblepolicies.InSection3weproveaconservationlawfortheGI|G|1systemandprovideacounterexampletotheclaimthatlimits

2

ofsampleaveragesofwaitingtimesalwaysexistwhentheinterarrivaltimesareexponentiallydistributed.InSection4,wederiveinequalitiesthatimposefurtherconstraintsonthesampleaveragesofwaitingtimesfortheM|G|1system.

2Systemmodelandadmissiblepolicies

Inthesequel,weusethefollowingmodel.(Thismodelhasbeenusedin[15]aswell.)SystemModel:WeconsiderasingleserverqueuewithNclassesofcustomers.Thetimeintervalbetweenthekthandk+1starrivingcustomer(k≥1)isdenotedbyTk.Weassumethatthefirstarrivaloccursattimet=0.Witheacharrivalthereisanassociatedrandomvariable,Ck,whichdenotestheclasstowhichthearrivalbelongs;thatis,ifCk=i,i=1,···,N,thenthekthcustomerbelongstoclassi.Ifthektharrivingcustomerbelongstoclassi,itsservicetimeisarandomvariableSik.Therefore,Sk,theservicetimeofthektharrivingcustomerisgivenby

Sk=

NXi=1

I{Ck=i}Sik,

(3)

whereI{A}denotestheindicatorfunctionoftheeventA.Weassumethat{Tk,k≥1},{Ck,k≥1}and{Sik,k≥1},foreachi=1,···,N,areindependentsequences.Eachsequencecontainsi.i.d.randomvariables.Itfollowsfrom(3)that{Sk,k≥1}isasequenceofi.i.d.randomvariablesindependentof{Tk,k≥1}.Wedefinethetotalarrivalrateasλ=1/ET1andthearrivalrateofclassiasλi=P(C1=i)/ET1.Toavoidunnecessarycomplications,weassumethatλ>0,P(T1=0)=0,P(S1=0)=0andP(C1=i)>0,i=1,···,N.

FortheconservationlawofTheorem1inSection3,thedistributionof{Tk,k≥1}isarbitrary.However,fortheinequalityrelationsofTheorem2inSection4weneedtoassumethattherandomvariables{Tk,k≥1}areexponentiallydistributed.ThenthisisequivalenttotheassumptionthatthearrivalinstantsofeachclassconstituteaPoissonprocesswithrateλi=P(C1=i)/ET1,independentofthearrivalprocessesoftheotherclasses.

Wespecifynextthesetofadmissibleschedulingpolicies(i.e.,allpoliciesunderwhichthe

3

∆

∆

∆

systemmayoperate.)Thisistheclassofnonpreemptive,work-conservingpolicies.Weplacenoergodicityrestrictiononanadmissiblepolicy.Thus,anyadaptiveortime-dependentpolicyisamemberofthisclass.Arigorousdefinitionofthisclassisgivenin[9].Roughlyspeaking,awork-conservingpolicydoesnotidletheserverwhilecustomersarewaitinginthequeue,doesnotaffecttheamountofservicetimegiventoacustomerorthearrivaltimeofacustomerandisnonanticipative(thatis,theschedulingdecisionsdonotdependonfutureinterarrivaltimes,futureservicetimesortheservicetimesofcustomersthatarepresentinthesystematthetimewhenaschedulingdecisionismade.)Underanonpreemptivepolicy,acustomerinthequeuemaynotreplaceacustomerwhoisbeingservedbeforeitsservicerequirementsarecompleted.Underanonpreemptive,work-conservingpolicy,theservicetimesofthedepartingcustomersfromclassiarei.i.d.r.v.,identicallydistributedto{Sik,k≥1}.Moreover,theservicetimeofthekthdepartingcustomerfromclassiisindependentofitswaitingtime(timethecustomerwaswaitinginqueuebeforeitsservicestarted)andofthewaitingtimesofthecustomersfromclassithatwereservedbeforethekthcustomer.ThesepropertiesarecrucialfortheresultsinthenextsectionsandarestatedformallyinLemma1below.AlthoughtheassertionsofLemma1arefairlyintuitive,theproofrequiresamoreprecisedefinitionoftheclassofadmissiblepoliciesaswellassometechnicalargumentswhicharepresentedin[9].

¯ikitsserviceForthekthdepartingcustomerfromclassi,letWikdenoteitswaitingtimeandStime.Fori=1,2,···,N,andk≥2,let

Fi1=σ(Wi1)

∆

∆¯in,1≤n≤k−1),Fik=σ(Win,1≤n≤k;S

whereσ(X)denotestheσ-fieldgeneratedbythesetofrandomvariablesX.

Lemma1Underanynonpreemptive,work-conservingpolicythefollowingstatementsaretrue:¯ikisindependentofFik,foreveryk≥1.1.S

4

¯ik,k≥1}and{Sik,k≥1},areidentically2.Forafixedi,1≤i≤N,thesequences{Sdistributed.

Remark:NotethatthesecondstatementofLemma1isnottruefortheservicetimesof

¯kistheservicetimeofthekthdepartingthesuccessivedepartingcustomers.Inotherwords,ifS

customer(irrespectiveofitsclass,)itisnottrueingeneralthatunderanonpreemptivework-¯k,k≥1}isidenticallydistributedto{Sk,k≥1}.conservingpolicy,{S

3Theconservationlaw

ThekeytothemainresultofthissectionistheStrongLawofLargeNumbersforMartingaleswhichispresentedinLemma2.Itsproofcanbefoundin[11].AswillbeseenintheproofofTheorem1,thecorollarytothislemma,Corollary1,willallowustostatetheconservationlawwithouttheneedtoassumetheexistenceoflimitsofsampleaveragesofwaitingtimes.

Lemma2Let{Xk,k≥1}beasequenceofrandomvariablesand{Fk,k≥1}anincreasingsequenceofσ-fields,withXkmeasurablewithrespecttoFk,foreachk.LetZbearandomvariableandletcbeaconstantsuchthatE(|Z|·max{0,log|Z|})<∞andP(|Xk|>x)≤c·P(|Z|>x)foreachx≥0andk≥1.Then

k

1X

[Xm+1−E(Xm+1|Fm)]=0a.e.lim

k→∞km=1

ThenextcorollaryfollowseasilyfromLemma2.

Corollary1Let{Wk,k≥1},{Sk,k≥1}besequencesofrandomvariablesand{Fk,k≥1}beanincreasingfamilyofσ-fields.SupposethatWkisFk-measurableforallk≥1andthatSk−1isFk-measurableforallk≥2.SupposealsothatSkisindependentofFk,forallk≥1.LettherebearandomvariableZ,aconstantδ>1,andaconstantcsuchthatE|Z|δ<∞and

5

P(|WkSk|>x)≤cP(|Z|>x)foreachx≥0andk≥1.Then

k→∞

lim

ÃPk

m=1

WmSm

−

kPk

m=1

WmESmk!

=0a.e.(4)

Proof:LetX1=0,Xk=Wk−1Sk−1,

∆∆

k≥2.Clearly,XkisFk-measurableforallk≥

1.Also,sinceSkisindependentofFkandWkisFk-measurable,wehavethatfork≥1,

E(Xk+1|Fk)=E(WkSk|Fk)=WkESk.Sinceδ>1,theconditionE|Z|δ<∞impliesthatE(|Z|max{0,log|Z|})<∞.Equation(4)followsnowbyapplyingLemma2tothesequence

2

{Xk,k≥1}.

RecallthatWim(orWim(π),whendependenceonthepolicyneedstobeemphasized,)denotesthewaitingtimeofthemthdepartingcustomerfromclassiwhenpolicyπisusedand¯ikdenotestheservicetimeofthekthdepartingcustomerfromclassi.WeshalluseCorollaryS

¯ik.Toverifytheconditionsof1inTheorem1below,byreplacingWkwithWikandSkwithS

Corollary1inthiscase,weneedthelemmathatfollowsandsomeconditionsonthemomentsoftheservicetimes.Letsi

∆

(m)∆

=ESim1denotethemthmomentoftherandomvariableSi1.Let

si=ESi11anddefineρi,theutilizationofclassi,asρi=λisi.Lemma3Supposethat

PN

i=1ρi<1andthatforsomeconstantγ>2,si

(γ)

<∞,i=

1,···,N.Thenunderanynonpreemptive,work-conservingpolicy,thereexistsaconstantciandanonnegativerandomvariableZisuchthatEZihavethat

¯ik>x)≤ciP(Zi>x).P(Wik(π)S

TheproofofLemma3isgivenin[9].Themainideaistousethefactthatunderanywork-conservingpolicy,thewaitingtimeofacustomerisboundedbythelengthofthebusyperiodinwhichthecustomerarrived,aquantitywhichisindependentofthepolicy.Thedetailsoftheproofarebasedonrenewalargumentsandareomittedforthesakeofbrevity.

WearenowreadytostateandprovetheconservationlawfortheGI|G|1queueingsystem.Foranadmissibleschedulingpolicyπ,letV(π)(t)denotetheworkinsystem(i.e.,thesumof

6

γ/2

<∞,andforeachx≥0andk≥1,we

remainingservicetimesofallcustomersinthesystemattimet,)whenpolicyπisused.LetusalsodenotebyFIFOthepolicythatservescustomersinFirstInFirstOutorder.Itiswellknownthatforthispolicy

1ZT(FIFO)

V(t)dt=V∗=constanta.e.lim

T→∞T0

Theorem1Supposethat

PN

i=1ρi<1andthatforsomeconstantγ>2,si

(γ)

<∞,i=

1,...,N.Then,forallwork-conserving,nonpreemptivepolicies,wehavethat

k→∞

lim

NXi=1

ρi

ÃPk

m=1

Wim(π)

k

!

N1X(2)

=V−λisia.e.

2i=1

∗

Proof:Letπbeanadmissiblepolicy.Sincetheadmissiblepoliciesarenonidling,theworkinsystemattimetisindependentofthepolicy,[13],andtherefore,forallt≥0,

V

(π)

(FIFO)

NXi=1

(t)=

Vi(t),

(π)

(5)

whereVi(t)istheworkinsystemattimetduetocustomersfromclassionly.

LetKimdenotethenumberofclassicustomersservedduringthemthbusyperiodandKm=

thatEK1<∞,[5].UsingtheStrongLawofLargeNumbers,wehavethatlimk→∞Mik/k=P(C=i)EK1andlimk→∞Mk/k=EK1.Therefore,

MikMik/kλi

=lim=P(C1=i)=lim

k→∞Mkk→∞Mk/kλ

From[3,Theorem6]wehavethat

kN1Xλi(2)V∗1Xa

WkSk=−silim

k→∞kλ2λm=1i=1

PN

i=1Kim.LetalsoMik=

Pk

m=1KimandMk=

Pk

m=1Km.Since

PN

i=1

ρi<1,wehave

a.e.(6)

a.e.,(7)

a

whereWkdenotesthewaitingtimeofthektharrivingcustomer.Takingthelimitin(7)over

thesubsequenceMkandrearrangingterms,wehavethat

NMikX1X

¯im=Wim(π)Slim

k→∞Mk

i=1m=1

Mik

limk→∞

i=1Mk

N

V∗1Xλi(2)=−s

λ2i=1λi

NX

PMik

m=1

¯imWim(π)S

Mika.e.

(8)

7

In(8),thesumsum

PMik

m=1

Wim(π).ItisherewhereCorollary1isused.Towardsthisend,letusdefine,

rik=

∆

PMik

m=1

¯imappears,whilefortheconservationlawweneedonlytheWim(π)S

PMik

PMik

¯W(π)SWim(π)imimm=1

−sim=1.

MikMik

(9)

¯ikUsingLemma1andLemma3weseethat(forafixedi,)thesequencesWk=Wik(π),Sk=SandFk=FiksatisfyalltheconditionsofCorollary1.Sincelimk→∞Mik=∞a.e.,weconcludethat

k→∞

limrik=0a.e.(10)

From(8),(9)and(10)wehavethat

lim

NXi=1

k→∞

Ã

Mik

siMk

PMik

N

λi(2)MikV∗1Xm=1Wim(π)−si+rik=

MikMkλ2i=1λ

!

a.e.(11)

Toproceed,weneedtoreplacein(11)thesequenceMik/Mkwithitslimit,λi/λ,andthiscanbedoneifweshowthatforafixedi,thesequence{

almosteverywhere.LetBkdenotethelengthofthekthbusyperiod;{Bk,k≥1}isasequence

2

<∞,ofi.i.d.randomvariables,independentoftheschedulingpolicy.ObservethatsinceES1

22

<∞,EK1<∞,[10],andtherefore,fromSchwartz’sinequalitywehavewehavethatEB1

PMik

m=1

Wim(π)/Mik,k≥1}isbounded

that

221/2

·EB1)<∞.E[K1B1]≤(EK1

¯imdenotethebusyperiodduringwhichthemthcustomerfromclassideparts.SinceLetB

¯im,wehavethatWim(π)≤B

Wim(π)

}≤limsup{limsup{m=1

Mikk→∞k→∞

PMik

Pk

¯Bimm=1m=1BmKim

}=limsupPkMikk→∞m=1Kim

Pk

E[B1K1]m=1BmKm

≤limP=<∞a.e.kk→∞P(C=i)EKK1imm=1

PMik

(12)

Usingnow(6),(11),(10)and(12)wehavethat

lim

NXi=1

k→∞

λisi

PMik

m=1

N

Wim(π)1X(2)∗

=V−λisi

Mik2i=1

a.e.(13)

8

Itremainstoshowthat(13)holdsforallk(andnotjustforthesubsequencesMik).Thisisdonebyusingthestandardargumentsbywhichpartialrewardlimitsareestablishedfromtheknownlimitsofrenewalrewardprocesses,seee.g.[14,Section2.3].

2

WhenthearrivalprocessofeachclassisPoisson,itisstatedin[12,p.432]thatunderanynonpreemptive,work-conservingpolicythelimitsofthesampleaveragesofthewaitingtimesexist.Ifthisstatementwerecorrect,Theorem1wouldbeusefulonlywheninterarrivaltimesarenotPoisson.ItwashintedbyFedergruenandGroenvelt[7],however,thatthestatementmaynotbetrue.WepresentnextacounterexamplethatshowsthattheassumptionofPoissonarrivalprocessesdoesnotguaranteeergodicityoftheschedulingpolicies.Therefore,strongerconditionsonthesepoliciesmustbeimposedtoestablishergodicity.

Counterexample.ConsideranM/G/1queuewithtwoclassesofcustomers.Thetwoclassesarecharacterizedbytheirarrivalrates(denotedasλ1andλ2)andservicerates(denotedasµ1andµ2.)Assumethatthesystemisstable(i.e.,λ1/µ1+λ2/µ2<1),thesecondmomentsoftheservicerequirementsarefinite,andthatλ1/µ1>0,λ2/µ2>0.Defineatime-dependentpolicyπ,asfollows:

Atthebeginningofthenthbusyperiod(n≥1,)policyπgiveshighestpriorityto22k+1≤n≤22(k+1)−1,)πgiveshighestprioritytoclass2customers.

class1customers,if22k≤n≤22k+1−1,forsomek≥0.Otherwise,(i.e.,if

Weshallshowthatunderpolicyπ,limitsofsampleaveragesofwaitingtimesdonotexist.LetWmdenotethewaitingtimeofthemthservedcustomerfromclass1,m≥1.Definethefollowingsets:

H(n)={m:customermbelongstoclass1andisservedduringbusyperiodl,1≤l≤n,in

whichclass1hashighestpriority}

L(n)={m:customermbelongstoclass1andisservedduringbusyperiodl,1≤l≤n,in

whichclass1haslowestpriority}

9

∆∆

hl(resp.Mn)denotethecardinalityofthesetH(n)servedinthefirstnbusyperiods.LetMn

Ofcourse,H(n)∪L(n)={1,2,···,Mn},whereMndenotesthenumberofclass1customers

(resp.L(n).)Finally,leth(n),l(n)denotethenumberofbusyperiodsamongthefirstnbusyperiodsduringwhichclass1hashighestandlowestpriorityrespectively.Clearly,h(n)+l(n)=n.

¯n,thesampleaveragewaitingtimeofclass1customersduringthefirstnbusyperiods,Then,Wisgivenby

∆1¯n=W

Mn

nh(n)

Wm=

Mnnh(n)m=1

¯ndoesnotconverge.Considerfirstthesubsequence{nk=(22k−WeshallshownowthatW

Wm,m∈H(n),areidenticallydistributedtothecorrespondingrandomvariablesinaqueueingsystemthatgivesalwaysnonpreemptiveprioritytocustomersinclass1.Similarly,therandomvariablesWm,m∈L(n),areidenticallydistributedtothecorrespondingrandomvariablesinaqueueingsystemthatgivesalwaysnonpreemptiveprioritytocustomersinclass2.LetBk,Ik,k=1,2,···

denotethelengthofthekthbusyperiodandkthidleperiod

1),k≥1}.Observethath(nk)=1(22k−1)andl(nk)=2(22k−1).Therandomvariables33Mn

X

hMn

Pl

nl(n)Mnm∈H(n)Wm+hMnMnnl(n)Pm∈L(n)

lMn

Wm

.(14)

respectively.TherandomvariablesBk+Ik,k=1,2,···areindependent,identicallydistributed.Moreover,theirdistributiondoesnotdependontheschedulingpolicy,sincethepoliciesconsideredarenonidling.LetEB(EI)denotethemeanofBk(Ik.)Then,usingtheStrongLawofLargeNumbersweobtainasintheproofofTheorem1,thatMn/n→λ1(EB+EI).Similarly,

h

/h(n)→λ1(EB+EI)sincelimn→∞h(n)=∞andlimn→∞l(n)=∞,wehavethatMn

l

/l(n)→λ1(EB+EI).Therefore,takinglimitsalongthesubsequencenkin(14)weandMn

concludethat

¯n=1Wh+2Wla.e.,limWk

k→∞33

whereWh(resp.Wl)denotetheaveragewaitingtimeofclass1customers,underthepolicy

whichalwaysgivesstrictnonpreemptiveprioritytoclass1(resp.class2).Similarly,ifwel(¯nk)=(22k+1−2)/3.Therefore,from(14),

nk)=(2·22k+1−1)/3andconsiderthesubsequence{n¯k=22k+1−1,k≥0},wefindthath(¯

2h1l

¯nlimWa.e.¯k=W+Wk→∞3310

SinceWh¯k}.Thesystemdoesnotreachsteady-stateunderthisparticulartwosubsequences{nk},{n

2

4InequalityconstraintsforM/G/1Systems

Theorem1describesahyperplaneintheN-dimensionalspace,onwhichthelimitofalinearcombinationofthesampleaveragesofwaitingtimesmustlie.Clearly,notallpointsinthishyperplanecanbeobtainedbyemployingsomeworkconservingpolilcy.Theperformancespace(i.e.,thesubsetofpointsthatareachievablebysomeadmissibleschedulingpolicy,)iswellknownforergodicsystems.ForanM|G|1system,weareabletofurthercharacterizetheperformancespace.Asweshallsee,theconstantsF(R)thatappearintherighthandsideoftheinequalitiesinTheorem2arethesameastheonesthatappearwhenonlyergodicpoliciesareallowed.Fortherestofthissection,weassumethattheinterarrivaltimesareexponential.Asin[8,7],thebasicideaistodeterminealowerboundonthetimeaverageoftheworkinsystemduetocustomersthatbelongtoasubsetRoftheclasses.

Supposethatthesystemoperatesunderanonpreemptive,work-conservingpolicyπ.ForanysetR,R⊂{1,2,···,N},letVR(t)betheworkinsystemattimet,duetocustomersthatbelongtotheclassesinR,thatis,

∆(π)

VR(t)=(π)

i∈R

X

Vi(t).

(π)

(15)

Weareinterestedindevelopingalowerboundforthequantity

liminf

T→∞

RT

0

VR(t)dt

.T

(π)

(π)

(16)

In[7],itwasshownthatforallt≥0andforeachsamplepath,VR(t)isminimizedbyapolicywhichgivesnonpreemptiveprioritytoclassesinR.Moreover,sincetheorderofserviceofcustomersfromclassesinRcannotaffectVR(t),itissufficienttoassumethattheorderof

11

(π)

serviceofcustomersfromclassesinRisFIFO.ThequestionthatneedstoberesolvediswhethertheorderofserviceofcustomersfromRc,thecomplementofR,canaffectthetimeaveragein(16).Undertheassumptionthatsteadystateexists,itisshownin[8,7]thattheorderofserviceofcustomersinRcdoesnotaffectthetimeaveragein(16).Sincewedonotmakeanyassumptionsabouttheergodicityofthepolicies,however,weneedadifferentapproachhere.Assumethatawork-conservingpolicyπgivesnonpreemptiveprioritytoclassesinR.LetτimbethetimeinstantthemtharrivingcustomerfromaclassiinRcisscheduledforserviceandletτ¯imbethefirsttimeintheinterval[τim+Sim,∞)atwhichtherearenocustomersfromclasses¯imisinRinthesystem.Observethateitherτ¯im=τjlforsomel=1,2,···andj∈Rc,orτtheendofabusycycle.Also,letτkbethefirsttimewithinthekthbusyperiodthatacustomerfromaclassinRcisscheduledforservice.LetΓkdenotethetimeinstantwhenthekthbusyperiodbegins.AttimeT=Γk+1,theintegralin(16)canbewrittenasfollows:

ZΓk+1

0

(π)

VR(t)dt

kZΓm+1X

=

m=1Γm

(π)

VR(t)dt

=

m=1

kX

(π)¯m,U

(17)

R(π)(π)∆Γm+1¯m¯(π),k=1,2,···whereU=ΓmVR(t)dt.WemayrewriteUk

intheform

(18)

¯(π)Uk

where

(π)∆

Uim=

=

(π)Uk

+

i∈Rc

X

m=Mi(k−1)+1

MikX

Uim,

(π)

Zτ¯im

τim

(π)

VR(t)dt

and

(π)∆Uk=

Zτk

Γk

VR(t)dt.

(π)

(π)(π)¯k¯kwecanshowthatthedistributionofthesequenceU,k≥UsingthisdecompositionofU

1,cannotbeaffectedbyanonpreemptive,work-conservingpolicythatgivesprioritytoclassesinR.Thisisthecontentofthenextlemma.

Lemma4Foranynonpreemptive,work-conservingpolicyπthatgivesprioritytoclassesinthe

(π)¯k,k≥1}consistsofi.i.d.randomvariables,setRoverclassesinthesetRc,thesequence{U¯kidenticallydistributedtothesequence{U

(πf)

,k≥1}generatedbythepolicyπfthatgives12

nonpreemptiveprioritytoclassesinR,servescustomersfromclassinRinFIFOorderandcustomersfromclassesinRcinFIFOorder.

Proof:Recallthatπiswork-conserving,thearrivalprocessisPoisson(andindependentoftheservicerequirements,)andtheservicerequirementsareindependentrandomvariables.ObservethatthevalueofVR(t)fort∈[τim,τ¯im)dependsonlyonSimandtheservicetimesandthearrivalprocessofcustomersfromclassesinRinthattimeinterval.Itfollowsthattherandomvariables{Uim,i∈Rc,m≥1}areindependentandalsoindependentof{Uk,k≥1}.Moreover,thedistributionofUimisindependentofthepolicyπ.SinceπisnonidlingandgivesnonpreemptiveprioritytocustomersinR,{Uk,k≥1}isasequenceofi.i.d.randomvariablesandthedistributionof{Uk,k≥1}isindependentofthepolicy.Observealsothatthesummationin(18)includesthesamecustomers,independentofthepolicy.Thisobservationandthefactthat{Uk,k≥1}and{Uim,i∈Rc,m≥1}areindependentsequencesof

(π)¯k,k≥1}isasequenceofindependentrandomindependentrandomvariables,implythat{U(π)¯k,k≥1}isthesameforallwork-conservingpoliciesvariablesandthatthedistributionof{U

thatgivenonpreemptiveprioritytocustomersinR.Toconcludetheproof,observethatunderthepolicythatservescustomersinRcinFIFOorder,theprevioussequenceconsistsofi.i.d.randomvariables.

2

(π)

(π)

(π)

(π)

(π)

(π)

(π)

(π)

ThemainresultregardingtheperformancespacefortheM|G|1queueingsystemisgivenbythefollowingtheorem.

PN

(γ)

Theorem2Supposethatwehavethat

i=1

ρi<1,andforsomeconstantγ>2,wehavesi

i=1,...,N.Thenforanywork-conserving,nonpreemptivepolicyπ,andforallR⊂{1,···,N}

liminf

k→∞

≤∞,for

i∈R

whereF(R)isaconstant,independentoftheschedulingpolicy.Thelimitexistsandequalityisachieved,ifclassesinRhavenonpreemptivepriorityoverclassesinRc.

X

ρi

ÃPk

m=1

Wim(π)

k!

≥F(R)a.e.,(19)

13

Proof:UsingLemma4andassumingthatcustomersfromclassesinRcareservedaccordingtoaFIFOpolicy,weconcludeasin[8,Chapter6],thatunderanynonpreemptive,work-conservingpolicyπthatgivesprioritytoclassesinR,

lim

RΓk

0

k→∞

wherew0istheaverageresidualworkofthecustomerinservice.Standardargumentscanbeusednow,toshowthatwhenclassesinRhavenonpreemptivepriority,

lim

RT

0

XVR(t)dtw0∆¯

=+ρisi=F(R)a.e.,PΓk1−i∈Rρii∈R

(π)

(20)

T→∞

(π)

VR(t)dt¯(R)a.e.=F

T

(π)

(21)

SinceVR(t)isminimizedbyapolicythatgivesnonpreemptiveprioritytoclassesinR,weconcludethatunderanynonpreemptive,work-conservingpolicy,

liminf

T→∞

RT

0

VR(t)dt¯(R)a.e.≥FT

(π)

(22)

ThelimitexistsandequalityisachievedifclassesinRhavenonpreemptivepriorityoverclassesinRc.FollowingthemethodologyofTheorem1andusing(22)wehavethat

liminf

k→∞

i∈R

X

ρi

ÃPk

m=1

Wim(π)k

!

¯(R)−≥F

1(2)∆

λisi=F(R)a.e.2i∈R

2

X

5Conclusions.

WeconsideredaGI|G|1queueingsystemwithNpriorityclasses.Thesystemoperatesunderaschedulingpolicywhichmaybenonergodicorforwhichergodicitymaynotbeverifiableinadvance.Adaptiveandtime-dependentschedulingrulesrepresentanimportantclassofsuchpolicies.Wehavederivedaninvariancerelationthat“conserves”aweightedsumofappropriateCesarosumsofwaitingtimes.Wehavealsodemonstratedinequalitiesthatcharacterizefurthertheachievableperformanceregion,forthespecialcaseofPoissonarrivals.

14

Acknowledgements

Theauthorswishtothanktheanonymousreviewersfortheirhelpfulcomments,whichcon-siderablyimprovedthepresentationofthispaper.

References

[1]P.P.Bhattacharya,L.Georgiadis,P.Tsoucas,andI.Viniotis.Optimalityandfinite

timebehaviorofanadaptivemulti-objectiveschedulingalgorithm.TechnicalreportRC15967,IBMT.J.WatsonResearchCenter,1990.MathematicsofOperationsResearch,toappear.

[2]O.J.BoxmaandW.P.Groenendijk.Waitingtimesindiscrete-timecyclic-service

systems.IEEETransactionsonCommunications,36:1—170,1988.

[3]S.L.Brumelle.Ontherelationbetweencustomerandtimeaveragesinqueues.J.Appl.

Prob.,8:508—520,1971.

[4]E.G.CoffmanandI.Mitrani.Acharacterizationofwaitingtimeperformancerealizable

bysingleserverqueues.OperationsResearch,28:810—821,1980.

[5]J.W.Cohen.TheSingleServerQueue,volume8ofAppliedMathematicsandMechan-ics.North-Holland,Amsterdam,1969.

[6]A.FedergruenandH.Groenevelt.Characterizationandoptimizationofachievable

performanceingeneralqueueingsystems.OperationsResearch,36:733—741,1988.[7]A.FedergruenandH.Groenevelt.M/G/cqueueingsystemswithmultiplecustomer

classes:Characterizationandcontrolofachievableperformanceundernonpreemptivepriorityrules.ManagementScience,34(9):1121—1138,1988.

15

[8]E.GelenbeandI.Mitrani.AnalysisandSynthesisofComputerSystems.Academic

Press,NewYork,1980.

[9]L.GeorgiadisandI.Viniotis.Ontheconservationlawandtheperformancespaceof

singleserversystems.TechnicalreportRC15673,IBMT.J.WatsonResearchCenter,1990.OperationsResearch,toappear.

[10]S.GhahramaniandR.W.Wolff.Anewproofoffinitemomentconditionsforgi/g/1

busyperiods.QueueingSystems,4:171—178,19.

[11]P.HallandC.C.Heyde.MartingaleLimitTheoryanditsApplications.Academic

Press,NewYork,1980.

[12]D.P.HeymanandM.J.Sobel.StochasticModelsinOperationsResearch,volumeI.

McGraw-Hill,NewYork,1982.

[13]L.Kleinrock.QueueingSystems,volume2.JohnWiley,1976.

[14]R.W.Wolff.StochasticModelingandtheTheoryofQueues.IndustrialandSystems

Engineering.PrendiceHall,19.

[15]R.W.Wolff.Work-conservingpriorities.JournalofAppliedProbability,7:327—337,1970.

16