Problems

Consider $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / k$ with the constraint that arriving customers who see $N$ customers in the line ahead of them leave and never return. Find the stationary distribution of queue length for the cases $k = 1$ and $k = 2$.

Consider $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ with the constraint that if an arriving customer sees $n$ customers in the line ahead of him, he joins the queue with probability $p(n)$ and otherwise leaves in disgust.

In a Moscow supermarket customers queue at the cash desk to pay for the goods they want; then they proceed to a second line where they wait for the goods in question. If customers arrive in the shop like a Poisson process with parameter $\lambda$ and all service times are independent and exponentially distributed, parameter $\mu_{1}$ at the first desk and $\mu_{2}$ at the second, find the stationary distributions of queue lengths, when they exist, and show that, at any given time, the two queue lengths are independent in equilibrium.

Consider M/G/1, with the modification that the server may serve up to $m$ customers simultaneously. If the queue length is less than $m$ at the beginning of a service period then she serves everybody waiting at that time. Find a formula which is satisfied by the probability generating function of the stationary distribution of queue length at the times of departures, and evaluate this generating function explicitly in the case when $m = 2$ and service times are exponentially distributed.

Consider $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ where $\lambda < \mu$. Find the moment generating function of the length $B$ of a typical busy period, and show that $\mathbb {E}\left[B\right] = (\mu -\lambda )^{-1}$ and $\operatorname {Var}\left[B\right] = (\lambda +\mu ) /(\mu -\lambda )^{3}$. Show that the density function of $B$ is

where $I_{1}$ is a modified Bessel function.

Consider $\mathrm{M}(\lambda ) / \mathrm{G} / 1$ in equilibrium. Obtain an expression for the mean queue length at departure times. Show that the mean waiting time in equilibrium of an arriving customer is $\frac{1}{2} \lambda \mathbb {E}\left[S^{2}\right] /(1-\rho )$ where $S$ is a typical service time and $\rho = \lambda \mathbb {E}\left[S\right]$.

Amongst all possible service-time distributions with given mean, find the one for which the mean waiting time is a minimum.

Let $W_{t}$ be the time which a customer would have to wait in a $\mathrm{M}(\lambda ) / \mathrm{G} / 1$ queue if he were to arrive at time $t$. Show that the distribution function $F(x ; t) = \mathbb {P}\left(W_{t} \leq x\right)$ satisfies

where $S$ is a typical service time, independent of $W_{t}$. Suppose that $F(x, t) \rightarrow H(x)$ for all $x$ as $t \rightarrow \infty$, where $H$ is a distribution function satisfying $0 = h-\lambda H+\lambda \mathbb {P}\left(U+S \leq x\right)$ for $x > 0$, where $U$ is independent of $S$ with distribution function $H$, and $h$ is the density function of $H$ on $(0, \infty )$. Show that the moment generating function $M_{U}$ of $U$ satisfies

where $\rho$ is the traffic intensity. You may assume that $\mathbb {P}\left(S = 0\right) = 0$.

Consider a $\mathrm{G} / \mathrm{G} / 1$ queue in which the service times are constantly equal to $2$, whilst the interarrival times take either of the values 1 and 4 with equal probability $\frac{1}{2}$. Find the limiting waiting time distribution.

Consider an extremely idealized model of a telephone exchange having infinitely many channels available. Calls arrive in the manner of a Poisson process with intensity $\lambda$, and each requires one channel for a length of time having the exponential distribution with parameter $\mu$, independently of the arrival process and of the duration of other calls. Let $Q(t)$ be the number of calls being handled at time $t$, and suppose that $Q(0) = I$.

Determine the probability generating function of $Q(t)$, and deduce $\mathbb {E}\left[Q(t)\right], \mathbb {P}\left(Q(t) = 0\right)$, and the limiting distribution of $Q(t)$ as $t \rightarrow \infty$.

Assuming the queue is in equilibrium, find the proportion of time that no channels are occupied, and the mean length of an idle period. Deduce that the mean length of a busy period is $\left(e^{\lambda / \mu }-1\right) / \lambda$.

Customers arrive in a shop in the manner of a Poisson process with intensity $\lambda$, where $0 < \lambda < 1$. They are served one by one in the order of their arrival, and each requires a service time of unit length. Let $Q(t)$ be the number in the queue at time $t$. By comparing $Q(t)$ with $Q(t+1)$, determine the limiting distribution of $Q(t)$ as $t \rightarrow \infty$ (you may assume that the quantities in question converge). Hence show that the mean queue length in equilibrium is $\lambda \left(1-\frac{1}{2} \lambda \right) /(1-\lambda )$.

Let $W$ be the waiting time of a newly arrived customer when the queue is in equilibrium. Deduce from the results above that $\mathbb {E}\left[W\right] = \frac{1}{2} \lambda /(1-\lambda )$.

Consider $\mathrm{M}(\lambda ) / \mathrm{D}(1) / 1$, and suppose that the queue is empty at time 0. Let $T$ be the earliest time at which a customer departs leaving the queue empty. Show that the moment generating function $M_{T}$ of $T$ satisfies

and deduce the mean value of $T$, distinguishing between the cases $\lambda < 1$ and $\lambda \geq 1$.

Suppose $\lambda < \mu$, and consider a $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ queue $Q$ in equilibrium.

Consider the queue $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / k$, where $k \geq 1$. Show that a stationary distribution $\mathbf{\pi }$ exists if and only if $\lambda < k \mu$, and calculate it in this case.

Suppose that the cost of operating this system in equilibrium is

the positive constants $A$ and $B$ representing respectively the costs of employing a server and of the dissatisfaction of delayed customers.

Show that, for fixed $\mu$, there is a unique value $\lambda^{*}$ in the interval $(0, \mu )$ such that it is cheaper to have $k = 1$ than $k = 2$ if and only if $\lambda < \lambda^{*}$.

Customers arrive in a shop in the manner of a Poisson process with intensity $\lambda$. They form a single queue. There are two servers, labelled 1 and $2$, server $i$ requiring an exponentially distributed time with parameter $\mu_{i}$ to serve any given customer. The customer at the head of the queue is served by the first idle server; when both are idle, an arriving customer is equally likely to choose either.

Consider the $\mathrm{D}(1) / \mathrm{M}(\mu ) / 1$ queue where $\mu > 1$, and let $Q_{n}$ be the number of people in the queue just before the $n$th arrival. Let $Q_{\mu }$ be a random variable having as distribution the stationary distribution of the Markov chain $\left\{ Q_{n}\right\}$. Show that $\left(1-\mu^{-1}\right) Q_{\mu }$ converges in distribution as $\mu \downarrow 1$, the limit distribution being exponential with parameter 2.

Taxis arrive at a stand in the manner of a Poisson process with intensity $\tau$, and passengers arrive in the manner of an (independent) Poisson process with intensity $\pi$. If there are no waiting passengers, the taxis wait until passengers arrive, and then move off with the passengers, one to each taxi. If there is no taxi, passengers wait until they arrive. Suppose that initially there are neither taxis nor passengers at the stand. Show that the probability that $n$ passengers are waiting at time $t$ is $(\pi / \tau )^{\frac{1}{2} n} e^{-(\pi +\tau ) t} I_{n}(2 t \sqrt{\pi \tau })$, where $I_{n}(x)$ is the modified Bessel function, i.e. the coefficient of $z^{n}$ in the power series expansion of $\exp \left\{ \frac{1}{2} x\left(z+z^{-1}\right)\right\}$

Machines arrive for repair as a Poisson process with intensity $\lambda$. Each repair involves two stages, the $i$ th machine to arrive being under repair for a time $X_{i}+Y_{i}$, where the pairs $\left(X_{i}, Y_{i}\right), i = 1,2, \ldots$, are independent with a common joint distribution. Let $U(t)$ and $V(t)$ be the numbers of machines in the $X$-stage and $Y$-stage of repair at time $t$. Show that $U(t)$ and $V(t)$ are independent Poisson random variables.

An insurance company pays independent and identically distributed claims $\left\{ K_{n}: n \geq 1\right\}$ at the instants of a Poisson process with intensity $\lambda$, where $\lambda \mathbb {E}\left[K_{1}\right] < 1$. Premiums are received at constant rate 1. Show that the maximum deficit $M$ the company will ever accumulate has moment generating function

For an $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ queue with $\lambda < \mu$, when in equilibrium, show that the expected time until the queue is first empty is $\lambda (\mu -\lambda )^{-2}$.

Consider an $M(\lambda ) / G / \infty$ queue. Use the renewal-reward theorem to show that the expected duration of a busy period is $\left(e^{\rho }-1\right) / \lambda$ where $\rho = \lambda \mathbb {E}\left[S\right]$.