Scheduling Unit Tasks to Minimize the Number of Idle Periods: A Polynomial Time Algorithm for Offline Dynamic Power Management

被引：58

作者：

Baptiste, Philippe ^{[1
]}

机构：

[1] Ecole Polytech, CNRS, LIX, Lab Informat, F-91128 Palaiseau, France

来源：

PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 2006年

关键词：

D O I：

10.1145/1109557.1109598

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：364 / 367

页数：4