Journal
JOURNAL OF SCHEDULING
Volume 16, Issue 4, Pages 385-394Publisher
SPRINGER
DOI: 10.1007/s10951-013-0312-6
Keywords
Energy-efficient scheduling; Approximation algorithms; Non-preemption
Ask authors/readers for more resources
We consider the following offline variant of the speed scaling problem introduced by Yao et al. 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. In contrast to Yao et al., 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 -norm objective.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available