Suppose there are two servers with exponential arrival rates $\mu_{1}$ and $\mu_2$ such that $\mu_1 > \mu_2$. These two servers have a shared infinite buffer, where there is independent Poisson arrival with rate $\lambda$. What is an optimal scheduling policy in these two sense :

  1. Throughput optimal that is it achieves the maximum capacity region.

  2. It reduces the mean time spent by a customers in the system.

I have a feeling that the greedy policy should be optimal, that is choose the faster server if it is free, otherwise choose the other one. Never keep the servers idle. I have no idea as to how one would prove optimality.

In the case of throughput optimality perhaps the greedy policy can stabilize an arrival rate of $\mu_1 + \mu_2$. Then it would be throughput optimal.

  • $\begingroup$ Suppose one server is so much faster that it can complete three jobs before the other finishes one. Wouldn't it make sense for small $\lambda$ to leave a single job in the queue even if the slow one is idle? $\endgroup$ Mar 19, 2015 at 20:22
  • $\begingroup$ yes you are right. I was thinking about that. But my question is whether we can derive an optimal policy, which will be dependent on the values of $\mu_1, \mu_2$ and $\lambda$. $\endgroup$
    – rajatsen91
    Mar 20, 2015 at 16:49
  • $\begingroup$ The answer is "yes," and this problem has been well-studied in the literature. Cf. kellogg.northwestern.edu/research/math/papers/592.pdf for the optimal policies where stalling of either server is allowed. $\endgroup$
    – Math1000
    Feb 23, 2016 at 21:29


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.