Script

QUEUING MODELS – M/M/k Queues

Slide 1

  • Welcome back.
  • In this module we look at the basic queuing model, the M/M/k model

Slide 2

  • Recall that in general
  • Queues are classified by giving its
  • Arrival distribution, service distribution, and number of servers
  • And that Poisson systems are
  • Designated by M
  • Deterministic systems by D
  • And systems with some general probability distribution are designated by G
  • We will be begin our discussion of specific queues with the M/M/1 system

Slide 3

  • In an
  • M/M/1 system
  • The first M designates that the arrival process is a Poisson process where we assume that we know the average arrival rate is lambda per hour.
  • The second Mdesignates that the service process is a Poisson process where we assume that we know the average service rate is mu per hour meaning the average service time is 1 over mu hours.
  • The 1 means that there is only one server
  • This is perhaps the simplest queuing system – it is sorta like the EOQ model for inventory in that many more real life models are simply variants of the M/M/1 with certain assumptions added, changed or relaxed.

Slide 4

  • For every queuing system we wish to determine the steady state performance measures we’ve discussed before.
  • Derivations of these quantities are not too complicated but here we will simply state the results for the M/M/1 model. First recall that to reach steady state, lambda must be less than mu.
  • If that is the case, the average number of customers in the system, L is lambda over mu minus lambda
  • Then the average number of customers in the queue, L sub Q, is L minus lambda over mu;
  • The average time a customer spends in the system, W, is L divided by lambda hours
  • The average time a customer spends in the queue W sub Q, is L sub Q divided by lambda hours
  • The probability there are no customers in the system p sub 0 is 1 minus lambda over mu – note that this is also the probability the one server is idle
  • The probability there are n customers in the system p sub n lambda over mu raised to the n-th power times p sub 0
  • And the average number of customers being served, which is the proportioin of time the server is busy or rho, is lambda over mu.

Slide 5

  • Let’s look at a specific example
  • Suppose customers arrive to Mary’s Shoe Store according to a Poisson process on the average of one every 12 minutes
  • Service times follow a Poisson process and average 8 minutes.
  • Mary is the only server.
  • This is an M/M/1 system with an average arrival rate of
  • Lambda equal to 60 minuets per hour divided by 12 minutes per customer equals 5 customers per hour
  • And mu equals 60 minutes per hour divided by the average service time of 8 minutes or 7.5 customers per hour
  • So we will reach steady state
  • Because lambda is less than mu.

Slide 6

  • Then for Mary’s shoes
  • The average number of busy servers, rho is
  • Lambda over mu or 5 over 7.5 or two-thirds
  • The average number of customers in the system, L, is lambda over mu minus lambda or 5 over 7.5 minus 5 which is 5 over 2.5 or 2.
  • The average number of customers in the queue, L sub Q, is L minus lamba over mu or 2 minus two-thirds or four-thirds
  • The average time that a customer spends in the system, W, is L divided by lambda or 2 divided by 5 or two-fifths of an hour.
  • The average time that a customer spends in the queue, W sub Q, is L sub Q divided by lambda or four-thirds divided by 5 or four-fifteenths of an hour.
  • The probability the server is idle, which is the probability that there are no customers in the system, p sub 0, is 1 minus lambda over mu or 1 minus two-thirds or one-third.
  • And the probability there are 3 customers in the system is lambda over mu raised to the third power times p sub 0 which is two-thirds cubed times one-third or 8 81-sts.

Slide 7

  • While these formulas were simple for the M/M/1 case
  • For other models these formulas can be quite complex
  • So we can use a computer queuing template to generate the corresponding quantities of interest
  • To get the results for the M/M/1 model, we go to the M/M/k worksheet of the template called Queue.
  • After inputting lambda and mu, the results are given in the row for k equals to 1 server.

Slide 8

  • So here is the queuing template
  • And we go to the MMk worksheet
  • We enter 5 for lambda and 7.5 for mu and the results for any number of servers for which steady state is achieved are given below.
  • Since we have one server, the results are given in row 11. Note that the numbers beginning in column J are the values of p sub 0, p sub1, p sub 2 and so forth.
  • So p sub 3, the probability there are 3 customers in the system, is .09877.

Slide 9

  • Now we turn to M M k systems
  • An M M k system is one whose
  • Arrival process is Poisson
  • Whose service process is Poisson
  • And has k identical servers
  • Recall that to reach steady state, lambda must be less than k times mu

Slide 10

  • The performance measures here are much more complex.
  • For example here are the formulas for p sub 0 and L respectively.

Slide 11

  • Again, let’s look at a specific example.
  • Between 9 and 1 on Saturdays
  • The arrival process to the Littletown Post Office follows a Poisson process with customers arriving at a rate of 100 per hour.
  • Service times follow an exponential distribution (which means a Poisson process) with an average service time of 1.5 minutes. That means each server serves at a rate of 60 divided by 1.5 or 40 customers per hour.
  • It employs 3 clerks during this time period.
  • This is an M M 3 system with
  • Lamba equal to 100,
  • mu equal to 40 and k equal to 3
  • Since lamba equals 100 with is less than k mu or 3 times 40 or 120,
  • steady state will be reached.

Slide 12

  • Using those horrible formulas for p sub 0 and L
  • It can be shown that p sub 0 equals to .044944
  • And L equals 6.0112
  • Then L sub Q equals L minus lambda over mu, 6.0112 minus 2.5 or 3.5112
  • W equals L divided by lambda, 6.0112 divided by 100 or .060112 hours
  • W sub Q equals L sub Q divided by lambda, 3.5112 divided by 100 or .035112 hours
  • The average number of busy servers, rho is lambda over mu, 100 over 40 or 2.5
  • And the system utilization rate, which is rho over k or 2.5 over 3 or .83. That means the each server is busy, on the average, 83% of the time.

Slide 13

  • We can get these values off the queuing template
  • We go to the M M k worksheet
  • Input lambda equal to 100 and mu equal to 40
  • And since there are 3 servers, the steady state results are in row 13 corresponding to k equal to 3

Slide 14

  • We conclude this module by looking at a finite queuing model, the M M k F model
  • This is one with
  • A Poisson arrival process
  • A Poisson service process
  • k identical servers
  • But a maximum of F customers can be in the system at any time.
  • Now because the queue cannot build up indefinitely, because it is a finite queuing situation, steady state will be achieved regardless of the values for lambda and mu.
  • Formulas for the steady state quantities for this model are quite complex, so we will only uses the template to get them.

Slide 15

  • Since this is a finite queuing model
  • only 0, 1, 2 up to F customers can possibly be in the system at any time.
  • A potential arriving customer who arrives when there are less than F customers in the system will join the system
  • But a potential arriving customer who tries to arrive when there are already F customers in the system will not join the system and his business is lost
  • Thus the effective arrival rate, the actual rate at which customers get through to the system, designated by lambda sub e, is equal to the potential arrival rate, lambda, times the probability that the system IS NOT full. The probability it is full is p sub F, so the probability it is not full is 1 minus p sub F.

Slide 16

  • Let’s look at a specific example.
  • The calling process to Ryan’s Roofing is Poisson. On the average 10 customers per hour try to dial the company.
  • There is only one operator who averages 3 minutes per call.
  • The service process is also Poisson.
  • There are 3 phone lines so the maximum number of calls in the system is 3, the one the operator is talking to plus two on hold. Anyone who calls when there are already two people on hold will get the busy signal, will not join the system, and his business is lost.
  • This is an M M 1 3 system with
  • Lambda equal to 10 per hour
  • And mu equal to 60 divided by 3 or 20 per hour

Slide 17

  • The worksheet for the M M k F template is designed for situations in which
  • There could be a queue of at least 1, that is, the maximum number of customers in the system, F, must exceed the number of servers, k.
  • To calculate the effective arrival rate, lambda sub e, we locate p sub F on the right side of the M M k F worksheet and take lambda and multiply it by 1 minus p sub F.

Slide 18

  • Here is the worksheet corresponding to the Ryan Roofing problem
  • The M M k F worksheet has been selected.
  • We input that lambda equals to 10, mu equals to 20, the number of servers is 1, and that the maximum number that can be in the system is 3.
  • The corresponding quantities of interest are then given in row 12.
  • P sub F equals p sub 3 in this case and is .06667.
  • So the effective arrival rate, lambda sub e, is 10 times 1 minus .06667 or 9.333. So while 10 customers per hour try to get through to Ryan Roofing, on the average only 9.333 do.

Slide 19

  • Let’s review what we’ve discussed in this module.
  • M M k systems are ones with
  • A Poisson arrival distribution
  • A Poisson or exponential service distribution
  • And k identical servers
  • While the quantities of interest for many models have quite complex formulas, the steady state formulas for the M M 1 model are quite simple and we gave them
  • We discussed finite queuing models and stated that
  • Steady state will always be reached
  • And that some arrivals will not join the system so that the effective arrival rate, lambda sub e, is lambda times 1 minus p sub F
  • And we showed how to use
  • The M M k template and the
  • M M k F template.

That’s it for this module. Do any assigned homework and I’ll be back to talk to you again next time.