An efficient algorithm for computing optimal discrete voltage schedules

Minming Li; Frances F. Yao

doi:10.1007/11549345_56

An efficient algorithm for computing optimal discrete voltage schedules

Minming Li^*
, Frances F. Yao

^*Corresponding author for this work

Research output: Contribution to journal › Conference article › peer-review

4 Scopus citations

Abstract

We consider the problem of job scheduling on a variable voltage processor with d discrete voltage/speed levels. We give an algorithm which constructs a minimum energy schedule for n jobs in O(dn log n) time. Previous approaches solve this problem by first computing the optimal continuous solution in O(n³) time and then adjusting the speed to discrete levels. In our approach, the optimal discrete solution is characterized and computed directly from the inputs. We also show that O(n log n) time is required, hence the algorithm is optimal for fixed d.

Original language	English
Pages (from-to)	652-663
Number of pages	12
Journal	Lecture Notes in Computer Science
Volume	3618
DOIs	https://doi.org/10.1007/11549345_56
State	Published - 2005
Externally published	Yes
Event	30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 - Gdansk, Poland Duration: 29 Aug 2005 → 2 Sep 2005

Access to Document

10.1007/11549345_56

Cite this

@article{cfa21edc8e5d4a08b6f5d0fa2432fc4c,

title = "An efficient algorithm for computing optimal discrete voltage schedules",

abstract = "We consider the problem of job scheduling on a variable voltage processor with d discrete voltage/speed levels. We give an algorithm which constructs a minimum energy schedule for n jobs in O(dn log n) time. Previous approaches solve this problem by first computing the optimal continuous solution in O(n3) time and then adjusting the speed to discrete levels. In our approach, the optimal discrete solution is characterized and computed directly from the inputs. We also show that O(n log n) time is required, hence the algorithm is optimal for fixed d.",

author = "Minming Li and Yao, \{Frances F.\}",

year = "2005",

doi = "10.1007/11549345\_56",

language = "英语",

volume = "3618",

pages = "652--663",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

note = "30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 ; Conference date: 29-08-2005 Through 02-09-2005",

}

TY - JOUR

T1 - An efficient algorithm for computing optimal discrete voltage schedules

AU - Li, Minming

AU - Yao, Frances F.

PY - 2005

Y1 - 2005

N2 - We consider the problem of job scheduling on a variable voltage processor with d discrete voltage/speed levels. We give an algorithm which constructs a minimum energy schedule for n jobs in O(dn log n) time. Previous approaches solve this problem by first computing the optimal continuous solution in O(n3) time and then adjusting the speed to discrete levels. In our approach, the optimal discrete solution is characterized and computed directly from the inputs. We also show that O(n log n) time is required, hence the algorithm is optimal for fixed d.

AB - We consider the problem of job scheduling on a variable voltage processor with d discrete voltage/speed levels. We give an algorithm which constructs a minimum energy schedule for n jobs in O(dn log n) time. Previous approaches solve this problem by first computing the optimal continuous solution in O(n3) time and then adjusting the speed to discrete levels. In our approach, the optimal discrete solution is characterized and computed directly from the inputs. We also show that O(n log n) time is required, hence the algorithm is optimal for fixed d.

UR - https://www.scopus.com/pages/publications/26844482427

U2 - 10.1007/11549345_56

DO - 10.1007/11549345_56

M3 - 会议文章

AN - SCOPUS:26844482427

SN - 0302-9743

VL - 3618

SP - 652

EP - 663

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005

Y2 - 29 August 2005 through 2 September 2005

ER -

An efficient algorithm for computing optimal discrete voltage schedules

Abstract

Access to Document

Other files and links

Fingerprint

Cite this