Descriptif

Sujet 1 (Frédéric Meunier) : l'organisation d'une chaîne de production en  "Bucket Brigades" permet d'assurer une grande flexibilité, tout en permettant d'avoir un taux de production souvent proche de l'optimal. Pour des chaînes de préparation de commande, un tel mode d'organisation présente un certain nombre de difficultés, et Pyung-Hoi Koo (Operations Research Spectrum, 2009) a proposé des pistes pour les pallier, tout en laissant plusieurs aspects encore susceptibles d'être optimisés. 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 2 (Frédéric Meunier) : on considère un problème d'atelier de production, pour lequel les employés ont des qualifications variées. Des produits arrivent selon un processus de Poisson, et chacun doit visiter un sous-ensemble des machines dans un ordre spécifique. Le taux d'arrivée étant assez élevé, des files d'attente peuvent se former devant les machines. Comme les employés sont moins nombreux que les machines, le défi est de décider sur quelle machine envoyer un employé qui vient de finir une tâche. L'objet du projet est de trouver les règles d'affectation qui permettent d'avoir un temps de séjour moyen le plus faible possible.

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 ».

Format des notes
Numérique sur 20

Littérale/grade réduit
Pour les étudiants du diplôme Echanges PEI
Le rattrapage est autorisé (Note de rattrapage conservée)

L'UE est acquise si note finale transposée >= C

Crédits ECTS acquis : 6 ECTS

Le coefficient de l'UE est : 13

La note obtenue rentre dans le calcul de votre GPA.

La note obtenue est classante.
Pour les étudiants du diplôme Diplôme d'ingénieur de l'Ecole polytechnique
Le rattrapage est autorisé