Cooperation in multi-organization scheduling

Abstract : The distributed nature of the grid results in the problem of scheduling parallel jobs produced by several independent organizations that have partial control over the system. We consider systems composed of n identical clusters of m processors. We show that it is always possible to produce a collaborative solution that respects participant's selfish goals, at the same time improving the global performance of the system. We propose algorithms with a guaranteed worst-case performance ratio on the global makespan: a 3-approximation algorithm if the last completed job requires at most m/2 processors, and a 4-approximation algorithm in the general case.
Type de document :
Communication dans un congrès
Springer. Euro-Par 2007 Parallel Processing, Aug 2007, Rennes, France. Springer, 4641, pp.224-233, 2007, LNCS. 〈10.1007/978-3-540-74466-5_25〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00689789
Contributeur : Ist Rennes <>
Soumis le : vendredi 20 avril 2012 - 11:04:08
Dernière modification le : mercredi 11 avril 2018 - 01:56:02

Lien texte intégral

Identifiants

Collections

Citation

Fanny Pascual, Krzysztof Rzadca, Denis Trystram. Cooperation in multi-organization scheduling. Springer. Euro-Par 2007 Parallel Processing, Aug 2007, Rennes, France. Springer, 4641, pp.224-233, 2007, LNCS. 〈10.1007/978-3-540-74466-5_25〉. 〈hal-00689789〉

Partager

Métriques

Consultations de la notice

245