Scheduling unit tasks to minimize the number of idle periods

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management

Full text

Pdf (156 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm table of contents

Miami, Florida

Pages: 364 - 367

Year of Publication: 2006

ISBN:0-89871-605-5

Author

Philippe Baptiste

Laboratoire d'Informatique CNRS LIX, Palaiseau, Philippe

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
: SIAM Activity Group on Discrete Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 45, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1109557.1109598 What is a DOI?

ABSTRACT

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Philippe Baptiste, Scheduling equal-length jobs on identical parallel machines, Discrete Applied Mathematics, v.103 n.1-3, p.21-32, July 15, 2000 [doi>10.1016/S0166-218X(99)00238-3]
	2	Philippe Chretienne. On the no-wait single machine scheduling problem. In Proceeding of the 7th Conference on Models and Algorithms for Planning and Scheduling, pages 76--79, June 2005.
	3	Sandy Irani , Anna R. Karlin, Online computation, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	4	Sandy Irani , Kirk R. Pruhs, Algorithmic problems in power management, ACM SIGACT News, v.36 n.2, June 2005 [doi>10.1145/1067309.1067324]
	5	Sandy Irani, Sandeep Shukla, and Rajesh Gupta. Algorithms for power savings. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 37--46, 2003.

CITED BY 5

	Erik D. Demaine , Mohammad Ghodsi , Mohammad Taghi Hajiaghayi , Amin S. Sayedi-Roshkhar , Morteza Zadimoghaddam, Scheduling to minimize gaps and power consumption, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Jian-Jia Chen , Tei-Wei Kuo, Procrastination determination for periodic real-time tasks in leakage-aware dynamic voltage scaling systems, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Guy Even , Retsef Levi , Dror Rawitz , Baruch Schieber , Shimon (Moni) Shahar , Maxim Sviridenko, Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-17, June 2008
	Susanne Albers , Fabian Müller , Swen Schmelzer, Speed scaling on parallel processors, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Jian-Jia Chen , Tei-Wei Kuo, Procrastination for leakage-aware rate-monotonic scheduling on a dynamic voltage scaling processor, ACM SIGPLAN Notices, v.41 n.7, July 2006