Tight Analysis of Relaxed Multi-Organization Scheduling Algorithms - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

Tight Analysis of Relaxed Multi-Organization Scheduling Algorithms

Résumé

The goal of this paper is to study how limited cooperation can impact the quality of the schedule obtained by multiple independent organizations in a typical grid computing platform. This relaxed version of the problem known as the Multi-Organization Scheduling Problem (MOSP) models an environment where organizations providing both resources and jobs tolerate a bounded degradation on the makespan of their own jobs in order to minimize the makespan over the entire platform. More precisely, the technical contributions are the following. First, we improve the existing inapproximation bounds for this problem proving that what was previously though as not polynomially approximable (unless P = N P ) is actually not approximable at all. We achieve this using two families of instances whose Pareto optimal solutions are on par with the previous inaproximability bounds. Then, we present two algorithms that solve the problem with approximation ratios of (2; 3/2) and (3; 4/3) respectively. This means that when using the first (second) algorithm, if an organization tolerates that the completion time of its last job cannot exceed twice (three times) the time it would have obtained by itself, then the algorithm provides a solution that is a 3/2-approximation (4/3-approximation) for the optimal global makespan. Both algorithms are efficient since their performance ratio correspond to the Pareto optimal solutions of the previously defined instances.
Fichier principal
Vignette du fichier
main.pdf (171.69 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00592174 , version 1 (11-05-2011)

Identifiants

  • HAL Id : inria-00592174 , version 1

Citer

Daniel Cordeiro, Pierre-Francois Dutot, Grégory Mounié, Denis Trystram. Tight Analysis of Relaxed Multi-Organization Scheduling Algorithms. 25th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2011), May 2011, Anchorage, United States. ⟨inria-00592174⟩
438 Consultations
143 Téléchargements

Partager

Gmail Facebook X LinkedIn More