Choosing Service Capacity for a Delay Target

From a Delay Target to a Service Rate

In an M/M/1 queue, increasing the service rate reduces average delay, but the service rate must first be large enough for a stationary queue to exist. Choosing capacity for a delay target is therefore an inversion problem: start with the arrival rate and desired mean delay, then solve for the smallest service rate that meets the target. The answer depends on which delay is being controlled. Time in the system includes service; queueing delay does not.

Consider a queue on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_t)_{t\ge0}\) be the continuous-time process counting customers in the system, with state space \(S=\{0,1,2,\ldots\}\). Arrivals form a Poisson process of rate \(\lambda>0\), and each service time is exponential with rate \(\mu>0\). There is one server, an unlimited waiting room, and service is first-come, first-served. The natural filtration is \(\mathcal{F}_t=\sigma(X_s:0\le s\le t)\). A stationary M/M/1 queue requires \(\mu>\lambda\); set \(\rho=\lambda/\mu\) under this condition.

Let \(W\) denote the mean time from arrival until departure, and let \(W_q\) denote the mean time an arriving customer waits before service begins. The standard stationary M/M/1 formulas are

These formulas apply to a stable queue with \(\lambda>0\) and \(\mu>\lambda\). In terms of the stationary mean numbers \(L=\lambda/(\mu-\lambda)\) in the system and \(L_q=\lambda^2/(\mu(\mu-\lambda))\) in the queue, they follow by dividing each mean number by the arrival rate \(\lambda\) in Little's law. The service time is included in \(W\), but not in \(W_q\).

Minimum Rate for a Mean Time-in-System Target

Suppose the requirement is \(W\le T\), where \(T>0\) is the maximum permitted mean time in the system. The target is feasible with finite service rate: making \(\mu\) sufficiently large makes \(W\) sufficiently small. The inequality can be inverted directly because \(\mu-\lambda\) is positive in the stable range.

Proof. Assume \(\mu>\lambda\). By the mean time-in-system formula, the target is \(1/(\mu-\lambda)\le T\). Both \(T\) and \(\mu-\lambda\) are positive, so multiplying by \(\mu-\lambda\) and dividing by \(T\) preserves the inequality and gives \(1\le T(\mu-\lambda)\), or \(\mu\ge\lambda+1/T\). Conversely, if \(\mu\ge\lambda+1/T\), then \(\mu-\lambda\ge1/T>0\); taking reciprocals gives \(W=1/(\mu-\lambda)\le T\). Equality holds at \(\mu=\lambda+1/T\), while every smaller stable rate fails the target. This proves both the equivalence and minimality. \(\square\)

Minimum Rate for a Mean Queueing-Delay Target

A queueing-delay target asks for \(W_q\le D\), where \(D>0\). This is not the same inequality as a target on \(W\): the service time is excluded, and the rate appears in both factors of the denominator. Rearranging gives a quadratic in \(\mu\).

Proof. In the stable range \(\mu>\lambda\), the denominator \(\mu(\mu-\lambda)\) is positive. Therefore \(W_q\le D\) is equivalent to \(\lambda/[\mu(\mu-\lambda)]\le D\), which, after multiplication by the positive denominator, is equivalent to \(D\mu^2-D\lambda\mu-\lambda\ge0\). The corresponding equation has roots \(\bigl(\lambda\pm\sqrt{\lambda^2+4\lambda/D}\bigr)/2\), by the quadratic formula. Since \(\lambda>0\) and \(D>0\), \(\sqrt{\lambda^2+4\lambda/D}>\lambda\); the root with the minus sign is negative. The root with the plus sign, call it \(r\), is greater than \(\lambda\), because \(r-\lambda=(\sqrt{\lambda^2+4\lambda/D}-\lambda)/2>0\). Factoring the quadratic as \(D(\mu-r)(\mu-r_-)\), where \(r_-<0\) is the negative root, shows that for \(\mu>\lambda>0\) its value is nonnegative exactly when \(\mu\ge r\): the factor \(\mu-r_-\) is positive, so the sign is the sign of \(\mu-r\). Hence the target holds exactly for stable rates at least \(r\), and equality at \(r\) proves it is the minimum. \(\square\)

The queueing-delay expression also decreases strictly as \(\mu\) increases through the stable range. Indeed, if \(\mu_2>\mu_1>\lambda\), then \(\mu_2(\mu_2-\lambda)-\mu_1(\mu_1-\lambda)=(\mu_2-\mu_1)(\mu_2+\mu_1-\lambda)>0\). Thus the denominator grows while the numerator \(\lambda\) stays fixed. The root calculation gives the exact threshold; this monotonicity explains why rates above it continue to meet the target.

Meeting Two Targets at Once

Sometimes a service specification limits both the mean time in the system and the mean time waiting in the queue. Each target imposes its own lower bound on \(\mu\). Since both delays decrease with service rate in the stable range, meeting both targets requires meeting the more demanding of the two bounds.

To justify the combined rule, the first theorem says the system-time target holds exactly above its stated threshold, and the second says the queueing-delay target holds exactly above its threshold. Both hold precisely when \(\mu\) is at least each threshold, which is equivalent to being at least their maximum. Each threshold exceeds \(\lambda\), so the resulting choice is stable. At the maximum itself both inequalities hold, and any smaller rate violates at least the target whose threshold is larger.

Feasibility, Units, and a Common Mistake

The targets in these results must be strictly positive. With \(\lambda>0\), the mean queueing delay \(W_q=\lambda/[\mu(\mu-\lambda)]\) is positive for every finite stable \(\mu\), so a zero queueing-delay target cannot be met by any finite service rate. Likewise, \(W=1/(\mu-\lambda)>0\) for every finite stable \(\mu\), so a zero system-time target cannot be met. A positive target, by contrast, always has a finite rate threshold given above.

Keep units consistent: \(\lambda\) and \(\mu\) are rates, while \(T\) and \(D\) are times in the reciprocal unit. Thus \(1/T\) is a rate, and \(\lambda/D\) has units of rate squared, as required to add it to \(\lambda^2\) in the queueing-delay formula. Convert all quantities to a common time unit before applying either formula.

Common mistake: using the system-time formula for a queueing-delay target. For the values \(\lambda=2\) customers per minute and \(D=\tfrac14\) minute, incorrectly treating the target as \(W\le D\) gives \(\mu=2+1/(\tfrac14)=6\). That rate is stable, but it is not the minimum rate for the queueing-delay target: at \(\mu=4\), the actual queueing delay is already \(2/[4(4-2)]=\tfrac14\) minute. The system-time calculation answers a different question; at \(\mu=4\), total time is \(1/(4-2)=\tfrac12\) minute. Always choose the formula matching the stated delay.