Skip to content
Tutorials Center
My learning

Topics

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

Kingman's Formula for the G/G/1 Queue

When neither arrivals nor service are Poisson, Kingman's formula still gives a good estimate of waiting time: utilization, variability and mean service multiplied.

Poisson arrivals are a good model for independent customers, but many streams are smoother (a conveyor belt, a scheduled flight) or burstier (batches of packets, a bus unloading). For a queue where both interarrival times and service times follow general distributions, the G/G/1 queue, no exact simple formula exists. Kingman's formula gives an excellent approximation that is exact for M/G/1 and M/M/1 and accurate at high load.

The formula

Let ca² be the squared coefficient of variation of interarrival times, cs² that of service times, E[S] the mean service time, and ρ = λ E[S] < 1. Then:

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

Read it as the product of three factors:

  1. Utilization effect ρ/(1 - ρ): waiting explodes as ρ → 1.
  2. Variability effect (ca² + cs²)/2: the average of arrival and service variability.
  3. Time scale E[S]: slow servers wait longer in absolute terms.

Check it against known cases. For M/M/1 (ca² = cs² = 1), Wq = ρE[S]/(1 - ρ). ✓. For M/G/1 (ca² = 1), you get ρ(1 + cs²)E[S]/(2(1 - ρ)), the Pollaczek-Khinchine value. ✓

Python Kingman 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 90 percent utilization the M/M/1 wait is 9. Smoothing the arrivals (ca² = 0) halves it, and perfectly regular arrivals and service (ca² = cs² = 0) give 0 in the approximation. (The true D/D/1 queue indeed has zero wait when ρ < 1; Kingman is accurate in the heavy-traffic regime rather than at tiny variability.)

Reducing waiting: where to act

Because ca² and cs² enter as a sum, variability on either side counts equally. That gives practical levers:

  • Appointments and reservations reduce ca² (arrivals become less random than Poisson).
  • Standard work and training reduce cs².
  • Lower utilization helps most when ρ is already high, because of the 1/(1 - ρ) factor.
Python Which lever is cheaper? Utilization vs variability

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.

Small changes in load can beat large changes in variability near full utilization. Which lever wins depends on the numbers, so always compute rather than guess.

Accuracy and warnings

Kingman's formula is an approximation:

  • It becomes exact as ρ → 1 in the sense that the ratio of the formula to the true wait approaches 1 (heavy-traffic limit).
  • At moderate load it can be off by a noticeable margin when ca² and cs² are very different. Refined versions such as the Allen-Cunneen formula adjust for this in the multi-server case (G/G/c), where the approximation uses the Erlang C probability instead of ρ.
  • It estimates means only; it says nothing reliable about the distribution of waits.

Use Kingman for a quick sanity check and for what-if comparisons. If a decision depends on a few percent, simulate the system, as covered in the next chapter.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Kingman's formula for G/G/1 reduces to the M/M/1 mean wait when

    With both SCVs equal to 1 the factor (ca² + cs²)/2 is 1, leaving ρE[S]/(1 - ρ).
  2. 2. λ = 0.5, E[S] = 1, ca² = 1, cs² = 3. Kingman gives Wq =

    ρ/(1 - ρ) = 1, (1 + 3)/2 = 2, times E[S] = 1 gives 2.
  3. 3. Which change reduces ca²?

    Scheduled arrivals are more regular than Poisson arrivals, so their interarrival SCV is below 1.
  4. 4. The approximation is most reliable when

    Kingman's formula is a heavy-traffic approximation that becomes exact in the limit ρ → 1.

Summary

  • Kingman: Wq ≈ (ρ/(1 - ρ)) · ((ca² + cs²)/2) · E[S].
  • Exact for M/M/1 and M/G/1; good in heavy traffic.
  • Both arrival and service variability matter equally.
  • Use it for quick comparisons, simulation for precise answers.

Next: Tandem Queues and Burke's Theorem