Friday 28
New application domain on OR (health, biology, computer science, economy, energy, sustainable growth, cloud computing...), transfer to industry and software
Sonia Djebali
› 14:45 - 15:05 (20min)
› Bât. B - TD 35
Conception d'un système de rangement à deux niveaux
Martin Bué  1@  , François Clautiaux  2  , Luce Brotcorne  1  
1 : DOLPHIN  (INRIA Lille - Nord Europe)
INRIA, CNRS : UMR8022, Université Lille I - Sciences et technologies
2 : RealOpt  (INRIA Bordeaux - Sud-Ouest)
CNRS : UMR0000, Université Victor Segalen - Bordeaux II, Université Sciences et Technologies - Bordeaux I, INRIA, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)

Cette présentation a pour objet un problème de placement à deux niveau et une méthode de résolution adaptée. Plus précisément, il s'agit de conception de système de rangement. Une première phase consiste à découper le rangement en compartiments de différentes tailles. La seconde cherche à optimiser la répartition des objets dans ces compartiments en fonction de leurs valeurs au cours du temps.

Dans un premier temps le problème a été modélisé puis décomposé. On montre en particulier que le modèle peut s'écrire sous la forme d'un problème de sac à dos à contraintes disjonctives dont on explicite les sous-problèmes. On distinguera par ailleurs le cas où un objet doit avoir la même taille que le compartiment, du cas où il peut être plus petit.

La méthode de résolution tient compte de ces spécificités. Nous avons utilisé une approche type Branch & Bound. Les sous-problèmes sont résolus soit via un solveur linéaire, soit grâce à une heuristique polynomiale exploitant les propriétés des graphes d'intervalles.

Des résultats numériques viendront étayer l'exposé et permettront d'illustrer l'efficacité des méthodes proposées. 


Online user: 1