M/M/c queue

Template:Use American English Template:Short description In queueing theory, a discipline within the mathematical theory of probability, the M/M/c queue (or Erlang–C modelTemplate:Rp) is a multi-server queueing model. In Kendall's notation it describes a system where arrivals form a single queue and are governed by a Poisson process, there are Template:Var servers, and job service times are exponentially distributed. It is a generalisation of the M/M/1 queue which considers only a single server. The model with infinitely many servers is the M/M/∞ queue.

Model definition

An M/M/c queue is a stochastic process whose state space is the set {0, 1, 2, 3, ...} where the value corresponds to the number of customers in the system, including any currently in service.

• Arrivals occur at rate Template:Var according to a Poisson process and move the process from state Template:Var to Template:Var+1.
• Service times have an exponential distribution with parameter Template:Var. If there are fewer than Template:Var jobs, some of the servers will be idle. If there are more than Template:Var jobs, the jobs queue in a buffer.
• The buffer is of infinite size, so there is no limit on the number of customers it can contain.

The model can be described as a continuous time Markov chain with transition rate matrix Template:Block indent

on the state space Template:Nowrap The model is a type of birth–death process. We write Template:Var = Template:Var/(Template:Var) for the server utilization and require Template:Var < 1 for the queue to be stable. Template:Var represents the average proportion of time which each of the servers is occupied (assuming jobs finding more than one vacant server choose their servers randomly).

The state space diagram for this chain is as below.

Stationary analysis

Number of customers in the system

If the traffic intensity is greater than one then the queue will grow without bound but if server utilization $\rho =\frac{\lambda }{c\mu }<1$ then the system has a stationary distribution with probability mass function Template:Block indent

where Template:Var_Template:Var is the probability that the system contains Template:Var customers.

The probability that an arriving customer is forced to join the queue (all servers are occupied) is given by Template:Block indent

which is referred to as Erlang's C formula and is often denoted C(Template:Var, Template:Var/Template:Var) or E_{2,Template:Var}(Template:Var/Template:Var). The average number of customers in the system (in service and in the queue) is given by Template:Block indent

Busy period of server

The busy period of the M/M/c queue can either refer to:

• full busy period: the time period between an arrival which finds Template:Var−1 customers in the system until a departure which leaves the system with Template:Var−1 customers
• partial busy period: the time period between an arrival which finds the system empty until a departure which leaves the system again empty.

Write Template:Var_Template:Var = min( t: Template:Var jobs in the system at time 0⁺ and Template:Var − 1 jobs in the system at time Template:Var) and Template:Var_Template:Var(Template:Var) for the Laplace–Stieltjes transform of the distribution of Template:Var_Template:Var. Then

1. For Template:Var > Template:Var, Template:Var_Template:Var has the same distribution as Template:Var_Template:Var.
2. For Template:Var = Template:Var,Template:Block indent
3. For Template:Var < Template:Var,Template:Block indent

Response time

The response time is the total amount of time a customer spends in both the queue and in service. The average response time is the same for all work conserving service disciplines and is Template:Block indent

Customers in first-come, first-served discipline

The customer either experiences an immediate exponential service, or must wait for Template:Var customers to be served before their own service, thus experiencing an Erlang distribution with shape parameter Template:Var + 1.

Customers in processor sharing discipline

In a processor sharing queue the service capacity of the queue is split equally between the jobs in the queue. In the M/M/c queue this means that when there are Template:Var or fewer jobs in the system, each job is serviced at rate Template:Var. However, when there are more than Template:Var jobs in the system the service rate of each job decreases and is $\frac{c\mu }{n}$ where Template:Var is the number of jobs in the system. This means that arrivals after a job of interest can impact the service time of the job of interest. The Laplace–Stieltjes transform of the response time distribution has been shown to be a solution to a Volterra integral equation from which moments can be computed. An approximation has been offered for the response time distribution.

Finite capacity

In an M/M/Template:Var/Template:Var queue only Template:Var customers can queue at any one time (including those in service). Any further arrivals to the queue are considered "lost". We assume that Template:Var ≥ Template:Var. The model has transition rate matrix Template:Block indent on the state space {0, 1, 2, ..., Template:Var, ..., Template:Var}. In the case where Template:Var = Template:Var, the M/M/Template:Var/Template:Var queue is also known as the Erlang–B model.Template:Rp

Transient analysis

See Takács for a transient solution and Stadje for busy period results.

Stationary analysis

Stationary probabilities are given by

The average number of customers in the system is Template:Block indent and the average time in the system for a customer is Template:Block indent

The average time in the queue for a customer is Template:Block indent

The average number of customers in the queue can be obtained by using the effective arrival rate. The effective arrival rate is calculated by Template:Block indent

Thus we can obtain the average number of customers in the queue by Template:Block indent

An implementation of the above calculations in Python can be found.

Heavy-traffic limits

Writing Template:Var(Template:Var) for the number of customers in the system at time Template:Var, it can be shown that under three different conditions the process Template:Block indent converges to a diffusion process.Template:Rp

1. Fix Template:Var and Template:Var, increase Template:Var and scale by Template:Var = 1/(1 − Template:Var)².
2. Fix Template:Var and Template:Var, increase Template:Var and Template:Var, and scale by Template:Var = Template:Var.
3. Fix as a constant Template:Var whereTemplate:Block indent

and increase Template:Var and Template:Var using the scale Template:Var = Template:Var or Template:Var = 1/(1 − Template:Var)². This case is called the Halfin–Whitt regime.

See also

• Spectral expansion solution
• M/G/k queue