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 ».
The aim of this project is to propose methods for solving the resulting optimization issues, implement these methods and test them.
Topic 1(Frédéric Meunier): the organization of the production line in "Bucket Brigades" ensures great flexibility, while often having a production rate that is close to optimal. For order-picking lines, this type of organization presents a number of difficulties, and Pyung-Hoi Koo (Operations Research Spectrum, 2009) proposed ways to offset them while leaving several aspects open to further optimization.
Topic 2 (Frédéric Meunier): it is considered a workshop production issue, in which employees have a variety of qualifications. Products arrive according to a Poisson process, and each must visit a subset of the machines in a specific order. The arrival rate being quite high, queues can be formed in front of machines. As the employees are less numerous than the machines, the challenge is to pick which machine will be sent to an employee who has just completed a task. The aim of the project is to find the assignment rules that will keep the average stay time as low as possible.
Topic 3 (Eric Gourdin): We're interested in routing in Internet networks, which we'll first simulate and then optimize. The network is modeled by a graph whose links (edges/arcs) are equipped with capacities. We also have a set of requests, each request is defined by a source node, a destination node, and a volume of traffic to be handled. It is assumed that the network uses a shortest-path routing protocol: each link is assigned a (presumably given) administrative metric value, and traffic between the source and destination nodes is routed along the shortest paths (as defined by these administrative metrics). If there is more than one shortest path, traffic is distributed over the paths in accordance with the ECMP protocol. Link load is the ratio of traffic flow and capacity. Routing "quality" is measured by calculating the load of the fullest link. We'll take an interest in routing protocol evolution called "Segment Routing" where a request can be routed on a continuation of segments, the routing within each segment being by itself managed by the shortest paths.
Topic 4 (Eric Gourdin): in an Internet network, we're seeking to calculate a "robust" routing called "oblivious routing". The general context is similar to the previous topic: a graph with links provided with capacities, a set of requests to be handled. Unlike the previous topic, the routing to be calculated is totally free (traffic can be split over as many paths as you like, as long as you satisfy the flow conservation on each intermediate vertex). It is assumed that request volumes are unknown. We are looking for a routing that is valid for all possible requests and such the maximum overall request sets of the ratio between the max load with this single routing and the ratio obtained with a routing that would be optimized for this request set be as small as possible (oblivious routing). The modal approach consists in offering ways of calculating (or approximating) this "oblivious" routing.
- Teaching coordinator: Gourdin Eric
- Teaching coordinator: Meunier Frédéric