Optimal Offline Power-Down Scheduling
Brandon McPhail, UMass Amherst
Tuesday 12 May 2009, 4:00 p.m.
Room 140, Computer Science Building
Modern computing systems offer a wide variety of techniques for power management. Processor speed may be scaled down and subsystems may transition to low-power states to conserve energy. Developing algorithms to effectively manage these techniques can be challenging, and even simple optimization problems have proved difficult to solve or even approximate.
This talk considers the offline problem of scheduling a set of tasks with known processing times, release times, and deadlines on a single processor to minimize the number of idle gaps between periods of activity. Despite serious effort, it was not known whether the problem was NP-hard until 2005. I will present a dynamic programming algorithm by Baptiste et al. that places the problem in P.
Last modified 4 May 2009