Cooperation in Multi-Organization Scheduling

Fanny Pascual (travail effectué avec Krzysztof Rzadca et Denis Trystram)

LIP6, Université Paris 6
(travail effectué à l'INRIA Rhône-Alpes)

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.