The Pollaczek-Khinchine (PK) formula for the average waiting time of an \(M/G/1\) queue is a key result in Operations Research. We derive it using the renewal reward theorem, and follow the steps of Section 5.3.

We start from the simple observation that before an arrival gets access to the server, it must first wait for the job in service¹¹ If any. to complete, then for the queue to clear. From PASTA it follows that \(\E{\W} = \E{S_r} + \E{\QQ} \E S\), where \(\E{S_r}\) is the (time-)average remaining service time of the job in service.²² The rv \(S_{r}\) is also known as the remaining lifetime and is widely used in maintenance theory and actuarial sciences. With Little's law \(\E \QQ = \lambda \E\W\) and \(\rho = \lambda \E S\),

To proceed, we need an expression for \(\E{S_r}\).

Proof

In Fig. 1, the service of job \(k\) starts at \(\As_{k}\), so the job departs at time \(D_k=\As_k + S_k\). Hence, at any time \(s \in [\As_{k}, D_{k}]\), the remaining service time of job \(k\) is \(D_k-s\).

More generally, at some arbitrary time \(s\), the number of departures is \(D(s)\). Thus, \(D(s)+1\) is the index of the first job to depart after time \(s\), and its departure time is \(D_{D(s)+1}\). Consequently, the remaining service time at time \(s\) is \(D_{D(s)+1}-s\), provided that this job is in service, i.e., \(\As_{D(s)+1} \leq s\). The total remaining service time as seen by the server up to time \(t\) is therefore

\begin{equation*} R(t) = \int_0^t (D_{D(s)+1}-s)\1{\As_{D(s)+1} \leq s} \d s, \end{equation*}

and \(\lim_{t\to\infty} R(t)/t = \E{S_{r}}\).

In Fig. 1, \(R(D_k) - R(D_{k-1}) =:Z_k\) equals the area of the triangle. By inspecting \(R(\cdot)\) at \(\{D_{k}\}\), we see that \(Z=\lim_{n\to\infty} \frac{1}{n}\sum_{k=1}^n S_k^2/ 2 = \E{S^2}/2\). By the renewal-reward theorem, \(R=\delta Z\), but \(\delta = \lambda\) by rate-stability. The claim follows now from PASTA.

Noting that

and substituting this in the expression for \(\E{S_{r}}\) we obtain from Eq. (5.4.1) the following result.

The Pollaczek-Khinchine equation can also be found as a limiting case of the waiting time of the \(M^{B}/M/1\) queue by interpreting a job in the \(M/G/1\) as a batch consisting of many tiny items in the \(M^{B}/M/1\) queue.⁴⁴ If you are not interested in math, you may skip the next derivation. Suppose that in the \(M^{B}/M/1\) queue the service times of the items are iid with mean \(1/\nu\). If \(F\) is the cdf of the service times of the \(M/G/1\) queue, then we take

as the probability that a batch has size \(k\) in an \(M^{B}/M/1\) queue. Note that in the \(M^{B}/M/1\) queue, when a batch has size \(k\), the service time is the sum of \(k\) rvs that are \(\Exp{\nu}\); thus, the service time of a batch of size \(k\) is \(\sim \Gamma{k, \nu}\). When \(\nu \gg 1\), the expected service time of a batch is

In words, when \(\nu\) is large, the batch expected service time in an \(M^{B}/M/1\) queue approximates the expected service time in an \(M/G/1\) queue.

In fact, the proof that the expected waiting time of the \(M^{B}/M/1\) converges to the Pollaczek-Khinchine equation when \(\nu\to \infty\) is based on the fact that every cdf \(F\), concentrated on \([0, \infty)\), can be approximated (weakly) by the sequence of cdfs⁵⁵ See Asmussen, Section III.4, Applied Probability and Queues, 2003.

That is, the distribution of the service time of a batch whose items have \(\Exp{\nu}\) service times approaches the cdf \(F\) of the service time of the \(M/G/1\) queue. Thus, when \(\nu\to\infty\) in Eq. (5.3.4), the mean and scv of the batch service time converge to \(\E S\) and \(C_{S}^{2}\) of the job, and the last term vanishes as it is proportional to \(1/\nu\). This leads to Eq. (5.4.2).

labda = 3.0 / 8
ES = 2
rho = labda * ES
ca2 = 1
cs2 = 1 / 2
EW = (ca2 + cs2) / 2 * rho / (1 - rho) * ES
print(f"{EW=}")

cs2 = 0
EW = (ca2 + cs2) / 2 * rho / (1 - rho) * ES
print(f"{EW=}")

ES = 1
rho = labda * ES
cs2 = 1 / 3
EW = (ca2 + cs2) / 2 * rho / (1 - rho) * ES
print(f"{EW=}")

EW=4.5
EW=3.0
EW=0.4