Algorithms for power savings

This paper examines two different mechanisms for saving power in battery-operated embedded systems. The first is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. The second way in which power savings can be achieved is by varying the speed at which jobs are run. We utilize a power consumption curve P(s). which indicates the power consumption level given a particular speed. We assume that P(s) and P(s)/s are convex. The problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its arrival time and before its deadline. Although each problem has been considered separately, this is the first theoretical analysis of systems which can use both mechanisms. We give an off line algorithm which is within a factor of three of the optimal algorithm. We also give an online algorithm with a constant competitive ratio.