Capacity and Blocking in the M/M/c/K Queue

Capacity Counts Everyone in the System

In an M/M/c queue with unlimited waiting space, an arrival can join the queue even when all servers are busy. A finite-capacity system changes that rule: once the system is full, a new arrival is not admitted. The notation M/M/c/K uses \(K\) for the maximum number of customers in the system, counting both those in service and those waiting. Thus capacity is not the maximum queue length.

Let \(c\ge1\) and \(K\ge c\) be integers, and let \(\lambda>0\) and \(\mu>0\). On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), consider a queue with Poisson arrivals of rate \(\lambda\), \(c\) identical servers, and independent exponential service times of rate \(\mu\). Arrivals finding \(K\) customers present are blocked and leave without service. Otherwise they join the system. Each server serves at most one customer at a time, and a customer who is admitted waits if all servers are busy. The occupancy process is \((N_t)_{t\ge0}\), where \(N_t\) is the number of customers in the system at time \(t\); use its natural filtration \((\mathcal{F}_t)_{t\ge0}\).

The first M indicates Poisson arrivals, the second M indicates exponential service times, \(c\) is the number of servers, and \(K\) is the total system capacity. The conventional M/M/c/K model takes \(K\ge c\), so all servers can be occupied before the system is full. At \(n<c\), only \(n\) servers are busy. At \(n\ge c\), all \(c\) servers are busy, and any additional admitted customers wait.

Deriving the Birth and Death Rates

For a continuous-time Markov chain, a rate \(q_{ij}\), with \(i\ne j\), describes the first-order probability of a transition from \(i\) to \(j\): over a short interval of length \(h\), that probability is \(q_{ij}h+o(h)\). Here births are increases in occupancy and deaths are decreases. The memoryless property of exponential service makes the remaining service time of each busy server exponential with rate \(\mu\), conditional on the current state and history. Thus, with \(n\) customers present, the total rate of a service completion is the sum of the rates of the busy servers.

Proof. Fix a state \(n\). If \(n<K\), an arrival occurs during a short interval of length \(h\) with probability \(\lambda h+o(h)\), and it changes the occupancy from \(n\) to \(n+1\). If \(n=K\), an arrival is blocked, so it does not change occupancy and gives no transition to a different state. There are \(\min(n,c)\) busy servers in state \(n\). Each completes service at rate \(\mu\), and the probability of two or more service completions in an interval of length \(h\) is \(o(h)\). Therefore the probability of a decrease by one is \(\min(n,c)\mu h+o(h)\). A single arrival or departure changes occupancy by exactly one, and simultaneous events have probability \(o(h)\). These facts give the stated rates and rule out other transitions between distinct states. The exponential memoryless property and independent arrivals and services ensure that these rates depend on the current occupancy, not on the past; hence the occupancy process is a continuous-time Markov chain. \(\square\)

The corresponding generator \(Q=(q_{ij})\) has off-diagonal entries equal to these transition rates. Its diagonal entry in each row is the negative sum of the off-diagonal entries in that row. In particular, at full capacity the diagonal is \(-c\mu\), not \(-(\lambda+c\mu)\): blocked arrivals do not change the state. This gives the complete generator rule below.

Proof. The off-diagonal rates are exactly the transitions identified in the proposition. In a continuous-time Markov chain, the diagonal entry is the negative total rate of leaving the state, so the sum of all entries in row \(n\) is zero. At \(n=0\), the only possible transition is a birth if \(K\ge1\); at \(n=K\), the only possible transition to a different state is a death. For \(0<n<K\), both a birth and a death are possible. This accounts for every state, including both boundaries, and proves the rule. \(\square\)

Build the Rates State by State

A reliable way to construct the model is to inspect each occupancy before writing a matrix. First list the states from \(0\) through \(K\). In state \(n\), count the busy servers as \(\min(n,c)\), giving departure rate \(\min(n,c)\mu\). Then include an arrival transition of rate \(\lambda\) only if \(n<K\). Finally, set the diagonal to the negative of the included rates. This procedure follows directly from the event rates and guarantees that the generator rows sum to zero.

Blocked Arrivals Are Not Birth Transitions

A blocked arrival is an event in the arrival stream, but it is not a transition of the occupancy process: immediately before and after that event, \(N_t=K\). The generator records changes of state, so it has no off-diagonal entry for a blocked arrival. This distinction matters when using the model to calculate probabilities or performance measures later. The event “an arrival finds the system full” is meaningful, but it is not represented by a jump from state \(K\) to state \(K+1\).

Common mistake. Suppose \(c=2\), \(K=3\), \(\lambda=4\), and \(\mu=1\). A mistaken calculation might assign a birth rate \(4\) out of state \(3\), and a departure rate \(3\) because three customers are present. That produces a supposed transition from \(3\) to \(4\), outside the allowed state space, and overcounts departures. The correct state \(3\) has two busy servers, so its departure rate is \(\min(3,2)\cdot1=2\); it is full, so its birth transition rate is \(0\). Its generator row has only \(q_{3,2}=2\) and \(q_{3,3}=-2\). The row check is \(2-2=0\). The arrival rate \(4\) still describes attempted arrivals, but these attempts do not change the occupancy at capacity.

Another frequent error is to use \(n\mu\) as the departure rate at every state. That is correct only while \(n\le c\). When \(n>c\), customers beyond the \(c\) busy servers are waiting, not receiving service, so the total departure rate remains \(c\mu\). Also keep the capacity convention explicit: \(K\) counts customers in service and in the queue together, so the largest possible queue length is \(K-c\) when \(K\ge c\).