Worst-Case Analysis of Scheduling Heuristics of Parallel Systems

Abstract : It is well-known that most scheduling problems arising from parallel systems are NP-hard, even under very special assumptions. Thus various suboptimal algorithms, in particular heuristics, were proposed in the literature. Worst-case error bounds are established in this note for heuristics of makespan minimization of parallel computations. Different parallel computation models are investigated, including interprocessor communication, task duplication, multiprocessor tasks and parallel tasks. Due to the heterogeneity of these systems, scheduling heuristics can be far away from the optimal solutions. The bounds presented here provide insights to the design of scheduling heuristics in order to obtain good performance guarantee.
Type de document :
Rapport
RR-2710, INRIA. 1995
Liste complète des métadonnées

https://hal.inria.fr/inria-00073981
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:13:52
Dernière modification le : samedi 27 janvier 2018 - 01:31:29
Document(s) archivé(s) le : jeudi 24 mars 2011 - 13:36:52

Fichiers

Identifiants

  • HAL Id : inria-00073981, version 1

Collections

Citation

Zhen Liu. Worst-Case Analysis of Scheduling Heuristics of Parallel Systems. RR-2710, INRIA. 1995. 〈inria-00073981〉

Partager

Métriques

Consultations de la notice

97

Téléchargements de fichiers

103