Séminaire Eric Sanlaville

Jeudi 14 Janvier 2010 (14h00)

Eric Sanlaville, Laboratoire Informatique Traitement de l'Information et Systèmes (LITIS ), Le Havre.

Titre : Affectation de ressources en ligne, modèle par scénarios, approche multi-critères. .

Résumé : Nous considérons un problème d'allocation de ressources. Ces ressources sont disponibles en quantité limitée et attribuées à au plus un utilisateur de façon permanente. Le problème a deux caractéristiques spécifiques. D'une part, les utilisateurs sont tous de même importance et doivent être traités de la manière la plus équitable possible. D'autre part, les demandes des utilisateurs ne sont pas connues au départ mais arrivent au fil de l'eau et doivent être traitées dès leur apparition.

Ce type de problème d'affectation apparaît en particulier dans les domaines suivants : affectation de bande passante dans un réseau, gestion d'une grille de calcul. Dans le second cas, les ressources sont soit de l'espace de stockage, soit des unités de calcul. Nous considérons que le comportement des utilisateurs peut être prédit dans une certaine mesure. Le modèle choisi est celui d'un nombre fini de scénarios pour les arrivées des demandes. Le problème consiste alors à construire des politiques (donnant une affectation par vecteur de demande possible) équitables. Nous définissons d'abord formellement la notion d'équité entre utilisateurs pour notre modèle. Nous montrons ensuite comment utiliser une approche multi-critères pour construire des politiques équitables (qui sont les points de la courbe de Pareto associée). Enfin, nous présentons un algorithme de calcul de ces politiques et nous étudions sa complexité.