Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Problème de bin packing
Résumé
En recherche opérationnelle et en optimisation combinatoire, le bin packing est un problème algorithmique. Il s'agit de ranger des objets dans un nombre minimum de boîtes. Le problème classique se définit en une dimension, mais il existe de nombreuses variantes en deux ou trois dimensions.
Le problème de bin packing peut s'appliquer à un grand nombre de secteurs industriels ou informatiques.
Pour la version classique en une dimension :
rangement de fichiers sur un support informatique ;
découpe de câbles ;
remplissage de camions ou de containers avec comme seule contrainte le poids ou le volume des articles.
Pour la version en deux dimensions :
découpe de matière première ;
placement de boîtes sur une palette (sans superposition de boîtes) ;
placement dans un entrepôt (sans superposition de boîtes).
Pour la version en trois dimensions :
rangement d'objets physiques dans des boîtes, un entrepôt, des camions, etc. (avec superposition de boîtes, de palettes, etc.).
Dans sa forme générale le Bin-Packing est un problème d'optimisation, on a une population d'objets à ranger avec des contraintes dans le moins de boîtes identiques possibles (appelées bins).
Lorsqu'il n'y a qu'une dimension, il n'y a pas de problème de placement au départ, voici la formulation du problème
Soit , des réels positifs tous non nuls, trouver et une fonction d'assignation tels que:
(la somme des tailles des objets de chaque bin n'excède pas sa capacité), de façon que soit minimal.
Ici on a opéré une normalisation de la capacité de chaque boîte pour avoir moins de variables entrant en jeu.
On peut noter qu'une solution n'est pas unique, sauf si : en introduisant la relation d'équivalence entre deux solutions non nécessairement optimales:
qui veut dire que deux solutions sont égales à permutation des indices des bins près, on montre qu'il y a une multitude de solutions possibles, ainsi pour les rechercher, il sera utile de quotienter l'ensemble des solutions admissibles mais pas optimales par cette relation d'équivalence, afin de n'avoir qu'un représentant de chaque classe à gérer.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.