Controlling and Assessing Correlations of Cost Matrices in Heterogeneous Scheduling

Abstract : This paper considers the problem of allocating independent tasks to unrelated machines such as to minimize the maximum completion time. Testing heuristics for this problem requires the generation of cost matrices that specify the execution time of each task on each machine. Numerous studies showed that the task and machine heterogeneities belong to the properties impacting heuristics performance the most. This study focuses on orthogonal properties, the average correlations between each pair of rows and each pair of columns, which is a proximity measure with uniform instances 1. Cost matrices generated with a novel generation method show the effect of these correlations on the performance of several heuristics from the literature. In particular, EFT performance depends on whether the tasks are more correlated than the machines and HLPT performs the best when both correlations are close to one.
Type de document :
Communication dans un congrès
Euro-par 2016 - 22nd International Conference on Parallel and Distributed Computing, Aug 2016, Grenoble, France
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01664639
Contributeur : Louis-Claude Canon <>
Soumis le : vendredi 15 décembre 2017 - 09:28:54
Dernière modification le : vendredi 20 avril 2018 - 15:44:27

Fichier

europar16.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01664639, version 1

Citation

Louis-Claude Canon, Pierre-Cyrille Heam, Laurent Philippe. Controlling and Assessing Correlations of Cost Matrices in Heterogeneous Scheduling. Euro-par 2016 - 22nd International Conference on Parallel and Distributed Computing, Aug 2016, Grenoble, France. 〈hal-01664639〉

Partager

Métriques

Consultations de la notice

78

Téléchargements de fichiers

18