Turning Queueing Targets into a Design
A finite queue limits how many customers can be present, so an arrival may be turned away when the system is full. Capacity planning must therefore consider more than waiting time: adding capacity can reduce blocking, while adding servers can also reduce queueing delay. The useful design question is whether a particular pair of server count and total capacity meets all specified targets at once.
Consider an M/M/c/K queue with Poisson arrival rate \(\lambda>0\), \(c\ge1\) identical servers, exponential service times with rate \(\mu>0\) per server, and total system capacity \(K\ge c\). Arrivals finding \(K\) customers are blocked; otherwise they join the system. Let \((X_t)_{t\ge0}\) be the continuous-time Markov chain on state space \(S=\{0,1,\ldots,K\}\), where \(X_t\) is the number of customers present, on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Define \(\rho=\lambda/\mu\). The state-dependent total service rate in state \(n\) is \(d_n=\min(n,c)\mu\), with \(d_0=0\).
Here is the stationary distribution used to compare designs. Its weights are \(a_0=1\), \(a_n=\rho^n/n!\) for \(1\le n\le c\), and \(a_n=(\rho^c/c!)(\lambda/(c\mu))^{n-c}\) for \(c<n\le K\). Normalize with \(Z=\sum_{n=0}^{K}a_n\), so \(\pi_n=a_n/Z\). In particular, the blocking probability is \(\pi_K\). Since Poisson arrivals see time averages (PASTA), an arrival sees the stationary full-state probability \(\pi_K\); PASTA is a standard result whose proof is not needed for these calculations. Thus accepted throughput is \(X=\lambda(1-\pi_K)\). The queueing quantities follow from \(L=\sum_{n=0}^K n\pi_n\), \(L_q=\sum_{n=c+1}^K(n-c)\pi_n\), and Little’s law \(W_q=L_q/X\) for accepted customers.
Proof. In state \(n<K\), the transition rate upward is \(\lambda\); in state \(n>0\), the rate downward is \(d_n=\min(n,c)\mu\). The weights satisfy \(a_n\lambda=a_{n+1}d_{n+1}\) for each \(0\le n<K\): for \(n<c\), the ratio \(a_{n+1}/a_n=\rho/(n+1)=\lambda/((n+1)\mu)\); for \(n\ge c\), the ratio is \(\lambda/(c\mu)\). Divide these identities by \(Z\) to obtain \(\pi_n\lambda=\pi_{n+1}d_{n+1}\). At state 0, the probability flow out, \(\pi_0\lambda\), equals the flow in, \(\pi_1d_1\). At any interior state \(n\), the flow in is \(\pi_{n-1}\lambda+\pi_{n+1}d_{n+1}\), which equals \(\pi_nd_n+\pi_n\lambda\), the flow out. At state \(K\), the flow in \(\pi_{K-1}\lambda\) equals the flow out \(\pi_Kd_K\). These balance equations prove that the normalized weights are stationary. To see uniqueness, let \(\nu\) be any stationary distribution and write the balance equation at state 0 as \(\nu_0\lambda=\nu_1d_1\). The balance equation at state 1 then forces \(\nu_1\lambda=\nu_2d_2\); successively, the equation at each state forces \(\nu_n\lambda=\nu_{n+1}d_{n+1}\). Since all rates in these identities are positive, these relations determine every \(\nu_n\) from \(\nu_0\), and \(\sum_n\nu_n=1\) determines \(\nu_0\). Therefore \(\nu=\pi\). \(\square\)
The practical method is to enumerate feasible integer pairs \((c,K)\), calculate and normalize their weights, and then check each performance measure against its target. A finite queue has no stability restriction of the kind required for an infinite-capacity queue, but its targets may still rule out a candidate. Do not assume that every measure improves when capacity changes: more places to wait can lower blocking while increasing occupancy and delay.
Worked Example: Find a Design That Meets Four Targets
Let \(\lambda=2\) and \(\mu=1\). Require blocking probability at most \(1/4\), throughput at least \(3/2\), mean queueing delay at most \(1/4\), and mean occupancy at most \(8/5\). Compare designs \((c,K)=(2,3),(2,4),(3,3)\).
For \((2,3)\), the generator, with states in order \(0,1,2,3\), is
Each row sums to zero: \(-2+2=0\), \(1-3+2=0\), \(2-4+2=0\), and \(2-2=0\). Here \(\rho=2\), and the unnormalized weights are \((1,2,2,2)\), whose sum is \(7\). Thus \(\pi=(1,2,2,2)/7\), so blocking is \(2/7\), which exceeds \(1/4\). Throughput is \(2(1-2/7)=10/7\). Mean occupancy is \((2+4+6)/7=12/7\); mean queue length is \(2/7\), because only state 3 has a waiting customer. Therefore \(W_q=(2/7)/(10/7)=1/5\). This design misses the blocking, throughput, and occupancy targets.
For \((2,4)\), the weights are \((1,2,2,2,2)\), with sum \(9\). The generator has upward rates \(2\) below state 4 and downward rates \(1,2,2,2\) in states 1 through 4. Its successive row sums are \(-2+2=0\), \(1-3+2=0\), \(2-4+2=0\), \(2-4+2=0\), and \(2-2=0\). The blocking probability is \(2/9\), and throughput is \(2(1-2/9)=14/9\); both meet their targets. Mean occupancy is \((2+4+6+8)/9=20/9\), while \(L_q=(2+4)/9=2/3\). Consequently \(W_q=(2/3)/(14/9)=3/7\). This design fails the delay and occupancy targets.
For \((3,3)\), the weights are \((1,2,2,4/3)\), with sum \(19/3\). Its generator has rows \((-2,2,0,0)\), \((1,-3,2,0)\), \((0,2,-4,2)\), and \((0,0,3,-3)\); their sums are respectively \(-2+2=0\), \(1-3+2=0\), \(2-4+2=0\), and \(3-3=0\). The blocking probability is \((4/3)/(19/3)=4/19<1/4\). Throughput is \(2(1-4/19)=30/19>3/2\). Mean occupancy is \((2+4+4)/(19/3)=30/19<8/5\), since \(150<152\). There is no queue when \(K=c=3\), so \(L_q=0\) and \(W_q=0\). This design meets all four targets. The calculations also show why a design should be judged against the full set of requirements, not blocking alone.
Worked Example: The Smallest Capacity That Meets a Blocking Target
Let \(\lambda=3\), \(\mu=2\), and \(c=2\). Find the smallest capacity \(K\ge2\) giving blocking probability at most \(1/5\), and report its throughput, occupancy, and delay.
For \(K=2\), the weights are \((1,3/2,9/8)\), summing to \(29/8\). Thus \(\pi_2=9/29>1/5\), since \(45>29\), so capacity 2 fails. For \(K=3\), the weights are \((1,3/2,9/8,27/32)\), summing to \(143/32\). The generator rows are \((-3,3,0,0)\), \((2,-5,3,0)\), \((0,4,-7,3)\), and \((0,0,4,-4)\); each sums to zero: \(-3+3=0\), \(2-5+3=0\), \(4-7+3=0\), and \(4-4=0\).
At capacity 3, \(\pi_3=27/143<1/5\), because \(135<143\). Therefore \(K=3\) is the smallest feasible capacity. Throughput is \(3(1-27/143)=348/143\). Mean occupancy is \((48+72+81)/143=201/143\), using the state-weighted probabilities. The only state with a queue is state 3, so \(L_q=27/143\), and \(W_q=(27/143)/(348/143)=27/348=9/116\). As a check, the unnormalized probabilities sum to \((32+48+36+27)/32=143/32\), and the calculated blocking probability is precisely the full-state probability.
Worked Example: Adding Servers at Fixed Total Capacity
Let \(\lambda=4\), \(\mu=2\), and \(K=3\). Require blocking probability at most \(1/4\) and mean queueing delay at most \(1/8\). Compare \(c=1,2,3\), retaining \(K=3\) in every design.
For each candidate, the generator rows sum to zero. For \(c=1\), the rows are \((-4,4,0,0)\), \((2,-6,4,0)\), \((0,2,-6,4)\), and \((0,0,2,-2)\); their sums are \(-4+4=0\), \(2-6+4=0\), \(2-6+4=0\), and \(2-2=0\). With \(\rho=2\), the weights are \((1,2,4,8)\), summing to \(15\). Hence blocking is \(8/15\), throughput is \(4(7/15)=28/15\), and \(L=(2+8+24)/15=34/15\). The queue-length numerator is \(4+2(8)=20\), so \(L_q=4/3\) and \(W_q=(4/3)/(28/15)=5/7\). This candidate fails both targets.
For \(c=2\), the generator rows are \((-4,4,0,0)\), \((2,-6,4,0)\), \((0,4,-8,4)\), and \((0,0,4,-4)\); their sums are \(-4+4=0\), \(2-6+4=0\), \(4-8+4=0\), and \(4-4=0\). The weights are \((1,2,2,2)\), summing to \(7\). Blocking is \(2/7>1/4\), throughput is \(20/7\), and \(L=(2+4+6)/7=12/7\). Also \(L_q=2/7\), giving \(W_q=(2/7)/(20/7)=1/10<1/8\). The delay target is met, but the blocking target is not.
For \(c=3\), the rows are \((-4,4,0,0)\), \((2,-6,4,0)\), \((0,4,-8,4)\), and \((0,0,6,-6)\). Their sums are \(-4+4=0\), \(2-6+4=0\), \(4-8+4=0\), and \(6-6=0\). The weights are \((1,2,2,4/3)\), summing to \(19/3\). Blocking is \(4/19<1/4\), and throughput is \(4(15/19)=60/19\). Mean occupancy is \(30/19\), but \(L_q=0\), so \(W_q=0\). This is the only candidate meeting both targets.
Checking the Design Logic
Every candidate calculation has a short verification: the weights must sum to the stated normalizer, the probabilities must sum to 1, and blocking plus the fraction accepted must equal 1. The generator rows must sum to zero because the diagonal entry is minus the total rate of leaving that state. These checks catch many arithmetic and modeling errors before comparing targets.
Common mistake. In the first example, it would be wrong to report throughput \(2\), the offered arrival rate, for the \((c,K)=(2,4)\) design. Some arrivals are blocked, so the correct calculation is \(X=2(1-2/9)=14/9\). It would also be wrong to use \(L/X=(20/9)/(14/9)=10/7\) as queueing delay: \(L\) counts customers in service as well as customers waiting. Queueing delay uses \(L_q\), giving \(W_q=(2/3)/(14/9)=3/7\). Keep the measures aligned with their definitions: blocking uses \(\pi_K\), throughput counts accepted arrivals, and queueing delay uses the mean number waiting.
| Planning quantity | Calculation | Interpretation |
|---|---|---|
| Blocking probability | \(\pi_K\) | Fraction of arrivals finding the system full |
| Accepted throughput | \(\lambda(1-\pi_K)\) | Rate at which customers enter |
| Mean occupancy | \(\sum_{n=0}^K n\pi_n\) | Customers waiting and in service |
| Mean queue length | \(\sum_{n=c+1}^K(n-c)\pi_n\) | Customers waiting, excluding service |
| Mean queueing delay | \(L_q/[\lambda(1-\pi_K)]\) | Mean wait before service for accepted customers |
Check Your Understanding
For each question, state any candidate assumptions and verify numerical answers by substitution.
- For \(\lambda=2\), \(\mu=1\), \(c=2\), and \(K=4\), write the stationary weights and calculate the blocking probability.
- Why is the accepted throughput not generally equal to the offered arrival rate \(\lambda\) in a finite-capacity queue?
- For the \(\lambda=3,\mu=2,c=2,K=3\) design, verify that the blocking probability is less than \(1/5\) and calculate \(W_q\).
- At fixed capacity \(K=3\), explain why the \(c=2\) design in the last example meets the delay target but not the blocking target.
- Explain why \(L_q/X\), rather than \(L/X\), gives mean queueing delay for accepted customers.