 |
Génération de colonnes pour le Bin-Packing avec seuils
1 : Laboratoire des sciences pour la conception, lóptimisation et la production
Institut polytechnique de Grenoble - Grenoble Institute of Technology, Université Grenoble Alpes, Centre National de la Recherche Scientifique : UMR5272
2 : Laboratoire d'Informatique de Grenoble
Centre National de la Recherche Scientifique : UMR5217, Université Grenoble Alpes, Institut polytechnique de Grenoble - Grenoble Institute of Technology, Centre National de la Recherche Scientifique
Nous considerons une nouvelle variante du Bin-Packing, appelée Bin-Packing avec seuils. Dans cette variante, chaque item possède un seuil de sorte qu'au moment de placer l'item dans la boîte, la capacité restante doit rester supérieure au seuil. Par conséquent, selon l'ordre de remplissage au sein d'une boite, une même affectation est succeptible d'être ou ne pas être réalisable.
La méthode classique de génération de colonnes basée sur la formulation "set-partitioning" du Bin-Packing est adaptée pour prendre en compte cette nouvelle contrainte. L'efficacité de la méthode est évaluée sur un jeu d'instance adapté de la littérature.
