Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 38 · M/G/1 and Variability

The M/G/1 Queue and the Pollaczek-Khinchine Formula

Drop the exponential service assumption: derive the mean waiting time of an M/G/1 queue, see why variability matters, and compute it from E[S] and E[S²].

Exponential service times are convenient but often wrong. A vending machine takes almost exactly the same time for every customer. A support call can take two minutes or two hours. The M/G/1 queue keeps Poisson arrivals at rate λ and one server, but lets the service time S have any distribution G. All we need is its mean E[S] and its second moment E[S²].

The central result, the Pollaczek-Khinchine (P-K) formula, shows that the mean wait depends on the variability of service, not only its mean. That is one of the most useful ideas in queueing theory.

The formula

Let ρ = λ E[S] (utilization; we need ρ < 1). Then the mean waiting time in the queue is:

Text
Wq = λ E[S²] / (2 (1 - ρ))

and the other mean values follow from W = Wq + E[S], Lq = λ Wq and L = λ W (Little's Law).

A formula in terms of variability

The squared coefficient of variation of service is cs² = Var(S) / E[S]². Since E[S²] = Var(S) + E[S]² = E[S]² (1 + cs²), we can rewrite the formula as:

Text
Wq = ρ (1 + cs²) E[S] / (2 (1 - ρ))  =  ((1 + cs²)/2) · Wq(M/M/1)

because the M/M/1 value is ρ E[S]/(1 - ρ). So the wait is the M/M/1 wait times the factor (1 + cs²)/2:

Service type cs² Factor (1 + cs²)/2
Deterministic (M/D/1) 0 0.5
Exponential (M/M/1) 1 1
Very variable 4 2.5

Deterministic service halves the waiting time of the exponential case. Highly variable service can multiply it several times.

Python Pollaczek-Khinchine calculator

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.

At 80 percent utilization the exponential queue has Wq = 4. The deterministic queue has half that, and the variable queue is 2.5 times worse. The server is equally busy in all rows; only the unevenness of service times differs.

Why variability hurts

When service times are very uneven, an occasional long job blocks many customers behind it, and those customers all inherit the delay. A long job is also more likely to be in service when you arrive, a point explored in the next lesson on residual life. Even though a long job is rare, the customers affected are many.

The P-K formula for the number in system

The P-K formula for the mean number in the system is often written:

Text
L = ρ + ρ² (1 + cs²) / (2 (1 - ρ))

You can check this: Lq = λ Wq = λ ρ (1 + cs²) E[S] / (2(1 - ρ)) = ρ² (1 + cs²)/(2(1 - ρ)), and L = Lq + ρ.

Python Compare P-K with a quick simulation (Lindley recursion)

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.

This is a simulation, so the simulated values will wobble a little around the theory, but they should be close.

For uniform service on [0, 2] the variance is 2²/12 = 1/3 and the mean is 1, so cs² = 1/3. Always check that your cs² is the variance divided by the mean squared.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which two numbers describe service time enough to compute the mean wait in M/G/1?

    The P-K formula depends only on E[S] and E[S²] (equivalently, the mean and variance).
  2. 2. At the same utilization, how does the M/D/1 wait compare with the M/M/1 wait?

    The factor (1 + cs²)/2 is 0.5 when cs² = 0.
  3. 3. λ = 0.5, E[S] = 1, cs² = 1. What is Wq?

    ρ = 0.5, Wq = ρ(1 + 1)·1 / (2·0.5) = 1.
  4. 4. What does cs² measure?

    cs² = Var(S)/E[S]². It is unitless.

Summary

  • M/G/1: Poisson arrivals, one server, general service times.
  • Wq = λ E[S²] / (2(1 - ρ)) = ((1 + cs²)/2) · Wq(M/M/1).
  • Variability in service raises the wait even at fixed utilization.
  • Little's Law turns Wq into Lq, W and L.

Next: Residual Life and the Inspection Paradox