Energy Efficient Scheduling and Routing via Randomized Rounding

Evripidis Bampis 1 Alexander Kononov 2 Dimitrios Letsios 3 Giorgio Lucarelli 4, 5 Maxim Sviridenko 6
1 RO - Recherche Opérationnelle
LIP6 - Laboratoire d'Informatique de Paris 6
3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
5 DATAMOVE - Data Aware Large Scale Computing
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : We propose a unifying framework based on configuration linear programs and ran-domized 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-non-migratory 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-non-migratory 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.
Type de document :
Article dans une revue
Journal of Scheduling, Springer Verlag, 2018, 21 (1), pp.35-51. 〈10.1007/s10951-016-0500-2〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01725140
Contributeur : Lucarelli Giorgio <>
Soumis le : jeudi 8 mars 2018 - 10:55:59
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : samedi 9 juin 2018 - 13:00:45

Fichier

journal-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Evripidis Bampis, Alexander Kononov, Dimitrios Letsios, Giorgio Lucarelli, Maxim Sviridenko. Energy Efficient Scheduling and Routing via Randomized Rounding. Journal of Scheduling, Springer Verlag, 2018, 21 (1), pp.35-51. 〈10.1007/s10951-016-0500-2〉. 〈hal-01725140〉

Partager

Métriques

Consultations de la notice

409

Téléchargements de fichiers

52