Wednesday 26
Stochastic and robust optimization, online optimization, queuing theory and simulation, machine learning and statistical methods
Michaël Gabay
› 16:40 - 17:00 (20min)
› Bât. B - TD 36
Algorithme d'Approximation pour le Bin Stretching Semi-Online
Michaël Gabay  1, *@  , Vladimir Kotov  2  , Nadia Brauner  3  
1 : Laboratoire des sciences pour la conception, l'optimisation et la production  (G-SCOP)  -  Website
Université Joseph Fourier - Grenoble I, Institut National Polytechnique de Grenoble (INPG), CNRS : UMR5272
46, avenue Félix Viallet 38031 Grenoble Cedex 1 -  France
2 : Belarusian State University, FPMI DMA department
Nezavisimosti avenue 220030 Minsk Belarus -  Bélarus
3 : Laboratoire des sciences pour la conception, l'optimisation et la production  (G-SCOP)
Université Joseph Fourier - Grenoble I, Institut National Polytechnique de Grenoble - INPG, CNRS : UMR5272, Institut National Polytechnique de Grenoble (INPG)
* : Corresponding author

Nous nous intéressons au problème de Bin Stretching dans lequel on doit placer des objets dans m récipients. Le problème est online et chaque objet doit être placé irrévocablement, dès son arrivée, dans un récipient. L'objectif est de minimiser la taille du récipient le plus rempli (le stretching factor). On ne connaît pas les objets préalablement à leur arrivée, ni leur nombre mais on sait que tous les objets peuvent tenir dans dans m récipients de taille unitaire. Le problème est donc semi-online.

Ce problème correspond également au problème d'ordonnancement online sur m machines parallèle, lorsqu'une durée totale réalisable est connue à l'avance et qu'on veut minimiser la dégradation de celle-ci.

Nous présentons un algorithme d'approximation de stretching factor 26/17. Il améliore le précédent meilleur algorithme, de Kellerer et Kotov (2013), de stretching factor 11/7.
Notre algorithme fonctionne en 2 phases et repose sur une classification des objets et des techniques d'agrégation de récipients. Sa complexité est linéaire en le nombre total d'objets (plus précisément, chaque objet est affecté en temps constant).

Nous améliorons également la borne inférieure pour ce problème et montrons qu'il n'est pas approximable à moins de 19/14.

Références :
Hans Kellerer, Vladimir Kotov, An efficient algorithm for bin stretching, Operations Research Letters, Volume 41, Issue 4, July 2013, Pages 343-346.


Online user: 1