5.1 The M(n)/M(n)/1 Queue

In this section, we specify appropriate functions for \(\lambda(n)\) and \(\mu(n)\) in (4.6.2), or \(\lambda^{+}(n)\) in (4.6.10) in case of blocking, for several of the queueing models discussed in Section 3.2. We emphasize that understanding how to specify the level-crossing equations is more important than deriving closed-form expressions for the performance measures.¹¹The code of Section 5.2 deals with the numerical aspects. Further, it is assumed that a system without blocking is stable.²²A system that blocks demand is stable anyway.

In the \(M(n)/M(n)/1\) queue the inter-arrival and service times are exponentially distributed conditional on \(L=n\), that is,

\begin{align*} X|L=n & \sim \Exp{\lambda(n)}, & S|L=n & \sim \Exp{\mu(n)}. \end{align*}

Somewhat more specifically, similar to (1.2.6), we require that³³In the general case, arrivals need not enter. We therefore consider \(\lambda^{+}\) rather than \(\lambda\).

\begin{align*} \P{\L(t+\Delta t) = n+1 \given \L(t) = n } & = \lambda^{+}(n) \Delta t + o(\Delta t), \quad n\geq 0, \\ \P{\L(t+\Delta t) = n-1 \given \L(t) = n } & = \mu(n) \Delta t + o(\Delta t), \quad n \geq 1. \end{align*}

Note that, when all arrivals are accepted⁴⁴In which case \(\lambda^{+}(n) = \lambda(n)\)., we write \(\lambda(n)\), but otherwise, we use \(\lambda^{+}(n)\). The next models are all examples of the \(M(n)/M(n)/1\) queue with different choices for \(\lambda(n)\) (or \(\lambda^{+}(n)\)) and \(\mu(n)\).

The \(M/M/1\) queue has a constant arrival and service rate, so

\begin{align*} \lambda(n) & = \lambda^{+}(n) = \lambda, & \mu(n) & =\mu. \end{align*}

The level-crossing equations (4.6.5) result in

\begin{equation*} p(n+1) = \frac{\lambda(n)}{\mu(n+1)} p(n) = \frac{\lambda}{\mu} p(n) = \rho p(n) = \rho^{n+1} p(0),\quad \rho = \frac{\lambda}{\mu}, \end{equation*}

and from (4.6.6),

\begin{equation*} p(0)^{-1} = \sum_{n=0}^{\infty} \rho^{n} = \frac{1}{1-\rho} \quad \implies\quad p(n) = (1-\rho)\rho^{n}, \quad n \geq 0. \tag{5.1.1} \end{equation*}

With this expression for \(p(n)\), it is easy to compute the key performance measures. The load equals the utilization since all jobs are accepted and served. With a bit of algebra,⁵⁵Exercise 8.

\begin{align*} \E \L & = \frac \rho{1-\rho}, & \E{\Ls} & = \rho, \tag{5.1.2} \\ \E \QQ & = \E \L - \E{\Ls} = \frac{\rho^2}{1-\rho}, & \P{\L> n} & = \rho^{n+1}. \tag{5.1.3} \end{align*}

The \(M/M/c\) queue has \(c\) identical servers to process jobs, thus

\begin{align*} \lambda(n) = \lambda^{+}(n) & = \lambda, & \mu(n) & = \mu \min\{n, c\}. \end{align*}

Closed-form expressions for \(\E \QQ\) and \(p(n)\) exist⁶⁶Exercise 9., but are not very informative. However, two measures are particularly simple. The load is \(\rho = \lambda/c\mu\), and

\begin{align*} \E{\Ls} & \stackrel1= \sum_{n=0}^{\infty}\min\{n,c\} p(n) \stackrel2= \frac{\lambda}\mu, \end{align*}

where 1 shows how to compute \(\E{\Ls}\) as an expectation, and 2 follows from Little’s law because jobs spend an average time \(\E S=1/\mu\) in service, and jobs arrive at a rate \(\lambda\) at the servers.⁷⁷Note that \(\E{\Ls} \neq \rho\).

The \(M/M/1/K\) queue blocks jobs when \(L\geq K\), hence⁸⁸Thus, \(\lambda(n) \neq \lambda^{+}(n)\).

\begin{align*} \lambda(n) &= \lambda, & \lambda^{+}(n) & = \lambda \1{n < K}, & \mu(n) & = \mu. \end{align*}

This gives \(\lambda p(n) = \mu p(n+1)\) for \(n<K\), and \(p(n) = 0\) for \(n>K\), because \(\lambda^{+}(n) = 0\) for \(n\geq K\). Thus, in general, \(\lambda^{+}(n) p(n) = \mu(n+1)p(n+1)\), from which follows that

\begin{align*} \rho & = \frac{\lambda}{\mu}, & p(n) & = \frac{1-\rho}{1-\rho^{K+1}} \rho^n. \end{align*}

There is a subtle point to make here. When the system contains \(K\) jobs, the rate at which jobs arrive at the system is \(\lambda (K) = \lambda\) because jobs still arrive as a Poisson process. However, the rate at which jobs enter is \(\lambda^{+}(K)= 0\), consequently,

\begin{equation*} \lambda \pi(K) = \lambda(K) p(K) \neq \lambda^{+}(K) p(K) = 0. \end{equation*}

Since \(\lambda(K) = \lambda\), we still have⁹⁹PASTA. \(\pi(K) = p(K)\), and therefore the fraction of jobs rejected upon arrival is equal to \(p(K)\). Note that because jobs are blocked, the utilization is no longer equal to the load \(\rho=\lambda/\mu\). Specifically, if we define the mean acceptance rate as

\begin{equation*} \lambda^{+} = \sum_{n=0}^{\infty} \lambda^{+}(n) p(n), \tag{5.1.4} \end{equation*}

we see for the \(M/M/1/K\) queue that \(\lambda^{+} = \lambda(1-p(K))\). With this, the utilization becomes

\begin{align*} \tilde \rho & = \lambda^{+}/\mu = \lambda (1-p(K))/\mu = \E\Ls, \tag{5.1.5} \end{align*}

where the last equation follows from Little’s law.

The \(M/M/c/K\) queue is a multi-server queue with blocking¹⁰¹⁰Hence, it combines the \(M/M/c\) and the \(M/M/1/K\) queue.,

\begin{align*} \lambda(n) &= \lambda, & \lambda^{+}(n) & = \lambda\1{n<K}, & \mu(n) & = \mu \min\{n, c\}. \end{align*}

The \(M/M/c/c\) queue¹¹¹¹Also known as the Erlang-\(B\) model. blocks jobs when all of its \(c\) servers are occupied,¹²¹²Why is it not necessary to write \(\mu(n) = \mu \min\{c, n\}\)?

\begin{align*} \lambda(n) &= \lambda, & \lambda^{+}(n) & = \lambda\1{n<c}, & \mu(n) & = n \mu. \end{align*}

When \(n<c\), \(\lambda p(n) = (n+1)\mu p(n+1)\), hence

\begin{align*} p(n+1) = \frac{\lambda}{(n+1)\mu }p(n) = \cdots = \frac{\lambda^{n+1}}{(n+1)!\mu^{n+1}} p(0). \end{align*}

The normalizing constant \(p(0)\) follows from the constraint \(1 = \sum_{n=0}^{c}p(n)\). As there are as many servers as jobs, \(\E \QQ = 0\). Moreover, jobs get accepted at a rate \(1-p(c)\), so that by PASTA,

\begin{align*} \E \L = \E \Ls = \frac{\lambda}{\mu} \left(1- p(c)\right). \end{align*}

The \(M/M/\infty\) queue assigns a free server to each arrival,¹³¹³This system is said to have ample servers.

\begin{align*} \lambda(n) &= \lambda^{+}(n) =\lambda, & \mu(n) & = n \mu. \end{align*}

By taking the limit \(c\to \infty\) in the expressions of the \(M/M/c/c\) queue¹⁴¹⁴Or the \(M/M/c\) queue. we obtain

\begin{align*} p(n) & = e^{-\lambda/\mu} \frac{(\lambda/\mu)^n}{n!}, & \E \QQ & =0, & \E \L = \E \Ls = \frac \lambda \mu. \end{align*}

We see that the number of busy servers in the \(M/M/\infty\) queue is Poisson distributed with parameter \(\lambda \E S\).

A finite calling population has a finite number \(N\) of jobs. This model is useful for analyzing repair systems and inventory systems of spare parts. To see this, consider a factory with \(N\) machines and \(c\) mechanics.¹⁵¹⁵When \(c=N\), we obtain the Ehrenfest model of diffusion, which is used to provide some insight into the second law of thermodynamics. A machine can be in one of two states: working or failed. When a machine breaks down, it waits at the repair department until repaired. When \(n\) machines are in repair, there are still \(N-n\) machines running. Thus, if \(\lambda\) is the rate at which an individual machine fails,

\begin{align*} \lambda(n) & = \lambda (N-n), & \mu(n) = \mu \min\{n, c\}, \end{align*}

A customer balks when finding the queue too long and deciding not to join. Balking differs from blocking. In the latter case, \(\lambda^{+}(n)= \lambda \1{n < K}\); in the former case, a fraction of the customers may already choose not to join the system at a lower level than \(K\). A simple model for balking is

\begin{align*} \lambda^{+}(n) & = \lambda [K-n]^{+}, & \mu(n) & =\mu. \end{align*}

In the remainder, we derive the KPIs of the above models.¹⁶¹⁶These exercises are optional, i.e, you may skip them if you don’t like algebra.