10m ago

161 Views

3 Downloads

1.42 MB

12 Pages

Transcription

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

Related Documents: