Queuing Formulas - Missouri S&T

1 Queuing Formulas Contents1 Notation22 Basic Queueing Formulas23 Single-Server Formulas .. Some additional useful facts .. Examples .. 44 Multiple-Server Queues5 Notes prepared by A. Gosavi, Department of Engineering Management and Systems Engineering, Mis-souri S & Notation : mean rate of arrival. It is equal to 1=E[Inter-arrival-Time] whereE[:] denotes theexpectation operator. : mean service rate. It is equal to 1=E[Service-Time]. = = for single server queues: utilization of the server; also the probability that theserver is busy or the probability that someone is being served.

2 C: number of servers. Pn: probability that there arencustomers in the system. L: Mean number of customers in the system. Lq: mean number of customers in the queue. W: mean wait in the system. Wq: mean wait in the queue. C2: Coefficient of variation of a random variable;C2=V ariance(Mean)2. C2s: Coefficient of variation of service time. C2a: Coefficient of variation of inter-arrival time. 2s: variance of service time. K: capacity of Basic Queueing FormulasLittle s rule provide the following results:L= W;Lq= Wq:W=Wq+1 :23 Single-Server QueuesThe following notation is used for representing queues: A/B/c/K whereAdenotes thedistribution of the inter-arrival time, B that of the service time,cdenotes the number ofservers, andKdenotes the capacity of the queue.

3 IfKis omitted, we assume thatK= for Markov and is commonly used for the exponential distribution. Hence anM=M=1 queue is one in which there is one server (and one channel) and both the inter-arrival time and service time are exponentially distributed. AnM=G=1 queue is one withone server in which the inter-arrival time is exponentially distributed and the service time isgenerally distributed, , the service time has any given distribution. AG=G=1 queue is onewith one server in which both service and the inter-arrival time have any given FormulasFor the M/M/1 queue, we can prove thatLq= 21 :For the M/G/1 queue, we can prove thatLq= 2 2s+ 22(1 )The above is called the Pollazcek-Khintichine formula (named after its inventors and discov-ered in the 1930s).

4 For the G/G/1 queue, we do not have an exact result. The followingapproximation(derivedby Marchal in 1976) is popular:Lq 2(1 +C2s)(C2a+ 2C2s)2(1 )(1 + 2C2s):Notice that if the mean rate of arrival is , and 2adenotes the variance of the inter-arrivaltime, then:C2a= 2a(1= )2:Similarly, if denotes the service rate and 2sdenotes the variance of the service time, then:C2s= 2s(1= )2 Some additional useful facts If the random variableXis uniformly distributed with parameters (a; b), whereaisthe minimum value andbthe maximum value, then the mean of X is (a+b)=2 and thevariance is(b a)212.

5 For the exponential distribution if the mean if 1= , the variance is 1= 2. When a variable is deterministic, , inter-arrival time is fixed, its variance is zeroand hence so is its coefficient of variation. Consider two random variables,XandY. Then ifE[:] denotes the mean andV[:]denotes the variance, thenE[X+Y] =E[X] +E[Y];also, ifXandYare independent,V[X+Y] =V[X] +V[Y] ExamplesExample 1:Consider the following scenario: the inter-arrival time is exponentially dis-tributed with a mean of 10 minutes and the service time is also exponentially distributedwith a mean of 8 means, find the (i) mean wait in the queue, (ii) mean number in the queue,(iii) the mean wait in the system, (iv) mean number in the system and (v) proportion oftime the server is have an M/M/1 system.

6 We also have: = 1=10; = 1=8. Hence, = 8=10. Then:Number in the Queue =Lq= 21 =0:821 0:8= 3:2:Wait in the Queue =Wq=Lq= = 32mins:Wait in the System =W=Wq+ 1= = 40mins:Number in the System =L= W= 4:Proportion of time the server is idle = 1 = 0:2:Example 2:Consider the following scenario: the inter-arrival time is exponentially dis-tributed with a mean of 10 minutes and the service time has the uniform distribution witha maximum of 9 minutes and a minimum of 7 minutes, find the (i) mean wait in the queue,(ii) mean number in the queue, (iii) the mean wait in the system, (iv) mean number in thesystem and (v) proportion of time the server is have an M/G/1 system.

7 We also have: = 1=10; the mean service time will be (7+9)=2 =8, , = 1=8. The variance of the service time, 2swill equal (9 7)2=12 = 1=3. Also, = 8=10. Then:Number in the Queue =Lq= 2 2s+ 22(1 )= 1:608:Wait in the Queue =Wq=Lq= = 16:08mins:Wait in the System =W=Wq+ 1= = 24:08mins:Number in the System =L= W= 2:408:Proportion of time server is idle = 1 = 0:2:Example 3:Consider the following scenario: the inter-arrival time has a distribution thatis unknown with a mean of 10 minutes and a variance of 2min2. The service time has theuniform distribution with a maximum of 9 minutes and a minimum of 7 minutes, find the (i)mean wait in the queue, (ii) mean number in the queue, (iii) the mean wait in the system,(iv) mean number in the system and (v) proportion of time the server is have a G/G/1 system.

8 We also have: = 1=10; the variance of the inter-arrival time is2. The mean service time will be (7 + 9)=2 = 8, , = 1=8. The variance of the servicetime, 2swill equal (9 7)2=12 = 1=3. Also, = 8=10. Then:C2a= 2a(1= )2= 0:02;C2s= 2s(1= )2= 1=192:Number in the Queue =Lq= 2(1 +C2s)(C2a+ 2C2s)2(1 )(1 + 2C2s)= 0:037:Wait in the Queue =Wq=Lq= = 0:373mins:Wait in the System =W=Wq+ 1= = 8:373mins:Number in the System =L= W= 0:8373:Proportion of time server is idle = 1 = 0:2:4 Multiple-Server QueuesWe will only consider the identical server case. Letcdenote the number of identical = c 5 For the M/M/c queue,Lq=P0( )c c!

9 (1 )2whereP0= 1=[c 1 m=0(c )mm!+(c )cc!(1 )]:Note thatP0denotes the probability that there are 0 customers in the the G/G/c queue, we have anapproximation(Kingman, 1964)WG=G=cq WM=M=cqC2a+C2s2;whereWA=B=cqdenotes the waiting time in the queue for the A/B/c