Multi-Users Scheduling in Parallel Systems

Abstract : We are interested in this paper to study scheduling problems in systems where many users compete to perform their respective jobs on shared parallel resources. Each user has specific needs or wishes for computing his/her jobs expressed as a function to optimize (among maximum completion time, sum of completion times and sum of weighted completion times). Such problems have been mainly studied through game theory. In this work, we focus on solving the problem by optimizing simultaneously each user's objective function independently using classical combinatorial optimization techniques. Some results have already been proposed for two users on a single computing resource. However, no generic combinatorial method is known for many objectives. The analysis proposed in this paper concerns an arbitrarily fixed number of users and is not restricted to a single resource. We first derive inapproximability bounds; then we analyze several greedy heuristics whose approximation ratios are close to these bounds. However, they remain high since they are linear in the number of users. We provide a deeper analysis which shows that a slightly modified version of the algorithm is a constant approximation of a Pareto-optimal solution.
Type de document :
Communication dans un congrès
Proceedings of IPDPS 2009, the 23rd International Parallel and Distributed Processing Symposium, 2009, Roma, Italy. IEEE, 2009, 〈10.1109/IPDPS.2009.5161037〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00800421
Contributeur : Grégory Mounié <>
Soumis le : mercredi 13 mars 2013 - 16:22:05
Dernière modification le : jeudi 11 janvier 2018 - 06:22:01
Document(s) archivé(s) le : vendredi 14 juin 2013 - 06:55:07

Fichier

ipdps09-ST.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Érik Saule, Denis Trystram. Multi-Users Scheduling in Parallel Systems. Proceedings of IPDPS 2009, the 23rd International Parallel and Distributed Processing Symposium, 2009, Roma, Italy. IEEE, 2009, 〈10.1109/IPDPS.2009.5161037〉. 〈hal-00800421〉

Partager

Métriques

Consultations de la notice

293

Téléchargements de fichiers

103