This is from exercise 25, chapter 5, in Ross' Introduction to Probability Models, 11th ed. It goes as follows:

Customers can be served by any of three servers, where the service times of server $i$ are exponentially distributed with rate $μ_i$, $i = 1,2,3$. Whenever a server becomes free, the customer who has been waiting the longest begins service with that server.

(a) If you arrive to find all three servers busy and no one waiting, find the expected time until you depart the system.

Here's my solution, which agrees with other solutions I've seen:

Let $T$ denote your time in the system. Want $E[T]$. This is equal to $E[\min\{X_1,X_2,X_3\} + S]$, where $X_i$ is service time of server $i$, and $S$ your service time. We get

$E[\min\{X_1,X_2,X_3\} + S] = E[\min\{X_1,X_2,X_3\}] + E[S] = \frac{1}{\mu_1 + \mu_2 + \mu_3} + E[S]$.

To find $E[S]$, condition on which service time is shortest:

\begin{align*} E[S] = E[E[S|X_i \ \text{smallest}]] = \sum_i E[S|X_i \ \text{smallest}] P(X_i \ \text{smallest}) = E[S|X_1 \ \text{smallest}]P(X_1 \ \text{smallest}) + E[S|X_2 \ \text{smallest}]P(X_2 \ \text{smallest}) + E[S|X_3 \ \text{smallest}]P(X_3 \ \text{smallest}) = \frac{1}{\mu_1} \frac{\mu_1}{\mu_1+\mu_2+\mu_3} + \frac{1}{\mu_2} \frac{\mu_2}{\mu_1+\mu_2+\mu_3} + \frac{1}{\mu_3} \frac{\mu_3}{\mu_1 + \mu_2 + \mu_3} = \frac{3}{\mu_1 + \mu_2 + \mu_3} \end{align*}

I was just wondering, why doesn't $E[T]$ simply work out to be just: $$2\cdot E[\min\{X_1,X_2,X_3\}] = \frac{2}{\mu_1 + \mu_2 + \mu_3}\text{ ?}$$ I reason that when you enter the system, expected time to wait for a free server will be $E[\min\{X_1,X_2,X_3\}]$, and once you're being served, expected time to leave will be $E[\min\{X_1,X_2,X_3\}]$, since you're being served by the same server -- the server with the shortest service time. This would imply that $E[S] = E[\min\{X_1,X_2,X_3\}]$, so that $E[T] = 2 E[\min\{X_1,X_2,X_3\}]$.

  • $\begingroup$ What exactly do you mean with "..the server with the shortest service time.." in this context? $\endgroup$ – drhab Apr 13 at 9:09
  • $\begingroup$ @drhab By the server with the shortest service time I mean the server that is the fastest at finishing serving each customer that it serves, I think. But when you enter the line, the shortest service time should mean shortest remaining service time, I guess. I see now that replacing $X_i$ by $R_i$ in my solution, where $R_i$ denotes remaining service time of server $i$, agrees more closely with a related example in the book. But aren't these two things the same b.c. of memorylessness? $\endgroup$ – goblinb Apr 13 at 10:24
  • $\begingroup$ Yes, using memorylessness $(R_1,R_2,R_3)$ where $R_i$ is defined as remaining service time, have the same distribution as $(X_1,X_2,X_3)$. The server that is ready at first (shortest remaining service time) will be the one that serves you. This can be each of 3 distinct servers and this with a linked probability. This together determinex the expectation of $S$. But there is no reason to think that $S$ and $\min(X_1,X_2,X_3)=\min(R_1,R_2,R_3)$ have the same distribution. The server dealing with you will be the first or the second or the third. $\endgroup$ – drhab Apr 13 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.