Comparing Service-Time Variability at Fixed Traffic Intensity

Why Service-Time Variability Matters

Two single-server queues can have the same arrival rate, the same average service duration, and therefore the same traffic intensity, yet have different average waits. The Pollaczek–Khinchine formula makes the source of that difference precise: for an M/G/1 queue, mean waiting time depends on the second moment of service time. Since the mean service time is held fixed in this comparison, differences in the second moment are exactly differences in service-time variance.

We consider a first-come, first-served, single-server queue. Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Arrivals are a Poisson process \((N_t)_{t\ge0}\), with time index \(t\ge0\), state space \(\mathbb{Z}_{\ge0}\), and rate \(\lambda>0\). Customer service times \(S_1,S_2,\ldots\) are independent and identically distributed nonnegative random variables, independent of the arrival process. Write \(S\) for a generic service time, \(m=\mathbb{E}[S]\), and \(\sigma^2=\operatorname{Var}(S)\). The queue length \(Q_t\) is also indexed by \(t\ge0\) and takes values in \(\mathbb{Z}_{\ge0}\); for general service times, \(Q_t\) alone need not be a Markov process. Let \((\mathcal{F}_t)_{t\ge0}\) represent the history of arrivals and service in the queue up to time \(t\).

Assume \(m>0\), \(\lambda m<1\), and \(\mathbb{E}[S^2]<\infty\). The traffic intensity is \(\rho=\lambda m\); the inequality \(\rho<1\) is the stability condition for the stationary M/G/1 setting considered here. Let \(W_q\) denote a stationary customer's waiting time before service begins, excluding that customer's own service time. Its mean is taken in the stationary queue.

The key identity is \(\mathbb{E}[S^2]=m^2+\sigma^2\). If \(m\) and \(\lambda\) are fixed, then \(\rho\) is fixed as well. Substitution gives a direct decomposition of the mean wait into a part determined by the common mean service and a part determined by variability.

The coefficient of \(\sigma^2\) in the first expression is positive whenever \(\lambda>0\) and \(\rho<1\). Thus, at equal arrival rate and service mean, a larger service-time variance produces a larger mean waiting time. The same comparison can be made at fixed \(\rho\) and fixed \(m\), since then \(\lambda=\rho/m\) is also fixed. The coefficient of variation squared, \(\operatorname{CV}^2=\sigma^2/m^2\), gives a dimensionless way to state the variability contribution.

Exact Comparison at Fixed Traffic Intensity

Proof. Both queues have the same traffic intensity \(\rho=\lambda m<1\). By the Pollaczek–Khinchine formula, \(w_r=\lambda\mathbb{E}[S_r^2]/(2(1-\rho))\) for \(r=1,2\). For each service time, \(\mathbb{E}[S_r^2]=m^2+\sigma_r^2\). Subtracting the two formulas cancels the common \(m^2\) term and yields \(w_1-w_2=\lambda(\sigma_1^2-\sigma_2^2)/(2(1-\lambda m))\). The denominator and \(\lambda\) are positive, so the sign of the difference is exactly the sign of \(\sigma_1^2-\sigma_2^2\). This proves both directions of the ordering claim and the equality statement. \(\square\)

Proof. For any service time \(S\) with mean \(m\), \(\operatorname{Var}(S)=\mathbb{E}[(S-m)^2]\ge0\), since the squared quantity is nonnegative. It is zero exactly when \((S-m)^2=0\) with probability one, or equivalently \(S=m\) with probability one. The mean-waiting formula expressed using variance is increasing in \(\sigma^2\), so its minimum occurs at variance zero. Deterministic service attains that value, and the equality condition just established shows that no other service-time law attains it. \(\square\)

Worked Comparisons

What the Comparison Does—and Does Not—Say

The comparison is about the stationary mean waiting time. Equal means and equal variances imply equal mean waits under these assumptions, because the formula uses only the first two service-time moments. They do not imply that the waiting-time distributions are identical. The formula also does not say that every customer in the more variable queue waits longer, or that the probability of waiting more than a specified threshold is necessarily larger. Those are statements about distributions, not just their means.

Holding traffic intensity fixed requires care. If both the mean service time \(m\) and \(\rho\) are fixed, then the arrival rate is fixed too, since \(\lambda=\rho/m\). But if only \(\rho\) is held fixed while \(m\) changes, then \(\lambda\) changes and the mean waiting time also carries the scale factor \(m\): $$ \mathbb{E}[W_q]=\frac{\rho m}{2(1-\rho)}(1+\operatorname{CV}^2). $$ So a claim that one queue has a smaller mean wait just because its service variance is smaller is not justified when the service means differ. A fair variability comparison holds the mean service time fixed as well as the traffic intensity.

The assumptions matter. When \(\rho\ge1\), the stationary stable-queue comparison above does not apply. If the service-time second moment is infinite, the finite-mean formula cannot be used to produce a finite wait. And if arrivals are not Poisson or the service discipline is not the one assumed, this M/G/1 formula is not automatically valid. Check the model conditions before substituting moments.

Common pitfall. A frequent error is to insert \(\operatorname{Var}(S)\) in place of \(\mathbb{E}[S^2]\) in the Pollaczek–Khinchine formula. For the exponential example with mean \(2\), that mistake would give \(\frac{(\tfrac14)(4)}{2(1-\tfrac12)}=1\), incorrectly matching deterministic service. The formula requires the second moment, which is \(m^2+\operatorname{Var}(S)=4+4=8\) in this example; the correct mean wait is \(2\). The variance form is valid only after retaining the \(m^2\) term.