Cooperation in Multi-Organization Scheduling

Fanny Pascual 1 Krzysztof Rzadca 2 Denis Trystram 3
1 RO - Recherche Opérationnelle
LIP6 - Laboratoire d'Informatique de Paris 6
3 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
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 in which each organization owns a cluster of processors. Each organization wants its tasks to be completed as soon as possible. In this paper, we model an off-line system consisting of N identical clusters of m processors. We show that it is always possible to produce a collaborative solution that respects participants' selfish goals, at the same time improving the global performance of the system. We propose an algorithm (called MOLBA) with a guaranteed worst-case performance ratio on the global makespan, equal to 4. Next, we show that a better bound (equal to 3) can be obtained in a specific case when the last completed job requires at most m/2 processors. Then, we derive another algorithm (called ILBA) that in practice improves the proposed, guaranteed solution by further balancing the schedules. Finally, by an extensive evaluation by simulation, we show that the algorithms are efficient on typical instances.
Type de document :
Article dans une revue
Concurrency and Computation: Practice and Experience, Wiley, 2009, 21 (7), pp.905-921. 〈10.1002/cpe.1378〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00953257
Contributeur : Grégory Mounié <>
Soumis le : vendredi 28 février 2014 - 11:07:54
Dernière modification le : mercredi 11 avril 2018 - 01:59:24

Lien texte intégral

Identifiants

Citation

Fanny Pascual, Krzysztof Rzadca, Denis Trystram. Cooperation in Multi-Organization Scheduling. Concurrency and Computation: Practice and Experience, Wiley, 2009, 21 (7), pp.905-921. 〈10.1002/cpe.1378〉. 〈hal-00953257〉

Partager

Métriques

Consultations de la notice

190