Queueing Theory Part 2 - UW Courses Web Server
Queueing Theory(Part 2)M/M/1 Queueing SystemQueueing Theory-1
M/M/1 Queueing System Simplest queueing systemAssumptions:––– Interarrival times are iid, and exponentially distributed. The arrival process isPoisson.Service times are iid, and exponentially distributed.There is one serverThe interarrival times are exponentially distributed with parameter,! mean arrival rateThe service times are exponentially distributed with parameter,µ mean service rateThe utilization is " ! / µQueueing Theory-2
M/M/1 Queueing System and Rate Diagram The number of customers in the system, N(t), in an M/M/1queueing system satisfies the assumptions of a birth-death processwith–– !n ! for all n 0,1,2,!µn µ for all n 0,1,2,!We require ! µ , that is " 1 in order to have a steady state–Why?If ""1,!"Pnwon’t converge, and the queue will explode (up to #)n 0Rate Diagram!10µ!!2µ!3µ!!4µµQueueing Theory-3
M/M/1 Queueing SystemSteady-State ProbabilitiesCalculate Pn, n 0, 1, 2, !Rate In Rate OutState 0 : µP1 "P0#P1 State 1: "P0 µP2 ( " µ) P1Geometric Series# ""P0µ#n 0n 1if " 11% "( "21%"µP2 ' ( " µ) P0 "P0 * 2 P0µ&µµ! ) µ% " (n"" ! "State n : Pn P0 ' * P0 n P0µµ! µ& µ),Need - Pn 1n 0,,% " (n% " (n% 1 (nP P P P-'& µ *) 0 0 -'& µ *) 0 * 10'&1 )n 0n 0n 0,For M/M/1 with " 1P0 1# "Pn " n (1# ") for n 0,1,2, Queueing Theory-4!!
M/M/1 Queueing Systemd" n n" n#1d"L, Lq, W, WqCalculate L, Lq, W, Wq"1!""""1L expected number in system # nPn # n (1% ) (1% )# n nn 0n 0d (1" #)"2 "1(1" # ) ("1)d#n%1n 0d (1" #)1 2d#(1" #)& 1 )d( ""d nd !, /µ,' 1% * (1% )nL (1% )# (1% ) # (1% ) 2d n 0d (1% ) 1% 1% , / µ µ % ,n 0 d """"Lq expected number in queue # ( n %1) Pn # ( n %1) (1% ) # n (1% ) % # n (1% )nn 1n 1nn 1n 1 2,2Lq L % (1% P0 ) L % % 1% 1% µ(µ % ,)W L,1 , (µ % , ) , (µ % ,)Lq,2,Wq , µ(µ % ,) , µ(µ % ,)Queueing Theory-5!
M/M/1 Queueing SystemDistribution of Time in System! waiting time in systemExpected waiting time in system:1W E [! ] µ!"Probability that waiting time in system exceeds t :! µ 1!# tP (! t ) e ( ) for t " 0! q waiting time in queueExpected waiting time in queue:"Wq E # ! q %& µ (µ ! " )Probability that waiting time in queue exceeds t :! µ 1!# tP (! q t ) # P (! q t ) # e ( ) for t " 0Queueing Theory-6
M/M/1 Example: ER Emergency cases arrive independently at randomAssume arrivals follow a Poisson input process (exponentialinterarrival times) and that the time spent with the ER doctor isexponentially distributedAverage arrival rate 1 patient every hour! 2 patients / hour Average service time 20 minutes to treat each patientµ 1 patient / 20 minutes 3 patients / hour Utilization" %/µ 2/3 Does this M/M/1 queue reach steady state?Yes! " 1Queueing Theory-7
M/M/1 Example: ERQuestionsIn steady state, what is the!1. probability that the doctor is idle?2. probability that there are n patients?3. expected number of patients in the ER?4. expected number of patients waiting for the doctor?Queueing Theory-8
M/M/1 Example: ERIn steady state, what is the!Questions5. expected time in the ER?6. expected waiting time?7. probability that there are at least two patients waiting to see the doctor?8. probability that a patient waits to see the doctor more than 30 minutes?Queueing Theory-10
Car Wash Example Consider the following 3 car washesSuppose cars arrive according to a Poisson input process andservice follows an exponential distributionFill in the following table!µCar Wash A0.1car/min0.5car/minCar Wash B0.1car/min0.11car/minCar Wash C0.1car/min0.1car/min!LLqWWqP0What conclusions can you draw from your results?Queueing Theory-12
Car Wash Example Consider the following 3 car washesSuppose cars arrive according to a Poisson input process andservice follows an exponential distributionFill in the following table!µ!Car Wash A0.1car/min0.5car/min0.1/0.5 0.2Car Wash B0.1car/min0.11car/minCar Wash C0.1car/min0.1car/minLLqWWq(0.1)/(0.5-0.1) 0.25(0.1)2/(0.5)(0.4) 0.050.25/0.1 2.5 min0.5/0.1 0.5 min0.4/0.5 0.80.1/1.1 0.909(0.1)/(0.11-0.1) 10(0.1)2/(0.11)(0.1) 9.0910/0.1 100 min9.09/0.1 90.9 min0.01/11 0.090.1/0.1 10.1/(0.1-0.1) #Not steady state # # #What conclusions can you draw from your results?As & ! 1, then L, Lq, W, Wq ! # and P0 ! 0P00/0.1 0Queueing Theory-13
Car Wash Example M/M/1 with % 0.1 car/min& %/µL %/(µ-%) &/(1-&)L#!!" !"*!")!"(!"'!"&!"%!" !"Car wash BCar wash A#!"!"!,!!"!,#!"!, !"!,%!"!,&!"!,'!"!,(!"!,)!"!,*!"!, !"#,!!"&Rule of thumb: never exceed & 0.8, 80% utilizationQueueing Theory-14
Queueing Theory-12 Car Wash Example Consider the following 3 car washes Suppose cars arrive according to a Poisson input process and service follows an exponential distribution Fill in the following table What conclusions can you draw from your results? ! µ! L L q W W q P 0 Car Wash A 0.1 car/min 0.5 car/min Car Wash B 0.1 car/min
Purpose Simulation is often used in the analysis of queueing models. A simple but typical queueing model Waiting line Server Calling population Queueing models provide the analyst with a powerful tool for designing and evaluating the performance of queueing systems. Typical measures of system performance Server util
802.16 networks was conducted in [7], [8] by combining link-layer queueing with physical-layer transmission. A vacation queueing model was adopted in [9] to analyze the link-layer queueing performance of OFDM-TDMA systems with round-robin scheduling. A queueing model for OFDMA systems was used in [10] to design a scheduling scheme that balances
theory to construct the dynamic system of screening system in this paper. Queueing theory is the mathematical study of waiting lines [23]. In queueing theory, a model is constructed so that queue length
of Queueing Theory Applied to Emergency Care. Here is a picture of the participants at our meeting on October 25, 2012. Figure 1. Emergency Care/Queueing Seminar: (Left to Right) Jed Keesling, Trent Register, Joshua Hurwitz, Jean Larson, James Maissen, Hayriye Gulbu-dak, Evan Milliken,
the understanding of teletra c, queueing theory fundamentals and related queueing behavior of telecommunications networks and systems. These concepts and ideas form a strong base for the more mathematically inclined students who can follow up with the extensive literature on
probability, operational research, telecommunication, i ndustrial engineering, com-puter science, management science publish articles on queu eing extensively. The ow of new theories and methodologies in queueing has become very hard to keep . Queueing Theory and its Applications, A Personal View 13 distrib
have faded. But our lack of completeness is also explained by the time constraints of this survey. Queueing applications are abundant in Canada. The diverse areas where queueing analysis has been applied include: ship-ping and canals, grocery store checkout line count estimation, vehic
Components of a Queueing Model The calling population Finite or infinite (often approx. “very large”) Infinite pool: arrival rate not affected by the number of customers who have left the calling population and joined the queueing system. Finite pool: can affect arrival proce
