Paper Info
Title
Non-preemptive speed scaling
Abstract
We consider the following variant of the speed scaling problem introduced by Yao, Demers, and Shenker. We are given a set of jobs and we have a variable-speed processor to process them. The higher the processor speed, the higher the energy consumption. Each job is associated with its own release time, deadline, and processing volume. The objective is to find a feasible schedule that minimizes the energy consumption. Moreover, no preemption of jobs is allowed. Unlike the preemptive version that is known to be in P, the non-preemptive version of speed scaling is strongly NP-hard. In this work, we present a constant factor approximation algorithm for it. The main technical idea is to transform the problem into the unrelated machine scheduling problem with Lp-norm objective.
Year
DOI
Venue
2013
10.1007/s10951-013-0312-6
Journal of Scheduling
Keywords
DocType
Volume
Energy-efficient scheduling,Approximation algorithms,Non-preemption
Journal
16
Issue
ISSN
Citations 
4
1094-6136
11
PageRank 
References 
Authors
0.57
16
2
Name
Order
Citations
PageRank
Antonios Antoniadis112713.81
Chien-Chung Huang2110.57