Queueing Theory Part 2 - UW Courses Web Server

6m ago
29 Views
2 Downloads
1.42 MB
12 Pages
Last View : 5d ago
Last Download : 1m ago
Upload by : Warren Adams
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:

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

theory in the 20th century, writes, . approach is to make the limit laws of probability theory the primitive assumptions and formulate. Author: Robust Queueing Theory . for the stochastic network calculus \in M/M/1 and M/D/1 queuing scenarios where exact results are available, the stoch

Queueing Theory. 1 Basic Queuing Relationships Little’s formulae are the most important equation in queuing theory Resident items Waiting items Residence time Single server Utilisation System Utilisation. 2

Queueing theory became a eld of applied probability and many of its results have been used in operations research, computer science, telecommunication, tra c engineering, reliability theory

The study of queueing theory requires some background in probability theory. Two modern introductory texts are [11] and [13], two really nice “classic” books are [7], [6]. 1.3 Basic Model and Notation A basic model of a service center is shown in

MA6453 – Probability and Queueing Theory Handled by : Dr. A. Elumalai (Prof) and Mr. K. Chinnasamy. A.P.(Sl.G) UNIT - I - RANDOM VARIABLES PART-A 1. A continuous RV X has PDF f(x) 3 x2, 0 x 1 , 0 otherwise. Find k such that P ( X k) 0.5 2. If X and

Queueing Theory-8 Terminology and Notation λ n Mean arrival rate (expected # arrivals per unit time) of new customers when n customers are in the system s Number of servers (parallel service channels) µ n Mean service rate for overall syste

Queueing Theory Raj Jain Washington University in Saint Louis Jain@eecs.berkeley.edu or Jain@wustl.edu A Mini-Course offered at UC Berkeley, Sept-Oct 2012 These slides and audio/video recordings are available on-line at: . Can find the

Queueing theory and Replacement model 1. Trucks at a single platform weigh-bridge arrive according to Poisson probability distribution. The time required to weigh the truck follows an exponential proba

Queueing Theory Notation Queuing characteristics –Arrival process –Service time distribution –Number of servers –System capacity –Population size –Service discipline Each of these is described mathematically .

in probability theory and relating operators on probability distributions to operators on sequences. Then in §3 we review the classical M/G/1 single-server queueing model and identify integer sequences a

Simulation and Queueing Theory Contents . Let us state again the main use of the most important probability distributions: Binomial distribution. This distribution models the number of successes in successive trials, where

Divis ADVANCED ENGINEERING MATHEMATICS 2130002 – 5th Edition Darshan Institute of Engineering and Technology Name : Roll No. : ion :