Stability and Instability of Fluid Models

StabilityandInstabilityofFluidModelsforRe-EntrantLinesJ.G.Dai1andG.Weiss2GeorgiaInstituteofTechnologyAbstractRe-entrantlinescanbeusedtomodelcomplexmanufacturingsystemssuchaswaferfabricationfacilities.Astherststeptotheoptimalornear-optimalschedulingofsuchlines,weinvestigatetheirstability.InlightofarecenttheoremofDai(1995)whichstatesthataschedulingpolicyisstableifthecorrespondinguidmodelisstable,westudythestabilityandinstabilityofuidmodels.TodothisweutilizepiecewiselinearLyapunovfunctions.WeestablishstabilityofFirst-Buer-First-Served(FBFS)andLast-Buer-First-Served(LBFS)disciplinesinallre-entrantlines,andofallwork-conservingdisciplinesinanythreebuerre-entrantlines.ForthefourbuernetworkofLuandKumarwecharacterizethestabilityregionoftheLuandKumarpolicy,andshowthatitisalsotheglobalstabilityregionforthisnetwork.WealsostudystabilityandinstabilityofKelly-typenetworks.Inparticular,weshowthatnotallwork-conservingpoliciesarestableforsuchnetworks;however,allwork-conservingpoliciesarestableinaringnetwork.RunningTitle:StabilityforuidmodelsAMS1991subjectclassication:Primary60K25,90B22;Secondary60K20,90B35.Keywordsandphrases:Stability,unstablenetworks,uidmodels,piecewiselinearLya-punovfunctions,re-entrantlines,multiclassqueueingnetworks,schedulingpolicies,Harrisrecurrence.February6,1994RevisedNovember,1994FinalversionJanuary19,1995MathematicsofOperationsResearch,Vol.21,115{135(1996)1ResearchsupportedbyNSFgrantsDMS-9203524andDDM-9215233,andtwograntsfromtheTexasIn-strumentsCorporation2ResearchsupportedbyNSFgrantsDDM-8914863andDDM-9215233,andthefundforthepromotionofresearchattheTechnion1IntroductionConsideramulticlassqueueingnetworkwithasinglerouteforallcustomers.ThereareIstations(nodes)inthenetwork.AllthecustomersfollowaxeddeterministicKstageroutethroughthenetwork.Weshallnumberthestagessothateachcustomerwillenterthesysteminstage1,andoncompletionofstagekwillmovetostagek+1,k=1;:::;K1,andleavethesystemoncompletionofstageK.Wedesignatethosecustomersonthekthstageoftheroute(thekthvisitalongtheroute)asclasskcustomers.Weenvisionclasskcustomerswaitinginbuerk,whichisassumedtohaveinnitecapacity(whencustomersareservedinFIFOrule,itisenoughtohaveonebuerforeachstation).Foreachklet(k)bethestationnumberthatclasskcustomersvisit(thestationservingstagek).Thismodeliscalledare-entrantline,seeKumar(1993).Adistinctivefeatureofare-entrantlineisthatcustomersmayvisitaparticularstationmorethanonce,sothateachnodeservesseveralclasses.Letf(n);n1gbeasequenceofpositiverandomvariables.Thenthrandomvariable(n)isinterpretedastheinterarrivaltimebetweenthe(n1)thcustomerarrivalandthenthcustomerarrivalfromoutside;therstcustomerarrivesattime(1).Theservicetimesatdierentstages(visits)forthenthcustomerare1(n),:::,K(n).Wemakethefollowingthreeassumptions.Firstweassumethatf((n);1(n);:::;K(n));n1gisaniidsequence.(1.1)Thenweassumethatalltherandomvariableshaveniterstmoments.Thatis,E[(1)]1andE[k(1)]1fork=1;:::;K:(1.2)Finally,weassumethattheinterarrivaltimesareunboundedandtheirdistributionisspreadout.Thatis,foranyx0,Probaf(1)xg0;(1.3)andforsomeintegern0andsomefunctionp(x)0onR+withR10p(x)dx0,Proba(anXi=1(i)b)Zbap(x)dx;forany0ab:(1.4)Notethatin(1.1),weallowtheservicetimesatdierentstagesofvisitstohavearbitraryde-pendency.Thisfeatureisusefulforcertainapplications,notablyincomputercommunicationsandmanufacturingsystems.Therethelengthofacomputermessageorthesizeofamanu-facturinglotmayberandom.However,theservicetimesingeneralareproportionaltothemessagelengthorlotsize,andthereforearepositivelycorrelated.Wealsoallowdependenceoftheservicetimesonthepreviousinterarrivaltime.LetCi=fk:(k)=ig.ThesetCiiscalledtheconstituencyofstationi.LetCbetheIKincidencematrix,Cik=(1if(k)=i0otherwise.(1.5)1Withoutlossofgenerality,weassumethatE[(1)]=1:(1.6)Letmk=E[k(1)]bethemeanservicetimeforclasskcustomers.Weassumethatthereisasinglereliableserverateachstation.Foreachi=1;:::;I,leti=Xk2Cimk:Wecallithenominalworkloadforserveriperunitoftime(recallthatthearrivalrateisnormalizedtobeonein(1.6)).Throughoutthispaper,weassumei1fori=1;:::;I.(1.7)Nothinghasbeensaidyetaboutaqueueingdiscipline,whichdictatestheorderinwhichcustomersareservedateachstation(wewillusequeueingdisciplineandschedulingpolicyinterchangeably).Specicqueueingdisciplineswillbediscussedinlatersections.Weassumethatalldisciplinesarework-conserving.Thatis,serveriworksatfullspeedwheneverthereisworktodoatstationi.InDai(1995),theauthorintroducedastochasticprocessfX(t);t0gthatdescribesthedynamicsofthequeueingnetworkunderaspecicqueueingdiscipline.Foreacht0,X(t)=(X1(t);:::;XI(t)),whereXi(t)isthestateatstationiattimet.Theexactdenitionofstatedependsontheparticularqueueingdiscipline.Forexample,ifrst-in-rst-out(FIFO)disciplineisusedateachstation,thenoneneedstotakeXi(t)=(xi1(t);:::;xini(t)(t));u(t);vxi1(t)(t);whereni(t)isthequeuelength(includingthepossibleonebeingserved)atstationi,xij(t)istheclassnumberofthejthcustomeratthestation,u(t)istheresidualtimeforthenextexternalcustomertoarrive,vxi1(t)(t)istheresidu