Question

Consider a \(M / G / 1\) system with \(\lambda E[S]<1\). (a) Suppose that service is about to begin at a moment when there are \(n\) customers in the system. (i) Argue that the additional time until there are only \(n-1\) customers in the system has the same distribution as a busy period. (ii) What is the expected additional time until the system is empty? (b) Suppose that the work in the system at some moment is \(A\). We are interested in the expected additional time until the system is empty - call it \(E[T]\). Let \(N\) denote the number of arrivals during the first \(A\) units of time. (i) Compute \(E[T \mid N]\). (ii) Compute \(E[T]\).

Short answer

In summary, the expected additional time until the system is empty can be described as follows: (a) For an \(M/G/1\) system, the additional time until there are only \(n-1\) customers in the system has the same distribution as a busy period. The expected additional time until the system is empty is \(E[T] = \frac{E[S]}{1 - \lambda E[S]}\). (b) Given the work in the system at some moment is \(A\), we can compute the expected additional time until the system is empty as \(E[T \mid N] = A + \lambda A (\frac{E[S]}{2})\) and \(E[T] = E[A] + \lambda E[A] (\frac{E[S]}{2})\).

Step-by-step solution

Part (a) - Busy Period Distribution

(i) To argue that the additional time until there are only \(n-1\) customers in the system has the same distribution as a busy period, consider that when service begins, we have \(n\) customers in the system. In a busy period, we have a continuous period of time in which the system is never empty, followed by the arrival of a new customer just before the busy period ends. Additionally, as it is an \(M/G/1\) system, the arrival rate is Poisson and the service time follows a general distribution. Now, with the arrival of new customers during the service time of the current customer and the continuous service of other customers, the \(n-1\) customers remaining in the system still follow the same conditions as the busy period. Therefore, the additional time until there are only \(n-1\) customers in the system has the same distribution as a busy period.

Part (a) - Expected Additional Time

(ii) To find the expected additional time until the system is empty, we can use the definition of the expected busy period length \(E[B]\), which is given by: \(E[B] = \frac{E[S]}{1 - \lambda E[S]}\) Where, \(E[S]\) is the expected service time, and \(\lambda\) is the arrival rate. Since \(\lambda E[S]<1\), a busy period will eventually end. The expected additional time until the system is empty is equal to the expected busy period length: \(E[T] = E[B] = \frac{E[S]}{1 - \lambda E[S]}\)

Part (b) - Compute \(E[T \mid N]\)

(i) To compute \(E[T \mid N]\), we'll consider that the expected additional time until the system is empty depends on the number of arrivals during the first \(A\) units of time, so we have: \(E[T \mid N] = E[A] + E[\text{Remaining work}] \) Since the number of arrivals follows a Poisson process with parameter \(\lambda\), we have: \(E[N] = \lambda A\) The expected remaining work will be, with probability \((1-\lambda)\), the residual life of the service time: \(E[\text{Remaining work}] = \frac{E[S]}{2}\) Thus, we have: \(E[T \mid N] = A + \lambda A (\frac{E[S]}{2})\)

Part (b) - Compute \(E[T]\)

(ii) To compute \(E[T]\), we should find the expectation of the additional time until the system is empty by using the conditional expectation: \(E[T] = E[E[T \mid N]]\) We have already found \(E[T \mid N] = A + \lambda A (\frac{E[S]}{2})\). Now, let's find the expectation: \(E[T] = E[A] + \lambda E[A] (\frac{E[S]}{2})\) Since \(E[A]\) is given in the problem, the final formula for the expected additional time until the system is empty is: \(E[T] = E[A] + \lambda E[A] (\frac{E[S]}{2})\)