The energy usage of computer systems is becoming an important consideration, especially for battery operated systems. Various methods for reducing energy consumption have been investigated, both at the circuit level and at the operating systems level. In this paper, we propose a simple model of job scheduling aimed at capturing some key aspects of energy minimization. In this model, each job is to be executed between its arrival time and deadline by a single processor with variable speed, under the assumption that energy usage per unit time, P, is a convex function of the processor speed s. We give an off-line algorithm that computes, for any set of jobs, a minimum-energy schedule. We then consider some on-line algorithms and their competitive performance for the power function P(s) = s p, where p is greater than or equal to 2. It is shown that one natural heuristic, called the Average Rate Heuristic, uses at most a constant times the minimum energy required. The analysis involves bounding the largest eigenvalue in matrices of a special type.
From: Frances Yao, Alan J. Demers, Scott Shenker: A Scheduling Model for Reduced CPU Energy. FOCS 1995 : 374-382.