Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 38 · Networks of Queues

Decomposition and Bottlenecks in Non-Product-Form Networks

When service is not exponential, product form fails. Use the decomposition approximation with variability propagation to estimate delays in a line of queues.

Jackson and mean value analysis give exact answers, but only under strong assumptions: exponential service, FCFS, infinite buffers. Real lines have machines with steady cycle times, bursty arrivals, and rework. For these we use decomposition: analyze each station separately as a G/G/1 queue, and pass along an estimate of how variable the stream between stations is.

The method is the core of tools like Whitt's Queueing Network Analyzer. It is an approximation, and its accuracy should be checked against simulation, but it makes bottlenecks and variability effects visible quickly.

How variability flows through a station

A G/G/1 station takes an arrival stream with mean rate λ and squared coefficient of variation ca², and produces a departure stream with the same rate λ (in steady state) and an SCV that is a blend:

Text
cd² ≈ ρ² cs² + (1 - ρ²) ca²

Intuition: when the server is almost always busy (ρ near 1), departures simply mirror the service process, so cd² ≈ cs². When the server is mostly idle (ρ near 0), each customer is served immediately and the departure stream mirrors the arrival stream, so cd² ≈ ca².

For a tandem line the departure stream of station i is the arrival stream of station i + 1, so we can chain the approximation: ca²(i + 1) = cd²(i).

Line analysis

Station i then has waiting time estimated by Kingman:

Text
Wq_i ≈ ρ_i / (1 - ρ_i) · (ca_i² + cs_i²)/2 · E[S_i]

and the total time in the line is the sum of Wq_i + E[S_i].

Python Decomposition of a tandem line

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 an approximation calculator. The second station has high service variability, so its output stream is more variable and feeds extra delay into station 3. A single-station analysis that assumed Poisson arrivals everywhere (ca² = 1) would miss that.

Finding the bottleneck

Utilization alone is not a full picture. Compare two quantities for each station:

  1. Utilization ρ_i = λ E[S_i]. A station with ρ_i near 1 limits how much more demand the line can take.
  2. Share of delay Wq_i / Σ Wq. A station can have moderate utilization but a large share of delay because of high variability.

Improvement is cheapest where both are large. Reducing cs² at a busy, variable station may help more than buying speed at another.

Python Which improvement helps most?

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.

Compare the drops in total time. Reducing variability or speeding up the busiest, most variable station beats improving a less loaded one.

Decomposition ignores correlation between successive intervals in a stream, and it is not reliable with feedback, blocking or very heavy variability. Treat its answers as estimates and confirm important decisions with a simulation, as the next chapter shows.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A station has ρ = 0.9, ca² = 1 and cs² = 0. The departure SCV is approximately

    cd² = ρ² cs² + (1 - ρ²) ca² = 0 + 0.19 · 1 = 0.19.
  2. 2. When ρ is very small, the departure stream resembles

    An idle server passes customers straight through, so cd² ≈ ca².
  3. 3. In the decomposition method, what is Kingman used for?

    Each station is treated as a G/G/1 queue whose wait comes from Kingman's formula.
  4. 4. Which is a weakness of decomposition?

    It is an approximation; verify key results by simulation.

Summary

  • Decomposition treats each station as a G/G/1 queue and passes variability downstream.
  • cd² ≈ ρ² cs² + (1 - ρ²) ca² links input and output variability.
  • Combine utilization and delay share to find the bottleneck.
  • Always cross-check important results by simulation.

Next: Simulating an M/M/1 Queue from Scratch