Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 38 ยท Scheduling and Queueing

Multi-Server Queues and Simulation

Size service systems with M/M/c and Erlang C and Erlang B formulas, see the effect of service variability with M/G/1, and simulate multi-server queues with an event heap in Python.

One server is rarely the whole story. Call centers have dozens of agents, supermarkets have several checkouts, web clusters have many workers. With c servers and a single shared line, the system is called M/M/c. This lesson gives the formulas used for staffing decisions (Erlang C and Erlang B), shows how service-time variability matters, and ends with a general discrete-event simulation you can adapt when formulas run out.

If you are new to the notation (arrival rate lambda, service rate mu, utilization), review Queueing Fundamentals and the M/M/1 Queue first.

The M/M/c queue

With c identical servers, each with rate mu, and one common line, let:

TEXT
a   = lambda / mu          (offered load, in "servers worth of work")
rho = a / c                (utilization per server, must be < 1)

The probability that an arriving customer finds all servers busy and has to wait is the Erlang C formula:

TEXT
C(c, a) = [ a^c / (c! (1 - rho)) ] / [ sum_{k=0}^{c-1} a^k / k!  +  a^c / (c! (1 - rho)) ]

Then the average queue wait is:

TEXT
Wq = C(c, a) / (c * mu - lambda)         Lq = lambda * Wq         W = Wq + 1/mu

Pooling servers behind one line is very efficient: a single line with c servers performs far better than c separate lines each with one server at the same utilization. That is why banks and airports use one snake line.

Python Erlang C and the staffing question

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You need at least 8 agents just to be stable (a = 7.5), but the waits drop sharply when you add a few more. The staffing rule on the last line uses the exponential tail of the waiting time, P(Wq > t) = C(c, a) * exp(-(c mu - lambda) t).

The square-root staffing rule says: staff for the offered load a plus a safety margin of about beta * sqrt(a) agents, with beta around 0.5 to 2 depending on the service goal. Bigger systems run at higher utilization for the same quality.

Losing customers: Erlang B

If there is no waiting room (a phone trunk line, a parking lot), customers who find all c servers busy are lost. This is the M/M/c/c model, and the Erlang B blocking probability is:

TEXT
B(c, a) = (a^c / c!) / sum_{k=0}^{c} a^k / k!

It can be computed stably by recursion: B(0) = 1, B(k) = a B(k-1) / (k + a B(k-1)). Erlang B is used to size telephone circuits, parking lots and hospital beds. It happens to hold for any service-time distribution with mean 1/mu (insensitivity).

Python Erlang B: how many lines for 1% blocking?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the diminishing returns: the first few extra servers cut blocking massively, while the last reduce it slowly.

Service variability: M/G/1

What if service times are not exponential? For a single server with Poisson arrivals and general service times of mean 1/mu and squared coefficient of variation cs2 (variance divided by mean squared), the Pollaczek-Khinchine formula gives:

TEXT
Wq = ((1 + cs2) / 2) * rho / (mu - lambda)

For exponential service cs2 = 1 and you recover M/M/1. For constant service times (M/D/1), cs2 = 0, so the queue wait is half that of M/M/1. For highly variable service (cs2 = 4), it is two and a half times larger. Variability itself is a cause of waiting, so standardizing the work (lower cs2) is as valuable as adding capacity.

Discrete-event simulation

When the system has priorities, breakdowns, time-varying arrivals or networks of queues, closed forms disappear, and you simulate. In a discrete-event simulation, the state changes only at events (arrival, departure). You keep a clock and a priority queue of future events, always processing the earliest. For a multi-server FIFO queue there is a neat shortcut: keep a heap with the time each server becomes free.

Python Simulating M/M/c and checking Erlang C

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simulation is close to Erlang C (waiting probability 0.508 against 0.509; the mean wait can differ by a few percent between seeds because waits are heavy-tailed), and it also gives something the formula does not: the 95th percentile of the wait, which is often what customers actually feel.

Using queueing models in optimization

Queueing models link to the rest of operations research:

  • Cost minimization: choose c to minimize c * cost_server + lambda * Wq * cost_waiting. Compute the total cost for each c (it is convex-like) and pick the best.
  • Constraints in an LP/MILP: the performance of a queue is a nonlinear function of c, but you can tabulate it for each integer c and let a MILP choose a staffing level per time period using binary variables, as in Staff Rostering.
  • Capacity planning: keep utilization below a threshold such as 80-85% to protect against variability.
  • Networks of queues: Jackson networks multiply M/M/c results when customers route randomly between stations.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the Erlang C formula give?

    Erlang C is the probability that all c servers are busy when a customer arrives, so the customer waits.
  2. 2. Which model describes a phone system where callers get a busy signal when all lines are in use?

    There is no waiting room, so blocked customers are lost; the blocking probability is given by Erlang B.
  3. 3. Compared with M/M/1 at the same rho, what is the queue wait of an M/D/1 queue?

    With constant service times cs2 = 0, so the Pollaczek-Khinchine factor (1 + cs2)/2 is 1/2.
  4. 4. Why does a single shared line with c servers beat c separate lines?

    With separate lines, one server can be idle while customers wait at another; pooling removes that inefficiency.

Summary

  • M/M/c adds c servers behind one line; utilization is rho = lambda / (c * mu), and Erlang C gives the probability of waiting.
  • Staffing decisions use Erlang C (waiting systems) or Erlang B (loss systems), searching for the smallest c that meets the service target.
  • Service variability raises waits: M/G/1 waiting scales with (1 + cs2) / 2.
  • A discrete-event simulation with a heap of server-free times handles models without formulas and gives percentiles.
  • Queueing results feed optimization models for staffing and capacity.

Next: Blending and Feed Mix