Abstract
The aim of power management policies is to reduce the amount of energy consumed by computer systems while maintaining satisfactory level of performance. One common method for saving energy is to simply suspend the system during the idle times. No energy is consumed in the suspend mode. However, the process of waking up the system itself requires a certain fixed amount of energy, and thus suspending the system is beneficial only if the idle time is long enough to compensate for this additional energy expenditure. In the specific problem studied in the paper, we have a set of jobs with release times and deadlines that need to be executed on a single processor. Preemptions are allowed. The processor requires energy L to be woken up and, when it is on, it uses the energy at a rate of R units per unit of time. It has been an open problem whether a schedule minimizing the overall energy consumption can be computed in polynomial time. We solve this problem in positive, by providing an O(n 5)-time algorithm. In addition we provide an O(n 4)-time algorithm for computing the minimum energy schedule when all jobs have unit length.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Augustine, J., Irani, S., Swamy, C.: Optimal power-down strategies. In: Proc. 45th Symp. Foundations of Computer Science (FOCS 2004), pp. 530–539 (2004)
Baptiste, P.: Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management. In: Proc. 17th Annual ACM-SIAM symposium on Discrete Algorithms (SODA 2006), pp. 364–367 (2006)
Chretienne, P.: On the no-wait single-machine scheduling problem. In: Proc. 7th Workshop on Models and Algorithms for Planning and Scheduling Problems (2005)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H.Freeman and Co., New York (1979)
Irani, S., Gupta, R., Shukla, S.: Competitive analysis of dynamic power management strategies for systems with multiple power savings states. In: Proc. Conf. on Design, Automation and Test in Europe (DATE 2002), p. 117 (2002)
Irani, S., Shukla, S., Gupta, R.: Algorithms for power savings. In: SODA 2003. Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 37–46. ACM Press, New York (2003)
Irani, S., Shukla, S., Gupta, R.: Online strategies for dynamic power management in systems with multiple power-saving states. Trans. on Embedded Computing Sys. 2(3), 325–346 (2003)
Irani, S., Pruhs, K.R.: Algorithmic problems in power management. SIGACT News 36(2), 63–76 (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baptiste, P., Chrobak, M., Dürr, C. (2007). Polynomial Time Algorithms for Minimum Energy Scheduling. In: Arge, L., Hoffmann, M., Welzl, E. (eds) Algorithms – ESA 2007. ESA 2007. Lecture Notes in Computer Science, vol 4698. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75520-3_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-75520-3_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-75519-7
Online ISBN: 978-3-540-75520-3
eBook Packages: Computer ScienceComputer Science (R0)