Ancrage de solutions en optimisation robuste: applications à la gestion de ressources

Sujet du stage

Dans un contexte réel, les données d'un problème d'optimisation combinatoire peuvent être soumises à des fluctuations entre le jour où une solution initiale doit être adoptée et le jour de mise en oeuvre effective de cette solution. Il est alors nécessaire de remettre en cause la solution initiale si cette dernière n'est plus valide ou n'est plus optimale: on parle alors d'une étape de réoptimisation. Le coût de mise en oeuvre d'une solution initiale est donc le coût de la solution initialement prévue, plus le coût nécessaire à la transition vers une nouvelle solution. Dans le cadre devenu classique de l'optimisation robuste, on choisit habituellement une solution robuste initiale qui réalise un compromis entre son coût propre et son aptitude à s'adapter aux aléas.

Un nouveau concept introduit par l'équipe RO du laboratoire LIP6 propose une nouvelle approche d'optimisation robuste: nous définissons le niveau d'ancrage entre deux solutions comme le nombre de décisions qui sont différentes entre ces deux solutions. Le problème de réoptimisation revient alors à rechercher une solution de niveau d'ancrage minimal vis à vis de la solution initiale. Plus globalement, nous appelons solution ancrée une solution initiale pour laquelle, quels que soient les aléas considérés dans un ensemble prédéfini, il existe une solution ayant un niveau d'ancrage bas vis-à-vis de la solution initiale. Ainsi une solution ancrée correspond à un surdimensionnement moindre par rapport à une solution robuste, tout en permettant une réoptimisation à faible coût entre la solution initiale et la nouvelle solution. Le concept d'ancrage de solutions a été initialement introduit dans le cadre des problèmes d'ordonnancement dit PERT où sont pris en compte uniquement des contraintes de précédences.

Objectifs du stage

Le cadre théorique de ce stage est l'algorithmique et l'étude de complexité de problèmes combinatoires. Nous utiliserons également la programmation linéaire et la programmation linéaire en nombres entiers. Ce stage comporte des objectifs pratiques et théoriques:

Applications au problème d'affectations de personnels

Nous appliquerons l'approche par solutions ancrées au problème d'allocation de ressources et plus particulièrement à l'affectation de personnels à compétences particulières. C'est le cas par exemple au sein d'EDF pour les Centres de Relation Clientèle (CRC) où les activités à traiter représentent une charge de travail pour plus de 5.000 conseillers. Dans ce cadre, la gestion du personnel demande un dimensionnement des effectifs en fonction des prévisions de charge sur le nombre et la nature technique des questions posées par les clients: ce qui implique de prendre en compte des recrutements, des plans de formation de personnels ou le recourt à l'externalisation. La charge sur certaines activités du personnel présente des incertitudes et des pics qu'il faut pouvoir prendre en compte sans pour autant surdimensionner les ressources sur le reste du temps.

Extension vers un niveau d'ancrage multicritère, multiagent et par scénarios
collaboration avec Olivier Spanjaard (équipe DECISION du laboratoire LIP6)

La définition initiale du niveau d'ancrage donnée initialement est assez réductrice: par exemple, le nombre de différences entre deux solutions n'est pas toujours le coût à payer pour passer d'une solution à une autre. Dans ce projet, nous envisageons de remettre en question la définition du niveau d'ancrage en nous appuyant sur l'optimisation multicritère: par exemple en considérant une mesure prenant en compte à la fois le nombre de différences et l'écart de coût entre les solutions. D'autres contextes sont aussi envisagés comme celui des contextes multiagents où le coût d'une solution impacte plusieurs agents qui ont chacun leur propre évaluation de l'évolution du coût de la solution. Une autre approche pour les solutions ancrées serait de prendre en compte différents scénarios pour l'évolution des données du problème. Ce cadre classique en robustesse est intéressant à transposer au contexte des solutions ancrées.

Perspective en thèse

Ce stage permet à l'étudiant une ouverture au monde de la recherche théorique et appliquée. Une poursuite en thèse sur ce sujet est envisagée dans le cadre académique ou dans le cadre d'un financement par EDF.

Pour plus d'informations:

http://androide.lip6.fr/?q=node/250