Abstract
Power management aims in reducing the energy consumed by computer systems while maintaining a good level of performance. One of the mechanisms used to save energy is the shut-down mechanism which puts the system into a sleep state when it is idle. No energy is consumed in this state, but a fixed amount of energy is required for a transition from the sleep state to the active state which is equal to L times the energy required for the execution of a unit-time task. In this paper, we focus on the off-line version of this problem where a set of unit-time tasks with release dates and deadlines have to be scheduled in order to minimize the overall consumed energy during the idle periods of the schedule. Here we focus on the case where the tasks have agreeable deadlines. For the single processor case, an O(n 3) algorithm has been proposed in [7] for unit-time tasks and arbitrary L. We improve this result by introducing a new O(n 2) polynomial-time algorithm for tasks with arbitrary processing times and arbitrary L. For the multiprocessor case we also improve the complexity from O(n 3 m 2) [7] to O(n 2 m) in the case of unit-time tasks and unit L.
This work has been supported by the ANR project TODO (09-EMER-010) and the GDR RO du CNRS.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albers, S.: Energy-efficient algorithms. Communications of the ACM 53(5), 86–96 (2010)
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, pp. 364–367 (2006)
Baptiste, P., Chrobak, M., Dürr, C.: Polynomial Time Algorithms for Minimum Energy Scheduling. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 136–150. Springer, Heidelberg (2007)
Baptiste, P., Néron, E., Sourd, F.: Modèles et Algorithmes en Ordonnancement, pp. 198–203. Ellipses Edition (2004)
Chrétienne, P.: On the no-wait single-machine scheduling problem. In: Proc. 7th Workshop on Models and Algorithms for Planning and Scheduling Problems (2005)
Demaine, E.D., Ghodsi, M., Hajiaghayi, M.T., Sayedi-Roshkhar, A.S., Zadimoghaddam, M.: Scheduling to minimize gaps and power consumption. In: SPAA, pp. 46–54 (2007)
Gururaj, Jalan, Stein, unpublished work, see survey of M. Chrobak, http://www.cs.pitt.edu/~kirk/cs3150spring2010/10071.ChrobakMarek.Slides.pdf
Irani, S., Pruhs, K.R.: Algorithmic problems in power management. SIGACT News 36(2), 63–76 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Angel, E., Bampis, E., Chau, V. (2012). Low Complexity Scheduling Algorithm Minimizing the Energy for Tasks with Agreeable Deadlines. In: Fernández-Baca, D. (eds) LATIN 2012: Theoretical Informatics. LATIN 2012. Lecture Notes in Computer Science, vol 7256. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29344-3_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-29344-3_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29343-6
Online ISBN: 978-3-642-29344-3
eBook Packages: Computer ScienceComputer Science (R0)