Descriptif

L'objet de ce projet est de proposer des méthodes pour résoudre les problèmes d'optimisation qui en résultent, d'implémenter ces méthodes et de les tester.

Sujet 1 (Frédéric Meunier) : On considère un entrepôt automatisé, avec deux ascenseurs partageant une même rampe, comme celui étudié par Carlo et Vis (2012). Des requêtes de stockage ou de récupération arrivent au fil de l’eau, suivant un processus de Poisson. Quelle politique utiliser pour minimiser le délai moyen de satisfaction d’une requête ? Ce projet vise à proposer des algorithmes pour répondre à cette question et à les évaluer par simulation.

Sujet 2 (Frédéric Meunier) :L'organisation d'une chaîne de production en  "Bucket Brigades" permet d'assurer une grande flexibilité, tout en assurant un taux de production souvent proche de l'optimal. Dans le cas à deux employés, le comportement dans le temps long de la chaîne a été décrit de manière quasi-complète par Gurumoorthy, Banerjee et Paul (2009). Ce projet vise à explorer de manière expérimentale le comportement dans le temps long du cas à trois employés et si possible à formuler certaines conjectures.

Sujet 3 (Eric Gourdin) : on s’intéresse au routage dans les réseaux Internet, que l’on cherchera, dans un premier temps à simuler, puis, dans un deuxième temps, à optimiser. Le réseau est modélisé par un graphe dont les liens (arêtes/arcs) sont munis de capacités. On dispose également d’un ensemble de demandes, chaque demande étant définie par un nœud source, un nœud destination et un volume de trafic à écouler. On suppose que le réseau utilise un protocole de routage basé sur les plus-court-chemins : une valeur de métrique administrative (supposée donnée) est associée à chaque lien et le trafic entre le nœud source et le nœud destination est écoulé sur les plus-court-chemins (au sens de ces métriques administratives).  S’il y a plusieurs plus-court-chemin, le trafic est réparti sur les chemins conformément au protocole ECMP. La charge d’un lien est le ratio entre le trafic écoulé et la capacité. On mesure la « qualité » du routage en calculant la charge du lien le plus chargé. On s’intéressera à une évolution des protocoles de routage appelé « Segment Routing » où une demande peut être routée sur une suite de segments, le routage au sein de chaque segment étant lui-même régi par les plus-court-chemins.

Sujet 4 (Eric Gourdin) : dans un réseau Internet, on cherche à calculer un routage « robuste » appelé « oblivious routing ». Le contexte général est similaire à celui du sujet précédent : un graphe avec des liens muni de capacités, un ensemble de demandes à écouler. Contrairement au sujet précédent, le routage à calculer est totalement libre (on peut fractionner le trafic sur autant de chemins qu’on veut du moment qu’on satisfait toujours la conservation des flots sur chaque sommet intermédiaire). On suppose ici que les volumes des demandes ne sont pas connus. On cherche un routage valide pour tous les ensembles de demandes possibles et tel que le maximum sur tous les ensembles de demandes du ratio entre la charge max avec ce routage unique avec le ratio obtenu avec un routage qui serait optimisé pour cet ensemble de demande soit aussi petit que possible (oblivious routing). Le modal consiste à proposer des façons de calculer (ou d’approcher) ce routage dit « oblivious ».