Problème de bin packing

Problème de bin packing

Le problème de bin packing relève de la recherche opérationnelle et de l'optimisation combinatoire. Il s'agit de trouver le rangement le plus économique possible pour un ensemble d'articles dans des boîtes. Le problème classique se définit en une dimension, mais il existe de nombreuses variantes en deux ou trois dimensions.

Sommaire

Applications pratiques

Le problème de bin packing peut être appliqué à 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 dimension :

  • rangement d'objets dans des boîtes, des camions, etc...(avec superposition de boîtes)

Formulation du problème

Dans le problème classique, les données sont :

  • un nombre infini de boîtes de taille C
  • une liste 1,2,\ldots,n d'articles i de taille ci.

On cherche à trouver le rangement valide pour tous ces articles qui minimise le nombre de boîtes utilisées. Pour qu'un rangement soit valide, la somme des tailles des articles affectés à une boîte doit être inférieure ou égale à C.

Pour décrire une solution, on peut utiliser un codage binaire pour indiquer dans quel boîte j chaque objet i est rangé.

  • La variable xij vaudra 1 si l'article i est rangé dans la boîte j, et 0 sinon.
  • La variable binaire yj est égale à 1 si la boîte j est utilisée, 0 sinon.

On cherche donc à minimiser le nombre de boîtes utilisées

min \sum_{j=1}^n y_j

Sous les contraintes suivantes :

\sum_{i=1}^{n} c_i x_{ij} \leq C y_j, j=1,\ldots,n
\sum_{j=1}^{n} x_{ij} = 1, i=1,\ldots,n
x_{i,j} \in \{0,1\}, i=1,\ldots,n, j=1,\ldots,n
y_j \in \{0,1\}, j=1,\ldots,n

La première inégalité signifie qu'on ne peut dépasser la taille d'une boîte pour un rangement. A noter que la partie droite de l'inégalité oblige yj à prendre la valeur 1 dès qu'un article est rangé dans la boîte j. La deuxième inégalité impose à tous les objets d'être rangés dans une boîte et une seule. Toute solution pour laquelle la famille d'équations précédente est vérifiée est dite réalisable.

La modélisation décrite plus haut a été proposée par Leonid Kantorovich[1] en 1960. Il existe d'autres formulations linéaires pour ce problème, sous forme d'un problème de flot maximum dans un graphe, ou utilisant une décomposition de Dantzig et Wolfe.

NP-complétude

Article détaillé : théorie de la complexité.

Ce problème fait partie de la classe des problèmes NP-difficiles. Sauf si P = NP, on ne peut pas le résoudre à l'aide d'un algorithme de complexité polynomiale. La preuve de ce résultat se fait par réduction à partir du problème de bipartition.

Méthodes de résolution

Le problème de bin packing a été largement étudié dans la communauté de recherche opérationnelle. Il existe des heuristiques très efficaces pour le résoudre, et une modélisation très efficace utilisant l'optimisation linéaire.

Méthode heuristiques

Article détaillé : heuristique.

Pour résoudre le problème de bin packing, on utilise souvent des algorithmes simples comme first-fit decreasing (FFD) ou best-fit decreasing (BFD). Les deux méthodes fonctionnent suivant un principe similaire : on trie la liste d'articles par ordre décroissant de taille, puis on range chaque article dans l'ordre. Dans first-fit, on range l'article courant dans la première boîte qui peut le contenir. Dans best-fit, on range l'article dans la boîte la mieux remplie qui puisse le contenir. Ces algorithmes ne sont pas optimaux, mais ils permettent d'obtenir de très bons résultats en pratique.

Les algorithmes Best Fit Decreasing et First Fit Decreasing n'utilisent jamais plus de 11/9 OPT + 1 boîtes (où OPT est le nombre optimal de boîtes dans une solution optimale)[2]. La procédure de tri est la partie la plus coûteuse de l'algorithme, mais sans elle, la qualité de la méthode est beaucoup moins bonne. On obtient dans ce cas des solutions utilisant au pire 17/10 OPT + 2 boîtes.

Une version plus efficace de FFD utilise au plus 71/60 OPT + 1 boîtes[3].

Méthodes exactes

On utilise aujourd'hui essentiellement l'optimisation linéaire en nombres entiers pour résoudre ce problème. Lorsque l'instance traitée est de faible taille, la formulation de Kantorovich peut être utilisée. Lorsque le nombre d'articles est grand, on utilise plutôt une résolution par génération de colonnes utilisant le modèle de Gilmore et Gomory[4], ou des modèles reposant sur la résolution d'un problème de flot maximal. La grande qualité des méthodes obtenues est due à l'excellente relaxation linéaire du modèle. La qualité de cette relaxation fait d'ailleurs l'objet d'une conjecture, appelée MIRUP : si L est la valeur de la solution de ce modèle en nombres réels et OPT la valeur de la solution en nombres entiers, alors on aurait \lceil L \rceil + 1 \geq OPT.

Extensions, généralisations

Le problème de bin packing a de fortes connexions avec le problème du sac à dos (knapsack). Ces deux problèmes sont les représentants les plus connus de ce qu'on appelle dans la communauté de recherche opérationnelle les problèmes de découpe et de conditionnement (cutting and packing).

Il existe de nombreuses extensions pour le problème de bin packing basique. On peut considérer ces articles possédant deux ou trois dimensions, interdire à certains articles d'être rangés dans la même boîte, ou autoriser l'usage de boîtes de tailles différentes. Les objets peuvent prendre des formes différentes : rectangles (pavés), cercles (sphères). Lorsque les formes ne sont pas convexes, on parlera plutôt de problème de nesting.

La version du problème où l'on ne connaît pas la liste d'objets par avance a été longuement étudiée. On parle de version on-line du problème.

Lorsque des articles de même taille apparaissent de nombreuses fois dans le problème, on parlera plutôt de problème de cutting-stock.

Voir aussi

Notes

  1. ↑ L.V. Kantorovich, Mathematical methods of organizing and planning production, Management Science, 6: 363-422, 1960
  2. ↑ M. Yue, "A simple proof of the inequality FFD(L) ≤ (11/9)OPT(L) + 1, for all L, for the FFD bin-packing algorithm", Acta Mathematicae Applicatae Sinica 7, pp. 321–331, 1991.
  3. ↑ Michael R. Garey and David S. Johnson, "A 71/60 theorem for bin packing", Journal of Complexity, Vol. 1, pp. 65–106, 1985.
  4. ↑ P. C. Gilmore, R. E. Gomory, A linear programming approach to the cuttingstock problem (part II), Operations Research 11, 363-888, 1963.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème de bin packing de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Probleme de bin packing — Problème de bin packing Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème… …   Wikipédia en Français

  • Bin packing problem — Problème de bin packing Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème… …   Wikipédia en Français

  • Probleme du sac a dos — Problème du sac à dos Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? Le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un …   Wikipédia en Français

  • Probleme de tournees de vehicules — Problème de tournées de véhicules Figure illustrant un problème de tournées de véhicules avec un dépot central. Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d optimisation combinatoire. Il s agit …   Wikipédia en Français

  • Problème de livraison et de collecte — Problème de tournées de véhicules Figure illustrant un problème de tournées de véhicules avec un dépot central. Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d optimisation combinatoire. Il s agit …   Wikipédia en Français

  • Problème du sac à dos — Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? En algorithmique, le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un… …   Wikipédia en Français

  • Problème de tournées de véhicules — Figure illustrant un problème de tournées de véhicules avec un dépot central. Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d optimisation combinatoire. Il s agit de déterminer les tournées d une… …   Wikipédia en Français

  • Suite de Sylvester — Démonstration graphique de la convergence vers 1 de la somme 1/2 + 1/3 + 1/7 + 1/43 +... Chaque rang de n carrés de côté 1/n a une aire totale de 1/n ; l ensemble des rangs recouvre exactement un carré plus grand, d aire 1. [Les carrés de… …   Wikipédia en Français

  • Ordonnancement multicœur soucieux des caches et équilibrage de charge — L ordonnancement multicœur soucieux des caches et équilibrage de charge est une problématique importante dans la conception des systèmes d exploitation destinés à gérer des microprocesseurs multi cœurs. L évolution des matériels depuis des… …   Wikipédia en Français

  • Liste de problèmes NP-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problème de décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive. La …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”