Les problèmes d’ordonnancement consistent généralement à affecter un ensemble de tâches à un ensemble de machines, de d'affecter à chaque tâche une date à laquelle elle sera exécutée. L'objectif est souvent soit de minimiser la date à laquelle toutes les tâches ont été exécutées, soit la date moyenne à laquelle une tâche a été exécutée. Ces problèmes étant souvent rencontrés dans l'industrie, ils ont été très étudiés, tant d'un point de vue théorique que d'un point de vue pratique. Cependant, la plupart des algorithmes proposés sont déterministes, et non probabilistes. Ce stage propose d'étudier l'intérêt des algorithmes probabilistes en ordonnancement.
Suivant l'intérêt de l'étudiant, ce stage pourra prendre l'une de ces deux directions :
<strong>1) Analyse d'algorithmes probabilistes.</strong>
Le but sera ici d'analyser la performance d'algorithmes probabilistes dans lequel les données sont traitées dans un ordre aléatoire. En ce qui concerne les problèmes d’ordonnancement, le but peut par exemple être d'analyser, en terme de rapport d'approximation, l'algorithme qui, étant donné des tâches dans un ordre aléatoire affecte chaque tâche à une machine, dès qu'une machine est disponible. Bien que cet algorithme soit très simple, sa performance n'est pas actuellement pas connue.
D'autres algorithmes dans lesquels les données sont traitées dans un ordre aléatoire, pour d'autres problèmes que des problèmes d’ordonnancement (couplage, etc.) pourront également être analysés.
Il est intéressant de connaître la performance de ces algorithmes probabilistes car, bien que moins performants que des algorithmes exacts, ces algorithmes sont souvent très simples, très rapides (et donc souvent implémentés en pratique), et ils sont robustes aux manipulations (ils sont donc très utiles pour les problèmes en ligne, et dans des systèmes dans lesquels interviennent des agents égoïstes).
<strong>2) Problèmes dans lesquels interviennent des agents égoïstes.</strong>
Le but est ici de concevoir des algorithmes efficaces pour des problèmes d'ordonnancements en présence d'agents égoïstes (qui cherchent à optimiser leur propre fonction objectif, et non la fonction objectif du système). L'apport des algorithmes probabilistes pour ces problèmes sera étudié, mais d'autres techniques apparues récemment en théorie des jeux algorithmique pourront également être utilisées. Il pourra par exemple être intéressant d'étudier l'apport de mécanismes avec vérification pour des problèmes d'ordonnancement en présence d'agents égoïstes. <br><br>
----<br>
Ce stage sera encadré par <a href="http://www-desir.lip6.fr/~doerr/">Carola Doerr</a> (CNRS, LIP6), <a href="https://www.ibisc.univ-evry.fr/~thang/">Thang Nguyen Kim</a> (Université d'Evry Val d'Essonne, IBISC), et <a href="http://www-poleia.lip6.fr/~pascualf/">Fanny Pascual</a> (UPMC, LIP6). Il pourra se dérouler soit au LIP6, soit à l'IBISC.