Energy-efficient scheduling and routing via randomized rounding

Evripidis Bampis (), Alexander Kononov (), Dimitrios Letsios (), Giorgio Lucarelli () and Maxim Sviridenko ()
Additional contact information
Evripidis Bampis: Sorbonne Universités, UPMC Univ Paris 06
Alexander Kononov: Sobolev Institute of Mathematics
Dimitrios Letsios: Sorbonne Universités, UPMC Univ Paris 06
Giorgio Lucarelli: Sorbonne Universités, UPMC Univ Paris 06
Maxim Sviridenko: Yahoo Labs

Journal of Scheduling, 2018, vol. 21, issue 1, No 4, 35-51

Abstract: Abstract We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed scalable processors in a fully heterogeneous setting. For both the preemptive-nonmigratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-nonmigratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem.

Keywords: Randomized rounding; Scheduling; Approximation; Energy-aware; Configuration linear program (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-016-0500-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:21:y:2018:i:1:d:10.1007_s10951-016-0500-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-016-0500-2

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().