Statistics for Industry and Technology Series Editor N. Balakrishnan McMaster University Department of Mathematics and Statistics 1280 Main Street West Hamilton, Ontario L8S 4K1 Canada Editorial Advisory Board Max Engelhardt EG&G Idaho, Inc. Idaho Falls, ID 83415 Harry F. Martz Group A-1 MS F600 Los Alamos National Laboratory Los Alamos, NM 87545 Gary C. McDonald NAO Research & Development Center 30500 Mound Road Box 9055 Warren, MI 48090-9055 Kazuyuki Suzuki Communication & Systems Engineering Department University of Electro Communications 1-5-1 Chofugaoka Chofu-shi Tokyo 182 Japan U. Narayan Bhat An Introduction to Queueing Theory Modeling and Analysis in Applications Birkha¨user Boston • Basel • Berlin U.NarayanBhat ProfessorEmeritus StatisticalScience&OperationsResearch SouthernMethodistUniversity Dallas,TX75275-0332 USA ISBN:978-0-8176-4724-7 e-ISBN:978-0-8176-4725-4 DOI: 10.1007/978-0-8176-4725-4 LibraryofCongressControlNumber:2007941114 MathematicsSubjectClassification(2000):60J27,60K25,60K30,68M20,90B22,90B36 (cid:1)c2008Birkha¨userBoston Allrightsreserved.Thisworkmaynotbetranslatedorcopiedinwholeorinpartwithoutthewrit- tenpermissionofthepublisher(Birkha¨userBoston,c/oSpringerScience+BusinessMediaLLC,233 SpringStreet,NewYork,NY10013,USA),exceptforbriefexcerptsinconnectionwithreviewsor scholarlyanalysis.Useinconnectionwithanyformofinformationstorageandretrieval,electronic adaptation,computersoftware,orbysimilarordissimilarmethodologynowknownorhereafterde- velopedisforbidden. Theuseinthispublicationoftradenames,trademarks,servicemarksandsimilarterms,evenifthey arenotidentifiedassuch,isnottobetakenasanexpressionofopinionastowhetherornottheyare subjecttoproprietaryrights. Coverdesign:DuttonandSherman,Hamden,CT. Printedonacid-freepaper. 9 8 7 6 5 4 3 2 1 www.birkhauser.com Inmemoryofmyparents, VaidyaP.IshwarandParvatiBhat Contents Preface ......................................................... xi 1 Introduction................................................. 1 1.1 BasicSystemElements...................................... 1 1.2 ProblemsinaQueueingSystem .............................. 2 1.3 AHistoricalPerspective ..................................... 4 1.4 ModelingExercises......................................... 11 2 SystemElementModels ....................................... 13 2.1 ProbabilityDistributionsasModels ........................... 13 2.1.1 DeterministicDistribution(D) ......................... 14 2.1.2 Exponentialdistribution;Poissonprocess(M)............ 14 2.2 IdentificationofModels ..................................... 18 2.2.1 CollectionofData ................................... 18 2.2.2 TestsforStationarity ................................. 18 2.2.3 TestsforIndependence ............................... 19 2.2.4 DistributionSelection ................................ 19 2.3 ReviewExercises .......................................... 20 3 BasicConceptsinStochasticProcesses........................... 23 3.1 StochasticProcess.......................................... 23 3.2 Point,Regenerative,andRenewalProcesses .................... 23 3.3 MarkovProcess............................................ 24 4 SimpleMarkovianQueueingSystems ........................... 29 4.1 AGeneralBirth-and-DeathQueueingModel.................... 29 4.2 TheQueueM/M/1......................................... 34 4.2.1 DepartureProcess.................................... 40 4.3 TheQueueM/M/s......................................... 43 4.4 TheFiniteQueueM/M/s/K ................................ 51 4.5 TheInfinite-ServerQueueM/M/∞........................... 58 viii Contents 4.6 Finite-SourceQueues ....................................... 59 4.7 OtherModels.............................................. 62 4.7.1 TheM/M/1/1System ............................... 62 4.7.2 MarkovianQueueswithBalking ....................... 64 4.7.3 MarkovianQueueswithReneging ...................... 66 4.7.4 Phase-TypeMachineRepair ........................... 66 4.8 Remarks .................................................. 68 4.9 Exercises ................................................. 68 5 ImbeddedMarkovChainModels............................... 75 5.1 ImbeddedMarkovChains ................................... 75 5.2 TheQueueM/G/1......................................... 76 5.3 TheQueueG/M/1......................................... 98 5.4 Exercises ................................................. 112 6 ExtendedMarkovModels ..................................... 115 6.1 TheBulkQueueM(X)/M/1 ................................. 115 6.2 TheBulkQueueM/M(X)/1 ................................. 118 6.3 TheQueuesM/E /1andE /M/1............................ 120 k k 6.4 TheBulkQueuesM/GK/1andGK/M/1 ..................... 123 6.5 TheQueuesE /G/1andG/E /1 ............................ 126 k k 6.6 TheQueueM/D/s ......................................... 126 6.7 TheQueueM/M/1withPriorityDisciplines ................... 127 6.8 Exercises ................................................. 138 7 QueueingNetworks .......................................... 141 7.1 Introduction ............................................... 141 7.2 TheMarkovianNodeNetwork ............................... 142 7.3 QueuesinSeries ........................................... 144 7.4 QueueswithBlocking....................................... 147 7.5 OpenJacksonNetworks ..................................... 150 7.6 ClosedJacksonNetworks.................................... 152 7.7 CyclicQueues ............................................. 154 7.8 OperationalLawsforPerformanceAnalysis .................... 155 7.9 Remarks .................................................. 157 7.10 Exercises ................................................. 158 8 RenewalProcessModels ...................................... 161 8.1 RenewalProcess ........................................... 161 8.2 RenewalProcessModelsforQueueingSystems................. 166 9 TheGeneralQueueG/G/1andApproximations.................. 169 9.1 TheGeneralQueueG/G/1 .................................. 169 9.2 Little’sLawL=λW ....................................... 173 9.3 Approximations............................................ 175 9.4 DiffusionApproximation .................................... 178 Contents ix 9.5 FluidApproximation........................................ 180 9.6 Remarks .................................................. 183 10 StatisticalInferenceforQueueingModels ........................ 185 10.1 Introduction ............................................... 185 10.2 Birth-and-DeathProcessModels.............................. 187 10.3 ImbeddedMarkovChainModelsforM/G/1andG/M/1 ........ 191 10.4 TheQueueG/G/1 ......................................... 193 10.5 OtherMethodsofEstimation................................. 194 10.6 TestsofHypotheses......................................... 197 10.7 ControlofTrafficIntensityinM/G/1andG/M/1 .............. 197 10.8 Remarks .................................................. 199 11 DecisionProblemsinQueueingTheory .......................... 201 11.1 Introduction ............................................... 201 11.2 PerformanceMeasuresforDecisionMaking.................... 202 11.3 DesignProblemsinDecisionMaking.......................... 202 11.4 ControlProblemsinDecisionMaking ......................... 205 12 ModelingandAnalysisUsingComputationalTools ................ 207 12.1 MeanValueAnalysis........................................ 207 12.2 TheConvolutionAlgorithm.................................. 211 12.2.1 ComputingOtherPerformanceMeasures ................ 213 12.3 Simulation ................................................ 214 12.4 MATLAB................................................. 217 12.5 Exercises ................................................. 223 Appendices A PoissonProcess: PropertiesandRelatedDistributions ............. 229 A.1 PropertiesofthePoissonProcess ............................. 229 A.2 VariantsofthePoissonProcess ............................... 231 A.3 Hyperexponential(HE)Distribution........................... 233 A.4 ErlangDistribution(E )..................................... 234 k A.5 MixedErlangDistributions .................................. 234 A.6 CoxianDistributions;Phase-TypeDistribution .................. 235 A.7 AGeneralDistribution ...................................... 236 A.8 SomeDiscreteDistributions.................................. 236 B MarkovProcess.............................................. 239 B.1 KolmogorovEquations...................................... 239 B.2 ThePoissonProcess ........................................ 240 B.3 ClassificationofStates ...................................... 242 B.4 Phase-TypeDistributions .................................... 243 x Contents C ResultsfromMathematics..................................... 247 C.1 Riemann–StieltjesIntegral................................... 247 C.2 LaplaceTransforms......................................... 248 C.3 GeneratingFunctions ....................................... 250 References ...................................................... 253 Index........................................................... 265