  It is well-known that the power-of-d choices routing algorithm maximizes
throughput and is heavy-traffic optimal in load balancing systems with
homogeneous servers. However, if the servers are heterogeneous, throughput
optimality does not hold in general. We find necessary and sufficient
conditions for throughput optimality of power-of-d choices when the servers are
heterogeneous, and we prove that almost the same conditions are sufficient to
show heavy-traffic optimality. Additionally, we generalize the sufficient
condition for throughput optimality to a larger class of routing policies.
