Queueing Theory - University Of Washington

Queueing TheoryChapter 17Queueing Theory-1

Why Study Queueing Theory Queues (waiting lines) are a part of everyday life.– Buying a movie ticket, airport security, grocery check out, mail apackage, get a cup of coffee etc.– It is estimated that Americans wait 37,000,000,000 hours peryear waiting in queues!!!More generally, great inefficiencies occur because of other types of“waiting”– Machines waiting to be repaired leads to loss of production– Vehicles waiting to load or unload delays subsequent shipments– Airplanes waiting to take off or land– Delays in telecommunication transmissio.Queueing theory uses queueing models to represent various typesof systems that involve “waiting in lines”. The models investigatehow the system will perform under a variety of conditions.Decision Analysis-2

Basic Queueing ProcessJ ArrivalsQueueService Arrival timedistribution Calling population(infinite or finite) Capacity(infinite or finite) Queueingdiscipline Number of servers(one or more) Service timedistribution“Queueing System”Queueing Theory-3

Examples and Applications Call centers (“help” desks, ordering goods)ManufacturingBanksTelecommunication networksInternet serviceTransportationHospitalsRestaurantsOther examples .Queueing Theory-4

Labeling Convention rvicetimedistributionMarkovian (exponentialinterarrival times,Poisson number ofarrivals)DeterministicErlang with shapeparameter kGeneral/Number ofservers/QueueingdisciplineFCFS first come,first servedLCFS last come,first servedSIRO service inrandom orderGDgeneraldisciplinePriority queuesRound robin/SystemcapacityFiniteCapacity KInfiniteCapacity CallingpopulationsizeFinitePopulation NInfinitePopulation Queueing Theory-5

Labeling Convention (Kendall-Lee)Examples:M/M/1M/M/1/FCFS/ / M/M/sM/M/s/FCFS/ / M/G/1M/M/s//10M/M/s/FCFS/K 10/ M/M/1///100M/M/1/FCFS/ /N 100Ek/G/2//10Erlang(k)/General/s 2/FCFS/K 10/ Queueing Theory-6

Terminology and Notation State of the systemNumber of customers in the queueing system (includes customers inservice)Queue lengthNumber of customers waiting for service State of the system - number of customers being servedN(t) Pn(t) State of the system at time t, t 0Probability that exactly n customers are in the queueingsystem at time tL Expected number of customers in the systemLq Expected number of customers in the queueQueueing Theory-7

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 system(expected # customers completing service per unit time)when n customers are in the systemNote:µn represents the combined rate at which all busy servers(those serving customers) achieve service completion.Queueing Theory-8

Terminology and Notationλ010µ1 λ2λ12µ2 µ3State is number of customers in the system, may be infiniteTransitions can happen at any time, so instead of transitionprobabilities, as with Markov chains, we have transition ratesQueueing analysis is based on a special case of continuous timeMarkov chains called birth-death processesQueueing Theory-9

Exampleλ010µ1 λ2λ12µ2 µ3Arrival rate depends on the number n of customers in the systemλ0: 6 customers/hourλ1: 5 customers/hourλ2: 4 customers/hourService rate is the same for all nµ1: 2 customers/hourµ2: 2 customers/hourµ3: 2 customers/hourQueueing Theory-10

Terminology and NotationWhen arrival and service rates are constant for all n,λ mean arrival rate(expected # arrivals per unit time)µ mean service rate for a busy server1/λ expected interarrival time1/µ expected service timeρ λ/sµ utilization factor for the service facility expected fraction of time the system’s service capacity (sµ)is being utilized by arriving customers (λ)Queueing Theory-11

ExampleCustomerarrives Customer Customerarrives arrivesCustomerarrivesA customer arrives every 10 minutes, on average- What is the arrival rate per minute?λ 1 customer / 10 minutes 0.10 customers/minuteor 6 customers/hour- Interarrival time between customers is 1/λThe service time takes 30 minutes on average- What is the service rate per minute?µ 1 customer / 30 minutes 0.0333 customers/minuteor 2 customers/hourQueueing Theory-12- Service time is 1/µ

Terminology and NotationSteady StateWhen the system is in steady state, thenPn probability that exactly n customers are in the queueing systemL expected number of customers in queueing system" ! nPnn 0λ010µ1λ2λ12µ2 µ3Lq "expected queue length (excludes customers being served) ! (n # s ) Pnn sQueueing Theory-13

Example: Utilization Suppose λ 6 customers/hour and µ 2 customers/hourUtilization is ρ λ/(sµ)If one server, s 1, ρ λ/µ 6/2 3,utilization 1, so steady state will never be reached, queue lengthwill increase to infinity in the long run If three servers, s 3, ρ λ/(3µ) 1utilization 1, queue is unstable and may never reach steady state If four servers, s 4, ρ λ/(4µ) 3/4utilization 1, the queue will reach steady state and L is finiteQueueing Theory-14

Terminology and NotationSteady StateWhen the system is in steady state, thenω waiting time in system (includes service time)for each individual customerW E[ω] expected time in systemωq waiting time in queue (excludes service time)for each individual customerWq E[ωq] expected time in queueQueueing Theory-15

Little’s FormulaDemonstrates the relationships between L, W, Lq, and Wq Assume λn λ and µn µIntuitive Explanation:(arrival and service rates1.* C C C C Servermeconstant for all n) In a steady-state queue,Expected number in system (Arrival rate) x (Expected time in system)L "WLq "W qExpected time in system (Expected time in queue) (Expected time in service)!1W Wq µI have just arrived, and because thesystem is in steady state, I expect towait W until I leave2.C C C C Server *meAs I leave, the number of customers inthe system is the number that arrivedwhile I was in the system. Because thesystem is in steady state, I expect thisnumber to be L.But, if I expect to wait W, and theaverage arrival rate is λ, then I expectto see λW arrivals while I am in theQueueing Theory-16system, so L λW !

Little’s Formula (continued) This relationship also holds true for !λ (expected arrival rate)when λn are not equal.L "Wλ0Lq " W q#where " "n Pnn 010µ1λ2λ12µ2 µ3!Recall, Pn is the steady state probability of having n customers in the systemQueueing Theory-17

Heading toward M/M/s The most widely studied queueing models are of the formM/M/s (s 1,2, )What kind of arrival and service distributions does this modelassume?Reviewing the exponential distribution .A picture of the probability density function for T exponential(! ) :fT(t)#1 &Area P%T ( 0.393 2" '# 11&Area P% T ( 0.239 2""'#1&Area P%T ( 0.368 "'α!!e!12!1! !tQueueing Theory-18

Exponential Distribution ReviewedIf T exponential(α), then& %t#%efT (t ) "! 0αt 0t 0!e12!tFT (t) P(T " t) % #e #uP(T t) 1 (1 eE[T] ) e1!du 1 e #tu 0 #tfT(t) #tFT(t)11-e-11!!Var(T) 1 2!1!Queueing Theory-19

Property 1Strictly DecreasingThe pdf of exponential, fT(t), is a strictly decreasing functionP(0 " T " !t ) P(t " T " t !t ) A picture of the pdf:fT(t)#1 &Area P%T ( 0.393 2" '# 11&Area P% T ( 0.239 2""'#1&Area P%T ( 0.368 "'α!!e!12!1! !tQueueing Theory-20

Property 2MemorylessThe exponential distribution has lack of memoryi.e. P(T t s T s) P(T t)for all s, t 0Example:P(T 15 min T 5 min) P(T 10 min)For interarrival times, this means the time of the next arriving customer is independent ofthe time of the last arrival i.e. arrival process has no memoryThis assumption is reasonable if1. there are many potential customers2. each customer acts independently of the others3. each customer selects the time of arrival randomlyEx: phone calls, emergency visits in hospital, cars (sort of)The probability distribution has no memory of what has already occurredFor service times, most of the service times are short, but occasional long service timesQueueing Theory-21

Property 2Memoryless Prove the memoryless property for the exponential distributionP (T t s T s) P (T t s and T s) P (T t s) P (T s)P (T s)e"# ( t s) e"# ( t )e"# ( s)"# ( t ) "# ( s) e P (T t )"# ( s)eet0! st sOnly exponential and geometric distributions are memorylessIs this assumption reasonable?– For interarrival times– For service timesQueueing Theory-22

Property 3Minimum of ExponentialsThe minimum of several independent exponential randomvariables has an exponential distributionIf T1, T2, , Tn are independent r.v.s, Ti expon(αi) andU min(T1, T2, , Tn),nU expon( " #"i)i 1Example:If there are s servers, each with exponential service times with mean µ,then U time until next service completion exponential(sµ)!XXXXX1µ2µsµ!Queueing Theory-23

Property 4Poisson and ExponentialSuppose the time T between events is exponential (α), let N(t) be thenumber of events occurring by time t. Then N(t) Poisson(αt)n"t ) e#"t(P(N (t) n) , n 0,1,2, n!0"t ) e#"t(P ( N ( t ) 0) e#"t0!1 #"t"te()P ( N ( t ) 1) "te#"t1!2"t ) e#"t(P ( N ( t ) 2) 20tNote:E[N(t)] αt, thus the expected number of events per unit time is α!Queueing Theory-24

Property 5ProportionalityFor all positive values of t, and for small Δt,P(T t Δt T t) αΔti.e. the probability of an event in interval Δt is proportional (with factorα) to the length of that intervalαΔttt ΔtQueueing Theory-25

Property 6Aggregation and DisaggregationThe process is unaffected by aggregation and disaggregationAggregationDisaggregationN1 Poisson(λ1)N1 Poisson(λp1)N2 Poisson(λ2)N Poisson(λ) λ λ1 λ2 λkNk Poisson(λk)Ex: different types of customers arearriving into 1 queueCall center – customers from differentcities, different questionsCar repairs – different types of cars,different types of problemsN Poisson(λ)p1p2pkN2 Poisson(λp2) Nk Poisson(λpk)Note: p1 p2 pk 1Disaggregate to other queues or serverspi probability of type i (fraction of type i)Ex: Manufacturing – good, defectiveQueueing Theory-26scrap, rework

Back to Queueing Remember that N(t), t 0, describes the state of the system:The number of customers in the queueing system at time t We wish to analyze the distribution of N(t) in steady state Find the steady state probability Pn of having n customers in thesystem with rates λ0, λ1, λ2 and µ1, µ2, µ3 λ010µ1λ2λ12µ2 µ3Queueing Theory-27

Birth-and-Death Processes If the queueing system is M/M/ / / / , N(t) is a birth-and-deathprocessA birth-and-death process either increases by 1 (birth), ordecreases by 1 (death)General assumptions of birth-and-death processes:1. Given N(t) n, the probability distribution of the time remaining until thenext birth is exponential with parameter λn2. Given N(t) n, the probability distribution of the time remaining until thenext death is exponential with parameter µn3. Only one birth or death can occur at a timeQueueing Theory-28

Rate Diagrams Rate diagrams indicate the states in a birth-and-death processand the arrows indicate the mean rates at which transitions occurλ010µ1λ2λ12µ2µ3λn-2λn-3 n-1n-2µn-2µn-1λnλn-1nµnλn 1n 1µn 1 µn 2Queueing Theory-29

Steady-State Balance Equations Assume the system achieves steady state(it will when utilization is strictly less than 1) Rate In Rate OutPn probability of n customers in systemλ010µ1λ2λ12µ2µ3λnλn-1 nµnµn 1Queueing Theory-30

Steady-State Balance EquationsPn probability of n customers in systemλ010µ1λ2λ12µ2State 0 : µ1P1 "0 P0λn-1 State n : "n -1Pn 1 µn 1Pn 1 ( "n µn ) PnNeed " Pn 1Define C0 1nµn 1!n#1 ! !0µ n !µ1Pn Cn P0Cn !"# P1 0 P0µ1#!n 0µnµ3State 1: "0 P0 µ2 P2 ( "1 µ1 ) P1!λn!"C P P "Cn 00n 0P2 "1"0P0µ2µ1" " ! "0# Pn 1 n n 1P0µn 1µn ! µ1P0 n 1n 01!"Cnn 0Queueing Theory-31

Recall Useful FactsGeometric series"1infinite sum : if x 1, # x 1 xn 0nNfinite sum :N 11 xfor any x % 1, # x 1 xn 0nQueueing Theory-32