Consider a machine where jobs arrive according to a Poisson stream with a rate of 4 jobs per hour. Half of the jobs have a processing time of exactly 10 minutes, a quarter have a processing time of exactly 15 minutes and the remaining quarter have a processing time of 20 minutes. The jobs with a processing time of 10 minutes are called type 1 jobs, the ones with a processing time of 15 minutes type 2 jobs and the rest type 3 jobs. The jobs are processed in order of arrival.

The first question about this queueing system is the following: determine the mean sojourn time (waiting time plus processing time) of a type 1, 2 and 3 job and also of an arbitrary job.

I first tried to calculate the mean sojourn time for an arbitrary job. The arrival rate is $ \lambda = 4 / \text{hour} = \frac{1}{15} / \text{minute} $. Furthermore, for the processing rate $\mu$ we have $ \frac{1}{\mu} = \frac{1}{2} \cdot 10 + \frac{1}{4} \cdot 15 + \frac{1}{4} \cdot 20 = \frac{55}{4} \text{minutes}$. So the processing time is $\frac{1}{\mu} = E(B) = \frac{4}{55}$. We can now also calculate the probability $\rho$ that the server is busy on arrival: $\rho = \frac{\lambda}{\mu} = \frac{11}{12}$.

So far, everything is correct (according to the answer sheet). However, something goes wrong in the following (again, according to the solution manual).

To calculate the waiting time, we can use the following formula (which holds for M/G/1 queues, so also for our case: M/D/1 queues (where D stands for "deterministic")) : $$ E(W) = \frac{\rho E(R)}{1-\rho} \quad . $$
Here, R denotes the residual service time. We also know that $E(R) = \frac{E(B^{2})}{2E(B)}$.

We know that $ Var(B) = E(B^{2}) - E(B)^{2}$, so $E(B^{2}) = Var(B) + E(B)^{2}$. I thought that, since the processing times are deterministic, the variance is always zero. So we have $E(B^{2}) = E(B)^{2} $, which implies that $E(R) = \frac{(55/4)^{2}}{2\cdot (55/4)} = \frac{55}{8} $.

According to the solutions manual, however, $E(R) = 15/2$. So I've probably done something wrong. Do you know who's wrong, the answer sheet or me? If it's me (which, again, is probably the case), do you know what I've done wrong?

  • $\begingroup$ I think "a quarter of the jobs have a processing time of exactly $10$ minutes" shouldn't be there? $\endgroup$ – joriki May 26 '16 at 12:52
  • $\begingroup$ @joriki Ah yes, you're right, thank you. My mistake. $\endgroup$ – Max Muller May 26 '16 at 13:02

The processing times are deterministic for each type, but you're talking about arbitrary jobs, and different types of job have different processing times, so you need to calculate $E(B^2)$ just like you calculated $E(B)$:

$$E(B^2)=\frac{1}{2} \cdot 10^2 + \frac{1}{4} \cdot 15^2 + \frac{1}{4} \cdot 20^2\;.$$

That makes the answer come out right.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.