Load sharing in heterogeneous queueing systems

Abstract

The problem of sharing jobs among a set of parallel queues is discussed. The system is heterogeneous in the sense that different servers may have different speeds. Socially optimal policies that minimize the mean response time of all jobs ar of interest. Using semi-Markov decision processes, it is shown that an optimal policy that uses the instantaneous queue length independent of system utilization does not exist. Rather, the optimal decision of assigning a job to a server depends on the workload intensity. At light loads, the optimal policy tends to assign most jobs to fast servers. At heavy loads, slower servers are used to offload fast ones. Simulation results indicate that a simple heuristic, i.e., a generalization of the optimal policy for homogeneous systems derived from the analytic results, yields substantial performance improvement compared with no load sharing and outperforms the join-shortest-queue policy.