  We analyze randomized dynamic load balancing schemes for multi-server
processor sharing systems when the number of servers in the system is large and
the servers have heterogeneous service rates. In particular, we focus on the
classical power-of-two load balancing scheme and a variant of it in which a
newly arrived job is assigned to the server having the least instantaneous
Lagrange shadow cost among two randomly chosen servers. The instantaneous
Lagrange shadow cost at a server is given by the ratio of the number of
unfinished jobs at the server to the capacity of the server. Two different
approaches of analysis are presented for each scheme. For exponential job
length distribution, the analysis is done using the mean field approach and for
more general job length distributions the analysis is carried out assuming an
asymptotic independence property. Analytical expressions to compute mean
sojourn time of jobs are found for both schemes. Asymptotic insensitivity of
the schemes to the type of job length distribution is established. Numerical
results are presented to validate the theoretical results and to show that,
unlike the homogeneous scenario, the power-of-two type schemes considered in
this paper may not always result in better behaviour in terms of the mean
sojourn time of jobs.
