Staffing M/M/c Queues to Meet Service Targets

Staffing as a Discrete Search

Staffing an M/M/c queue is a constrained integer problem. A proposed server count must first be stable; among stable counts, it must meet the specified service target. Since server counts are integers, the answer is not obtained by solving a continuous equation and rounding. Instead, calculate the performance at successive eligible counts and verify that the first feasible one is minimal.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_t)_{t\ge0}\) be the continuous-time number of customers in an M/M/c queue, with state space \(S=\{0,1,2,\ldots\}\), arrival rate \(\lambda>0\), and service rate \(\mu>0\) for each of \(c\) servers. Arrivals are Poisson, service times are exponential, and the arrival and service mechanisms are independent. The natural filtration is \(\mathcal{F}_t=\sigma(X_s:0\le s\le t)\). Write \(a=\lambda/\mu\) for offered load. Stability requires \(c>a\), so the first eligible count is the smallest integer strictly greater than \(a\).

The generator \(Q=(q_{ij})\) has \(q_{n,n+1}=\lambda\) and, for \(n\ge1\), \(q_{n,n-1}=\min(n,c)\mu\); its diagonal entry is \(q_{nn}=-(\lambda+\min(n,c)\mu)\), with the service term zero when \(n=0\). Thus each generator row sums to zero: its off-diagonal rates sum to \(\lambda+\min(n,c)\mu\), exactly canceled by the diagonal. The stationary queue-length probabilities give the Erlang C waiting probability. For an eligible \(c\), define

Here \(C(c,a)\) is the probability an arriving customer must wait, also written \(\mathbb{P}(W_q>0)\), where \(W_q\) is that customer's time from arrival until service begins. For a stable M/M/c queue, the waiting-time tail and mean are

These Erlang C formulas apply to the stationary, stable M/M/c model; the exponential tail includes an atom at zero, since its value at \(t=0\) is \(C(c,a)\), not \(1\). The denominator \(c\mu-\lambda\) is the net service capacity in excess of the arrival rate.

Why Testing Counts in Order Finds the Minimum

The search begins at the first stable count, not at \(c=1\) unless that count is stable. The following result explains why checking eligible counts in increasing order is valid.

Proof. Fix an eligible \(c\). Since \(a<c\), both \(H_c(a)\) and \(R_c(a)\) are positive. Direct simplification gives \(H_c(a)=a^c/((c-1)!(c-a))\), so

The strict inequality follows because \(a<c\) and \(c+1-a>0\), and the ratio is positive. Therefore \(H_{c+1}/R_{c+1}<H_c/R_c\). Since \(C(c,a)=z/(1+z)\) for \(z=H_c(a)/R_c(a)>0\), and \(z/(1+z)\) increases with \(z\), \(C(c+1,a)<C(c,a)\). Also \(q_c=c\mu-\lambda>0\) increases strictly with \(c\). Hence \(C(c,a)/q_c\) decreases strictly, and \(C(c,a)e^{-q_ct}\) decreases strictly for every \(t\ge0\). Thus every feasible count has all larger eligible counts feasible, so the first passing count is minimal. To check eventual feasibility, \(R_c(a)\ge a^{c-1}/(c-1)!\), giving \(0<C(c,a)\le H_c(a)/R_c(a)\le a/(c-a)\), which tends to zero. Also \(q_c\) tends to infinity. These bounds imply that \(C(c,a)\), \(C(c,a)/q_c\), and \(C(c,a)e^{-q_ct}\) tend to zero. Therefore each of the stated positive-tolerance targets is eventually met. \(\square\)

In practice, one can use the following procedure. With several targets, test all of them at each candidate and stop only when all are met.

Worked Staffing Calculations

Interpreting the Answer and Avoiding Pitfalls

For a deadline target, the service-level probability is \(1-C(c,a)e^{-(c\mu-\lambda)t_d}\), not \(1-C(c,a)\) unless the deadline is zero. For a mean-wait target, divide by the net rate \(c\mu-\lambda\), not by \(c\mu\). Both errors can lead to under-staffing. Units also matter: if rates are per hour, a deadline entered in minutes must first be converted to hours.

The target boundaries determine whether a finite answer exists. For a stable finite \(c\), \(C(c,a)>0\) and \(c\mu-\lambda>0\), so the mean wait is positive and the deadline tail is positive at every finite deadline. Consequently, a zero waiting-probability target, a zero mean-wait target, or a deadline service level of exactly \(1\) cannot be met with finitely many servers when \(\lambda>0\). By contrast, any strictly positive tolerance for waiting probability or mean wait, and any deadline service level strictly below \(1\), can be met at some finite stable count, as shown in the theorem.

A common computational mistake is to check only that \(c\mu\) exceeds \(\lambda\), then round a continuous staffing estimate. Stability is necessary, but it does not verify a service target. The correction is to evaluate the Erlang C quantity at integer counts, starting with the first stable count, and explicitly check that the preceding eligible count fails. When several targets apply, the same count must satisfy all of them; satisfying a mean-wait target alone does not establish a deadline service level unless that deadline probability is also evaluated.