Min-Energy Scheduling for Aligned Jobs in Accelerate Model

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)

5 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationAlgorithms and Computation
Subtitle of host publication20th International Symposium, ISAAC 2009, Proceedings
EditorsYingfei Dong, Ding-Zhu Du, Oscar Ibarra
PublisherSpringer Verlag
Pages462-472
ISBN (Print)3642106307, 9783642106309
Publication statusPublished - Dec 2009

Publication series

NameLecture Notes in Computer Science
Volume5878
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title20th Annual International Symposium on Algorithms and Computation (ISAAC 2009)
PlaceUnited States
CityHonolulu
Period16 - 18 December 2009

Abstract

Dynamic voltage scaling technique provides the capability for processors to adjust the speed and control the energy consumption. We study the pessimistic accelerate model where the acceleration rate of the processor speed is at most K and jobs cannot be executed during the speed transition period. The objective is to find a min-energy (optimal) schedule that finishes every job within its deadline. The job set we study in this paper is aligned jobs where earlier released jobs have earlier deadlines. We start by investigating a special case where all jobs have common arrival time and design an O(n2) algorithm to compute the optimal schedule based on some nice properties of the optimal schedule. Then, we study the general aligned jobs and obtain an O(n2) algorithm to compute the optimal schedule by using the algorithm for the common arrival time case as a building block. Because our algorithm relies on the computation of the optimal schedule in the ideal model (K=∞), in order to achieve O(n2) complexity, we improve the complexity of computing the optimal schedule in the ideal model for aligned jobs from the currently best known O(nlog n) to O(n2).

Citation Format(s)

Min-Energy Scheduling for Aligned Jobs in Accelerate Model. / Wu, Weiwei; Li, Minming; Chen, Enhong.

Algorithms and Computation: 20th International Symposium, ISAAC 2009, Proceedings. ed. / Yingfei Dong; Ding-Zhu Du; Oscar Ibarra. Springer Verlag, 2009. p. 462-472 (Lecture Notes in Computer Science; Vol. 5878).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)