NDLI: Polynomial-time algorithms for minimum energy scheduling

Please wait, while we are loading the content...

ACM Transactions on Algorithms (TALG) : Volume 13

ACM Transactions on Algorithms (TALG) : Volume 12

ACM Transactions on Algorithms (TALG) : Volume 11

ACM Transactions on Algorithms (TALG) : Volume 10

ACM Transactions on Algorithms (TALG) : Volume 9

ACM Transactions on Algorithms (TALG) : Volume 8

Issue 4, September 2012

Issue 3, July 2012

Assignment problem in content distribution networks: Unsplittable hard-capacitated facility location

Expansion properties of (secure) wireless networks

I/O-efficient shortest path algorithms for undirected graphs with random or bounded edge lengths

Improved algorithms for orienteering and related problems

Santa claus meets hypergraph matchings

The speed of convergence in congestion games under best-response dynamics

Polynomial-time algorithms for minimum energy scheduling

Tight approximation algorithms for scheduling with fixed jobs and nonavailability

Scalably scheduling processes with arbitrary speedup curves

Entropy, triangulation, and point location in planar subdivisions

Smoothed analysis of left-to-right maxima with applications

Counting occurrences for a finite set of words: Combinatorial methods

Testing nilpotence of galois groups in polynomial time

Issue 2, April 2012

Issue 1, January 2012

ACM Transactions on Algorithms (TALG) : Volume 7

ACM Transactions on Algorithms (TALG) : Volume 6

ACM Transactions on Algorithms (TALG) : Volume 5

ACM Transactions on Algorithms (TALG) : Volume 4

ACM Transactions on Algorithms (TALG) : Volume 3

ACM Transactions on Algorithms (TALG) : Volume 2

ACM Transactions on Algorithms (TALG) : Volume 1

Polynomial-time algorithms for minimum energy scheduling

Content Provider	ACM Digital Library
Author	Dürr, Christoph Chrobak, Marek Baptiste, Philippe
Copyright Year	2012
Abstract	The aim of power management policies is to reduce the amount of energy consumed by computer systems while maintaining a satisfactory level of performance. One common method for saving energy is to simply suspend the system during 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 article, 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 $\textit{L}$ to be woken up and, when it is on, it uses one unit of energy per one 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.
Starting Page	1
Ending Page	29
Page Count	29
File Format	PDF
ISSN	15496325
e-ISSN	15496333
DOI	10.1145/2229163.2229170
Volume Number	8
Issue Number	3
Journal	ACM Transactions on Algorithms (TALG)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-07-24
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Job scheduling Dynamic programming Minimizing energy consumption
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Variable voltage task scheduling algorithms for minimizing energy/power

Minimizing weighted flow time

Energy-Aware Scheduling of MapReduce Jobs for Big Data Applications

A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling

Polynomial time algorithms for minimum energy scheduling (908).

Heuristics for a scheduling problem of minimizing the number of one-way vehicles on paths with deadlines

Variable Voltage Task Scheduling for Minimizing Energy or Minimizing Power (2000)

Dürr C. Polynomial time algorithms for minimum energy scheduling

C.: polynomial time algorithms for minimum energy scheduling (2007).

Polynomial-time algorithms for minimum energy scheduling

Similar Documents

Variable voltage task scheduling algorithms for minimizing energy/power

Minimizing weighted flow time

Energy-Aware Scheduling of MapReduce Jobs for Big Data Applications

A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling

Polynomial time algorithms for minimum energy scheduling (908).

Heuristics for a scheduling problem of minimizing the number of one-way vehicles on paths with deadlines

Variable Voltage Task Scheduling for Minimizing Energy or Minimizing Power (2000)

Dürr C. Polynomial time algorithms for minimum energy scheduling

C.: polynomial time algorithms for minimum energy scheduling (2007).

Polynomial-time algorithms for minimum energy scheduling