An approximation to the response time for shortest queue routing

Abstract

In this paper we derive an approximation for the mean response time of a multiple queue system in which shortest queue routing is used. We assume there are Κ identical queues with infinite capacity and service times that are exponentially distributed. Arrivals of jobs to this system are Poisson and are routed to a queue of minimal length. We develop an approximation which is based on both theoretical and experimental considerations and, for Κ ≤ 8, has an relative error of less than one half of one percent when compared to simulation. For Κ = 16, the relative error is still acceptable, being less than 2 percent. An application to a model of parallel processing and a comparison of static and dynamic load balancing schemes are presented.