Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management
Philippe Jean Baptiste · Symposium on Discrete Algorithms · 2006
Power Management policies aim at reducing the amount of energy consumed by battery operated systems, while keeping the overall performance high. In this paper we focus on shut-down mechanisms that put a system into a sleep state when it is idle. A very small amount of energy is consumed in this state but, a fixed amount of energy is required when moving the system from the sleep state to the active state. The offline version of this problem consists in scheduling a set of unit execution tasks, with release dates and deadlines, on a single machine in order to minimize the number of idle time periods. We show that this problem can be solved in polynomial time by Dynamic Programming.