On the performance of greedy algorithms for energy minimization
Résumé
We revisit the well-known greedy algorithm for scheduling independent jobs on parallel processors, with the objective of energy minimization. We assess the performance of the online version, as well as the performance of the offine version, which sorts the jobs by non-increasing size before execution. We derive new approximation factors, as well as examples that show that these factors cannot be improved, thereby completely characterizing the performance of the algorithms.
Nous revisitons l'algorithme glouton bien connu d'ordonnancement de travaux indépendants sur des processeurs parallèles, avec un nouvel objectif de minimisation d'énergie. Nous étudions les performances de la version "online" et de la version "offline", cette dernière triant les travaux par ordre croissant de taille avant l'exécution. Nous donnons de nouveaux facteurs d'approximation, ainsi que des exemples qui montrent que ces facteurs ne peuvent pas être améliorés. Nous caractérisons donc complètement les performances de ces algorithmes.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...