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