A discrete-time load balancing problem by neuro-dynamic programming algorithms

The meaning of load balancing is to dispatch jobs among resources of a system for maximizing the system performance. This paper deals with a discrete-time optimal load balancing problem that minimizes an expected total cost. This problem is formulated as an undiscounted Markov decision process, and is solved by the modified policy iteration method. Since the modified policy iteration method can not solve practical sized problems due to the curse of dimensionality, a near-optimal load balancing policy is computed by neuro-dynamic programming algorithms. We further compare this policy with heuristic policies such as the random policy, round-robin policy and shortest policy.