Asynchronous scheduling for energy optimality in systems with multiple servers

We consider energy-aware scheduling in a multi-server system with N classes of jobs. Jobs arrive randomly and are queued according to their class. Servers operate asynchronously over their own timelines. Each server can be in either the active state or the idle state. At the beginning of each active period, a server chooses a processing mode from a collection of options that affect: (i) which classes of jobs are served, (ii) the service times, and (iii) the energy incurred. After processing, the server chooses an amount of time to remain idle. The goal is to make decisions over time that minimize time average power subject to stabilizing all queues. This is related to a non-convex optimization problem with fractional terms that have different denominators in the objective function and in the constraints. Such problems are generally intractable. However, the system has physical properties with special structure. Exploiting these properties, we develop a novel online algorithm that solves the problem. The algorithm does not require knowledge of the arrival rates. It can push time average power arbitrarily close to optimal, with a corresponding tradeoff in average queue size.