Exact algorithms for a task assignment problem

Abstract : We consider the problem of scheduling an application on a computing system consisting of heterogeneous processors and data repositories. The application consists of a large number of file-sharing otherwise independent tasks. The files initially reside on the repositories. The processors and the repositories are connected through a heterogeneous interconnection network. Our aim is to assign the tasks to the processors, to schedule the file transfers from the repositories, and to schedule the executions of tasks on each processor in such a way that the turnaround time is minimized. We propose a heuristic composed of three phases: initial task assignment, task assignment refinement, and execution ordering. We experimentally compare the proposed heuristics with three well-known heuristics on a large number of problem instances. The proposed heuristic runs considerably faster than the existing heuristics and obtains 10-14% better turnaround times than the best of the three existing heuristics.
Type de document :
Article dans une revue
Parallel Processing Letters, World Scientific Publishing, 2009, 19 (3), pp.451--465. 〈10.1142/S012962640900033X〉
Liste complète des métadonnées

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00381907
Contributeur : Bora Uçar <>
Soumis le : mercredi 6 mai 2009 - 16:31:30
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : lundi 15 octobre 2012 - 10:01:03

Fichier

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

Identifiants

Collections

Citation

Kamer Kaya, Bora Uçar. Exact algorithms for a task assignment problem. Parallel Processing Letters, World Scientific Publishing, 2009, 19 (3), pp.451--465. 〈10.1142/S012962640900033X〉. 〈ensl-00381907〉

Partager

Métriques

Consultations de la notice

366

Téléchargements de fichiers

896