Tight Analysis of Relaxed Multi-Organization Scheduling Algorithms

Abstract : 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.
Document type :
Conference papers
25th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2011), May 2011, Anchorage, United States. 2011
Liste complète des métadonnées


https://hal.inria.fr/inria-00592174
Contributor : Grégory Mounié <>
Submitted on : Wednesday, May 11, 2011 - 3:03:52 PM
Last modification on : Monday, October 5, 2015 - 4:58:07 PM
Document(s) archivé(s) le : Friday, November 9, 2012 - 11:10:42 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00592174, version 1

Collections

Citation

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. 2011. <inria-00592174>

Share

Metrics

Record views

421

Document downloads

84