1
$\begingroup$

My teacher says that it does not depend on the discipline when we have M/G/1 (we did not learn others like G/G/k). I found this statement only for M/M/1 (here[page 8] and here). But I doubt it, even if this is true only for M/M/1.

Consider FIFO and SF. When the number of customers in the queue is $0$ or $1$ then the service order is the same. So consider situations when the number of customers in the queue more than $1$.

The time from the arrival of a customer who now is in the queue until the time at which we consider the queue does not depend on the discipline, denote it $t_{Ai}$ (i.e. it is the time that the customer has already been in the system). Also denote the service time of each customer as $t_{Si}$ and the time in the system as $t_{SMi}$.

Suppose this situation: $t_{S1} = 7, t_{S2} = 10, t_{S3} = 5$. With FIFO, the service will take place in this order:

$t_{SM1} = 7 + t_{A1}$

$t_{SM2} = 7 + 10 + t_{A2} = 17 + t_{A2}$

$t_{SM3} = 17 + 5 + t_{A3} = 22 + t_{A3}$

Then average $\overline {t_{SM}} ≈ 15,3 + \frac{(t_{A1} + t_{A2} + t_{A3})}{3}$

With SF:

$t_{SM3} = 5 + t_{A3}$,

$t_{SM1} = 5 + 7 + t_{A1} = 12 + t_{A1}$,

$t_{SM2} = 12 + 10 + t_{A2} = 22 + t_{A2}$,

$\overline {t_{SM}} = 13 + \frac{(t_{A1} + t_{A2} + t_{A3})}{3}$

You can take any $t_{Si}$, the average time in the system with SF will always be less than or equal to (in the case when $t_{Si}$ consistently increase) the average time in the system with FIFO.

When we take into account all these situations, it turns out that the average time in the system in the case of SF will be less than in the case of FIFO. Now, when I explained my doubts, one more question arises: if the average time in the system does not depend on the discipline, then where am I mistaken?

P.S. I could also show that when we have constant service time (M/G/1) then the average time in system with FIFO and RR is also different (with RR it's bigger), that's why I started to doubt, but the question is already too big.

$\endgroup$

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.