Dynamic speed scaling and load balancing of interconnected queues

We consider the problem of joint service rate control and load balancing of a network of servers. The system incurs holding cost, effort cost, and a routing cost whenever a demand is routed to other servers. This formulation is motivated by recent interest on energy efficiency in IT systems where effort cost models power consumption and holding cost represents performance in terms of delay. The aim is to find a stationary policy that minimizes, over an infinite horizon, the long-run average cost rate. Using a dynamic programming formulation, we show that the optimal routing policy is acyclic and bipartite. We prove that the relative cost function is monotonically non-decreasing in queue size while for the case of 2 servers, the optimal service policy is non-decreasing in queue size and the optimal routing policy is a threshold policy. We show how upper and lower bounds of the optimal average cost rate can be efficiently calculated numerically. In particular, based on the monotonicity property, we develop an approximate dynamic programming procedure to efficiently compute a good upper bound. Numerical examples with two networked servers are provided to illustrate our findings.