A Call Centre Queue (M/M/N)

Consider a queue where N servers serve one job at a time. The remaining jobs wait in a queue. Jobs arrive as a Poisson process of rate \lambda. Jobs have independent, exponentially distributed service requirements with mean \mu^{-1}. In Kendall notation, this is called an M/M/N queue.

We can think of this as a simple model of a call centre. Some customers receive service immediately when there are idle servers. Otherwise, they must wait in the queue for the next available server.

Here, W denotes the waiting time in the queue. In particular, W>0 means that an arriving job must wait before entering service. We write \rho=\lambda/\mu for the offered load.

M/M/N queue.

Proposition

The number of jobs in the M/M/N queue is a reversible Markov chain. It is positive recurrent when \rho<N and has stationary distribution

\displaystyle \pi_n=\begin{cases}\dfrac{\left(\frac{\rho}{N}\right)^{n-N}\frac{\rho^N}{N!}}{\displaystyle\sum_{i=0}^{N-1}\frac{\rho^i}{i!}+\frac{\rho^N}{N!}\frac{N}{N-\rho}}, & n>N,\\[10pt]\dfrac{\frac{\rho^n}{n!}}{\displaystyle\sum_{i=0}^{N-1}\frac{\rho^i}{i!}+\frac{\rho^N}{N!}\frac{N}{N-\rho}}, & n\leq N.\end{cases}

In particular, the probability that a job has to wait is

\displaystyle \mathbb P(W>0)=\frac{\frac{\rho^N}{N!}\frac{N}{N-\rho}}{\displaystyle\sum_{i=0}^{N-1}\frac{\rho^i}{i!}+\frac{\rho^N}{N!}\frac{N}{N-\rho}}.

This is sometimes called the Erlang C formula. The expected waiting time is

\displaystyle \mathbb E[W]=\frac{1}{N\mu-\lambda}\,\mathbb P(W>0)=\frac{1}{\mu(N-\rho)}\,\mathbb P(W>0).

Remark. The proof below is tedious but straightforward. Feel free to skip it.

Proof

The queue is a continuous-time Markov chain. Its state is the number of jobs in the system. The transition rate from state n to state n+1 is \lambda, while the transition rate from state n to state n-1 is \min\{n,N\}\mu.

The detailed balance equations are

\displaystyle N\mu\pi_n=\lambda\pi_{n-1}\qquad\text{for }n>N,

\displaystyle n\mu\pi_n=\lambda\pi_{n-1}\qquad\text{for }n\leq N.

Therefore, for n\leq N,

\displaystyle \pi_n=\frac{\rho}{n}\pi_{n-1}=\frac{\rho^2}{n(n-1)}\pi_{n-2}=\cdots=\frac{\rho^n}{n!}\pi_0.

For n>N,

\displaystyle \pi_n=\frac{\rho}{N}\pi_{n-1}=\frac{\rho^2}{N^2}\pi_{n-2}=\cdots=\left(\frac{\rho}{N}\right)^{n-N}\pi_N=\left(\frac{\rho}{N}\right)^{n-N}\frac{\rho^N}{N!}\pi_0.

To find \pi_0, we sum over all states:

\displaystyle 1=\sum_{n=0}^{\infty}\pi_n=\sum_{n=0}^{N-1}\frac{\rho^n}{n!}\pi_0+\sum_{n=N}^{\infty}\left(\frac{\rho}{N}\right)^{n-N}\frac{\rho^N}{N!}\pi_0=\left(\sum_{n=0}^{N-1}\frac{\rho^n}{n!}+\frac{\rho^N}{N!}\frac{N}{N-\rho}\right)\pi_0.

Thus,

\displaystyle \pi_0=\left(\sum_{i=0}^{N-1}\frac{\rho^i}{i!}+\frac{\rho^N}{N!}\frac{N}{N-\rho}\right)^{-1}.

Together with the expressions for \pi_n above, this gives the stated stationary distribution.

The probability that a job has to wait is

\displaystyle \mathbb P(W>0)=\sum_{n=N}^{\infty}\pi_n=\frac{\frac{\rho^N}{N!}\frac{N}{N-\rho}}{\displaystyle\sum_{i=0}^{N-1}\frac{\rho^i}{i!}+\frac{\rho^N}{N!}\frac{N}{N-\rho}}.

The number of jobs waiting for service is (Q-N)_+, where Q is the total number of jobs in the system. Hence,

\displaystyle \mathbb E[(Q-N)_+]=\sum_{n=N}^{\infty}(n-N)\pi_n=\sum_{n=N+1}^{\infty}(n-N)\left(\frac{\rho}{N}\right)^{n-N}\frac{\rho^N}{N!}\pi_0=\frac{\frac{\rho}{N}}{\left(1-\frac{\rho}{N}\right)^2}\frac{\rho^N}{N!}\pi_0=\frac{\rho}{N-\rho}\,\mathbb P(W>0).

Finally, applying Little’s Law to the waiting queue gives

\displaystyle \mathbb E[W]=\frac{\mathbb E[(Q-N)_+]}{\lambda}=\frac{1}{\mu(N-\rho)}\,\mathbb P(W>0)=\frac{1}{N\mu-\lambda}\,\mathbb P(W>0).

This proves the result.

□

Example. Suppose that a call centre receives 600 calls per hour and that each call has a handling time of 5 minutes. If calls must be answered within one minute on average, how many operators should the call centre employ?

Remark. Other factors to consider in call-centre design include the number of calls that are abandoned, the number of calls that are blocked, and shrinkage, which is the time during which operators are not available to take calls. One may also need to account for overdispersion in the arrival process, where the variance in the number of arrivals is greater than the mean, unlike in a Poisson process.

Resource Pooling (M/M/N versus N × M/M/1)

There can be significant advantages to combining multiple queues into a single queue. This is an example of resource pooling.

For example, suppose that we compare N separate M/M/1 queues with a single M/M/N queue. We reorganize the same servers into one pooled resource, as illustrated below.

Resource pooling.

Suppose that the total arrival rate is \lambda. Under the separate-queue system, each M/M/1 queue receives arrival rate \lambda/N. The expected waiting time in the separate queues and in the pooled M/M/N queue are therefore

\displaystyle \mathbb E[W_{\mathrm{separate}}]=\frac{1}{\mu-\lambda/N}\qquad\text{and}\qquad \mathbb E[W_{\mathrm{pooled}}]=\frac{1}{N\mu-\lambda}\,\mathbb P(W>0)\leq\frac{1}{N\mu-\lambda}.

Since

\displaystyle \frac{1}{\mu-\lambda/N}=\frac{N}{N\mu-\lambda},

resource pooling can reduce the expected waiting time by as much as a factor of N.

Leave a comment