Skip to main navigation Skip to search Skip to main content

Min-Energy Scheduling for Aligned Jobs in Accelerate Model

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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(n2 log n) to O(n2).
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
DOIs
Publication statusPublished - Dec 2009
Event20th Annual International Symposium on Algorithms and Computation (ISAAC 2009) - Honolulu, United States
Duration: 16 Dec 2009 → 18 Dec 2009
https://theory.utdallas.edu/ISAAC2009/

Publication series

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

Conference

Conference20th Annual International Symposium on Algorithms and Computation (ISAAC 2009)
PlaceUnited States
CityHonolulu
Period16/12/09 → 18/12/09
Internet address

Fingerprint

Dive into the research topics of 'Min-Energy Scheduling for Aligned Jobs in Accelerate Model'. Together they form a unique fingerprint.

Cite this