Multi-organization scheduling approximation algorithms

Abstract : In this paper we consider the problem of scheduling on computing platforms composed of several independent organizations, known as the Multi-Organization Scheduling Problem (MOSP). Each organization provides both resources and jobs and follows its own objectives. We are interested in the best way to minimize the makespan on the entire platform when the organizations behave in a selfish way. We study the complexity of the MOSP problem with two different local objectives ―- makespan and average completion time ―- and show that MOSP is strongly NP-Hard in both cases. We formally define a selfishness notion, by means of restrictions on the schedules. We prove that selfish behavior imposes a lower bound of 2 on the approximation ratio for the global makespan. We present various approximation algorithms of ratio 2 which validate selfishness restrictions. These algorithms are experimentally evaluated through simulation, exhibiting good average performances and presenting good fairness to organizations' local objectives.
Type de document :
Article dans une revue
Concurrency and Computation: Practice and Experience, Wiley, 2011, 23 (17), pp.2220―2234. 〈10.1002/cpe.1752〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00796860
Contributeur : Grégory Mounié <>
Soumis le : mardi 5 mars 2013 - 11:05:33
Dernière modification le : vendredi 12 octobre 2018 - 01:18:01

Lien texte intégral

Identifiants

Collections

Citation

Johanne Cohen, Daniel Cordeiro, Denis Trystram, Frédéric Wagner. Multi-organization scheduling approximation algorithms. Concurrency and Computation: Practice and Experience, Wiley, 2011, 23 (17), pp.2220―2234. 〈10.1002/cpe.1752〉. 〈hal-00796860〉

Partager

Métriques

Consultations de la notice

277