Minimizing Response Times and Queue Lengths in Systems of Parallel Queues

We consider the problem of routing customers to one of two parallel queues. Arrivals are independent of the state of the system but otherwise arbitrary. Assuming that queues have infinite capacities and the service times form a sequence of i.i.d. random variables with Increasing Likelihood Ratio (ILR) distribution, we prove that the Shortest Queue (SQ) policy minimizes various cost functionals related to queue lengths and response times. We give a counterexample which shows that this result is not generally true when the service times have Increasing Hazard Rate but are not increasing in the likelihood rate sense. Finally, we show that when capacities are finite the SQ policy stochastically maximizes the departure process and minimizes the loss counting process. Keywords: Routing; stochastic majorization; response times; increasing likelihood ratio distributions AMS subject classification: 60K25 1 Introduction A classical problem in the literature of control of queues is the determin..