On the Heterogeneity Bias of Cost Matrices for Assessing Scheduling Algorithms

Abstract : Assessing the performance of scheduling heuristics through simulation requires one to generate synthetic instances of tasks and machines with well-identified properties. Carefully controlling these properties is mandatory to avoid any bias. We consider the scheduling problem consisting of allocating independent sequential tasks on unrelated machines while minimizing the maximum execution time. In this problem, the instance is a cost matrix that specifies the execution cost of any task on any machine. This article proposes two measures for quantifying the heterogeneity properties of a cost matrix. An analysis of two classical methods used in the literature reveals a bias in previous studies. We propose new methods to generate instances with given heterogeneity properties and we show that heterogeneity has a significant impact on twelve heuristics.
Type de document :
Article dans une revue
IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01664636
Contributeur : Louis-Claude Canon <>
Soumis le : vendredi 15 décembre 2017 - 09:26:43
Dernière modification le : vendredi 6 juillet 2018 - 15:06:09

Fichier

tpds16-1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01664636, version 1

Citation

Louis-Claude Canon, Laurent Philippe. On the Heterogeneity Bias of Cost Matrices for Assessing Scheduling Algorithms. IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2017. 〈hal-01664636〉

Partager

Métriques

Consultations de la notice

158

Téléchargements de fichiers

41