《土木与环境工程》（英文版）Queuing Systems: Lecture 3

Queuing Systems: Lecture 3 Amedeo odoni October 17. 2001

Queuing Systems: Lecture 3 Amedeo R. Odoni October 17, 2001

Lecture outline M/M/1: finite system capacity, K M/MIm: finite system capacity, K M/M/m: finite system capacity, Kem Related observations and extensions M/E,/l example M/G/: epochs and transition probabilities M/G1: derivation of l Why M/G/m, G/G/1, etc are difficult

Lecture Outline • M/M/1: finite system capacity, K • M/M/m: finite system capacity, K • M/M/m: finite system capacity, K=m • Related observations and extensions • M/E2 /1 example • M/G/1: epochs and transition probabilities • M/G/1: derivation of L • Why M/G/m, G/G/1, etc. are difficult

M/M/1: finite system capacity, K customers finding system full are lost p"·(1-p) K+1 forn=0,1,2,…,k Steady state is always reached Be careful in applying Little's Law! Must count only the customers who actually join the system =:(1-Pk)

M/M/1: finite system capacity, K; customers finding system full are lost … 0 1 2 K-1 K l l l l l m m m m m P for n K K n n 0, 1, 2, ....., 1 (1 ) 1 = - × - = + r r r • Steady state is always reached • Be careful in applying Little’s Law! Must count only the customers who actually join the system: l¢ = l ×(1- PK )

M/M/m: finite system capacity, K; customers finding system full are lost m 2 Can write system balance equations and obtain closed form expressions for Pn, L, W, Lg, Wg Often useful in practice

M/M/m: finite system capacity, K; customers finding system full are lost 0 1 2 m m+1 K-1 l l l l l l 3m m 2m mm mm mm K l mm mm l …… …… • Can write system balance equations and obtain closed form expressions for Pn , L, W, Lq , Wq • Often useful in practice

M/M/m: finite system capacity, m special case 3 m 2u forn=0,1,2,,m ∑ Probability of full system, Pm, is"Erlang's loss formula Exactly same expression for Pn of M/G/m system with Kem

M/M/m: finite system capacity, m; special case! …… 0 1 2 m-1 m l l l l l 3m m 2m (m-1)m mm for n m i n P m i i n n 0, 1, 2,... ! ( ) ! ( ) 0 = = å = m l m l • Probability of full system, Pm, is “Erlang’s loss formula” • Exactly same expression for Pn of M/G/m system with K=m

M/Moo(infinite no of servers (m-1) (m:+1y m+2 2 Pn or n= N is Poisson distributed! L=/p;W=1p;a=0;W=0 Many applications

M/M/¥ (infinite no. of servers) … 0 1 2 m-1 m m+1 l l l l l l l 3m m 2m (m-1)m mm (m+1}m (m+2)m … 0,1, 2,..... ! ( ) ( ) = × = - for n n e P n n m l m l • N is Poisson distributed! • L = l / m ; W = 1 / m ; Lq = 0; Wq = 0 • Many applications

Variations and extensions of birth-and-death queuing systems Huge number of extensions on the previous models Most common is arrival rates and service rates that depend on state of the system; some lead to closed-form expressions Systems which are not birth-and-death, but can be modeled by continuous time, discrete state Markov processes can also be analyzed State representation is the key(e.g MEK 1)

Variations and extensions of birth-and-death queuing systems • Huge number of extensions on the previous models • Most common is arrival rates and service rates that depend on state of the system; some lead to closed-form expressions • Systems which are not birth-and-death, but can be modeled by continuous time, discrete state Markov processes can also be analyzed • State representation is the key (e.g. M/Ek /1)

M/G/: Background Poisson arrivals: rate 2 General service times, S; fs(s); E[S]=1/; Os Infinite queue capacity The system is NoT a continuous time Markov process(most of the time"it has memory") We can, however, identify certain instants of time (epochs")at which all we need to know is the number of customers in the system to determine the probability that at the next epoch there will be 0, 1, 2,m, n customers in the system Epochs= instants immediately following the completion of a service

M/G/1: Background • Poisson arrivals; rate l • General service times, S; fS(s); E[S]=1/m; sS • Infinite queue capacity • The system is NOT a continuous time Markov process (most of the time “it has memory”) • We can, however, identify certain instants of time (“epochs”) at which all we need to know is the number of customers in the system to determine the probability that at the next epoch there will be 0, 1, 2, …, n customers in the system • Epochs = instants immediately following the completion of a service

M/G/1: Transition probabilities for system states at epochs (1) NE number of customers in the system at a random epoch, L e,, just after a service has been completed N'E number of customers in the system at the immediately following epoch R=number of new customers arriving during the service time of the first customer to be served after an epoch NEN+R- ifN>o NER InTO Note: make sure to understand how r is defined

M/G/1: Transition probabilities for system states at epochs (1) N = number of customers in the system at a random epoch, i.e., just after a service has been completed N' = number of customers in the system at the immediately following epoch R = number of new customers arriving during the service time of the first customer to be served after an epoch N' = N + R – 1 if N > 0 N' = R if N = 0 • Note: make sure to understand how R is defined

Epochs and the value of R Between t and t2. 2 Between t5 and t6, R=0 t2 t3 t4 t5 t6

Epochs and the value of R t1 t2 t3 t4 t5 t6 t N Between t1 and t2, R=2 Between t5 and t6, R=0