BOUNDING THE MEAN RESPONSE-TIME OF THE MINIMUM EXPECTED DELAY ROUTINGPOLICY - AN ALGORITHMIC APPROACH

Balancing loads in a multi-server system can have a significant impact on performance. In this paper, we model such a system as a heterogene ous multi-server queueing system. We study the behavior of such a syst em operating under the minimum expected delay (MED) routing policy, i. e., an arriving customer is assigned to the queue which has the minima l expected value of unfinished work. This routing discipline can be vi ewed as a generalization of the join-the-shortest queue (SQ) disciplin e for homogeneous servers, There is no closed-form solution for this c lass of queueing problem, In this paper, we provide a methodology to c ompute upper and lower bounds on the mean response time of the system. This methodology allows one to tradeoff the tightness of the bounds a nd computational cost. Applications and numerical examples are present ed which show how to use this methodology for deriving performance mea sures and also illustrating that the excellent accuracy of the computa tional algorithm which is achievable with modest computational cost.