Problème d'emballage des bacs - Bin packing problem

Paires couverture/emballage-problème
Couvrir les problèmes Problèmes d'emballage Couverture minimale Emballage maximum Couverture minimale des bords Correspondance maximale Couverture de sommet minimale Ensemble indépendant maximum Couverture de poubelle Emballage en bac Couverture de polygone Emballage rectangulaire
v t e

Le problème d'emballage des bacs est un problème d'optimisation , dans lequel des articles de différentes tailles doivent être emballés dans un nombre fini de bacs ou de conteneurs, chacun d'une capacité donnée fixe, de manière à minimiser le nombre de bacs utilisés. Le problème a de nombreuses applications, telles que le remplissage de conteneurs, le chargement de camions avec des contraintes de capacité de poids, la création de sauvegardes de fichiers dans les médias et le mappage technologique dans la conception de puces à semi-conducteurs FPGA .

D'un point de vue informatique, le problème est NP-difficile et le problème de décision correspondant - décider si les éléments peuvent tenir dans un nombre spécifié de cases - est NP-complet . Malgré sa dureté dans le pire des cas, des solutions optimales à de très grandes instances du problème peuvent être produites avec des algorithmes sophistiqués. De plus, de nombreux algorithmes d'approximation existent. Par exemple, l' algorithme de premier ajustement fournit une solution rapide mais souvent non optimale, consistant à placer chaque élément dans le premier bac dans lequel il s'adaptera. Il nécessite Θ ( n  log  n ) temps, où n est le nombre d'articles à emballer. L'algorithme peut être rendu beaucoup plus efficace en triant d' abord la liste des éléments par ordre décroissant (parfois appelé algorithme décroissant du premier ajustement), bien que cela ne garantisse toujours pas une solution optimale, et pour des listes plus longues, cela peut augmenter le temps d'exécution de l'algorithme. On sait cependant qu'il existe toujours au moins un ordre d'articles qui permet au premier ajustement de produire une solution optimale.

Il existe de nombreuses variantes de ce problème, telles que l'emballage 2D, l'emballage linéaire, l'emballage par poids, l'emballage par coût, etc. Le problème de l'emballage des bacs peut également être considéré comme un cas particulier du problème du stock de coupe . Lorsque le nombre de bacs est limité à 1 et que chaque article est caractérisé à la fois par un volume et une valeur, le problème de la maximisation de la valeur des articles pouvant tenir dans le bac est connu sous le nom de problème du sac à dos .

Une variante de l'emballage en bac qui se produit dans la pratique est lorsque les articles peuvent partager de l'espace lorsqu'ils sont emballés dans un bac. Plus précisément, un ensemble d'articles pourrait occuper moins d'espace lorsqu'ils sont emballés ensemble que la somme de leurs tailles individuelles. Cette variante est connue sous le nom de regroupement de machines virtuelles, car lorsque des machines virtuelles (VM) sont compressées dans un serveur, leur besoin total en mémoire peut diminuer en raison des pages partagées par les machines virtuelles qui ne doivent être stockées qu'une seule fois. Si les articles peuvent partager l'espace de manière arbitraire, le problème de l'emballage des bacs est même difficile à évaluer. Cependant, si le partage d'espace s'inscrit dans une hiérarchie, comme c'est le cas avec le partage de mémoire dans les machines virtuelles, le problème de l'emballage des bacs peut être efficacement approché.

Une autre variante d'emballage en bac d'intérêt dans la pratique est le soi-disant emballage en bac en ligne . Ici, les éléments de volume différent sont censés arriver séquentiellement, et le décideur doit décider s'il doit sélectionner et emballer l'élément actuellement observé, ou bien le laisser passer. Chaque décision est sans rappel. En revanche, l'emballage hors ligne permet de réorganiser les articles dans l'espoir d'obtenir un meilleur emballage une fois que des articles supplémentaires arrivent. Cela nécessite bien sûr un stockage supplémentaire pour contenir les éléments à réorganiser.

Déclaration formelle

Dans Computers and Intractability, Garey et Johnson énumèrent le problème d'emballage des bacs sous la référence [SR1]. Ils définissent sa variante de décision comme suit.

Instance : ensemble fini d'éléments, une taille pour chacun , une capacité de bac d'entier positif et un entier positif . ${\style d'affichage I}$${\displaystyle s(i)\in \mathbb {Z} ^{+}}$${\displaystyle i\in I}$${\style d'affichage B}$${\style d'affichage K}$

Question: Y at - il une partition de en disjoints de telle sorte que la somme des tailles des éléments dans chaque est ou moins? ${\style d'affichage I}$${\displaystyle I_{1},\dots ,I_{K}}$${\style d'affichage I_{j}}$${\style d'affichage B}$

Notez que dans la littérature, une notation équivalente est souvent utilisée, où et pour chaque . De plus, la recherche s'intéresse principalement à la variante d'optimisation, qui demande la plus petite valeur possible de . Une solution est optimale si elle a un minimum . La valeur - pour une solution optimale pour un ensemble d'éléments est indiquée par ou juste si l'ensemble d'éléments est clair du contexte. ${\style d'affichage B=1}$${\displaystyle s(i)\in \mathbb {Q} \cap (0,1]}$${\displaystyle i\in I}$${\style d'affichage K}$${\style d'affichage K}$${\style d'affichage K}$${\style d'affichage I}$${\displaystyle \mathrm {OPT} (I)}$${\displaystyle \mathrm {OPT} }$

Une formulation de programmation linéaire en nombres entiers possible du problème est :

minimiser ${\displaystyle K=\sum _{j=1}^{n}y_{j}}$
sujet à	${\displaystyle K\geq 1,}$
	${\displaystyle \sum _{i\in I}^{n}s(i)x_{ij}\leq By_{j},}$	${\displaystyle \forall j\in \{1,\ldots ,n\}}$
	${\displaystyle \sum _{j=1}^{n}x_{ij}=1,}$	${\displaystyle \forall i\in I}$
	${\displaystyle y_{j}\in \{0,1\},}$	${\displaystyle \forall j\in \{1,\ldots ,n\}}$
	${\displaystyle x_{ij}\in \{0,1\},}$	${\displaystyle \forall i\in I\,\forall j\in \{1,\ldots ,n\}}$

où si bin est utilisé et si l'article est mis dans bin . ${\displaystyle y_{j}=1}$${\style d'affichage j}$${\style d'affichage x_{ij}=1}$${\style d'affichage i}$${\style d'affichage j}$

Dureté de l'emballage du bac

Le problème de l'emballage des bacs est fortement NP-complet . Cela peut être prouvé en réduisant le problème à 3 partitions fortement NP-complet à l'emballage en bacs.

De plus, il ne peut y avoir d' algorithme d'approximation avec un rapport d'approximation absolu inférieur à à moins que . Ceci peut être prouvé par une réduction du problème de partition : étant donné une instance de Partition où la somme de tous les nombres d'entrée est 2 T , construisez une instance de bin-packing dans laquelle la taille de casier est T . S'il existe une partition égale des entrées, alors le conditionnement optimal nécessite 2 bacs ; par conséquent, chaque algorithme avec un rapport d'approximation inférieur à 3/2 doit renvoyer moins de 3 cases, ce qui doit être 2 cases. En revanche, s'il n'y a pas de partition égale des entrées, alors l'emballage optimal nécessite au moins 3 bacs. ${\style d'affichage 3/2}$${\style d'affichage P=NP}$

D'autre part, l'emballage des bacs peut être résolu en temps pseudo-polynomial pour tout nombre fixe de bacs et en temps polynomial pour toute capacité de bac fixe . ${\style d'affichage K}$${\style d'affichage B}$

Algorithmes d'approximation pour l'emballage des bacs

Pour mesurer les performances d'un algorithme d'approximation, deux ratios d'approximation sont considérés dans la littérature. Pour une liste d'éléments donnée, le nombre indique le nombre de casiers utilisés lorsque l'algorithme est appliqué à list , tandis que indique le nombre optimal pour cette liste. Le rapport de performance absolu dans le pire des cas pour un algorithme est défini comme suit : ${\style d'affichage L}$${\style d'affichage A(L)}$${\style d'affichage A}$${\style d'affichage L}$${\displaystyle \mathrm {OPT} (L)}$${\style d'affichage R_{A}}$${\style d'affichage A}$

${\displaystyle R_{A}\equiv \inf\{r\geq 1:A(L)/\mathrm {OPT} (L)\leq r{\text{ pour toutes les listes }}L\}.}$

D'autre part, le rapport asymptotique du pire des cas est défini comme ${\displaystyle R_{A}^{\infty }}$

${\displaystyle R_{A}^{\infty }\equiv \inf\{r\geq 1:\exists N>0,A(L)/\mathrm {OPT} (L)\leq r{\text{ pour toutes les listes }}L{\text{ avec }}\mathrm {OPT} (L)\geq N\}.}$

De manière équivalente, est le plus petit nombre tel que, pour une constante K, pour toutes les listes L :${\displaystyle R_{A}^{\infty }}$

${\displaystyle A(L)\leq R_{A}^{\infty }\cdot OPT(L)+K}$.

De plus, on peut restreindre les listes à celles pour lesquelles tous les éléments ont une taille d'au plus . Pour de telles listes, les rapports de performance de taille limitée sont notés et . ${\style d'affichage \alpha }$${\displaystyle R_{A}({\text{size}}\leq \alpha )}$${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )}$

Les algorithmes d'approximation pour le conditionnement en bacs peuvent être classés en deux catégories :

1. Heuristique en ligne, qui considère les articles dans un ordre donné et les place un par un dans les bacs. Ces heuristiques sont également applicables à la version en ligne de ce problème.
2. Heuristique hors ligne, qui modifie la liste d'éléments donnée, par exemple en triant les éléments par taille. Ces algorithmes ne sont plus applicables à la variante en ligne de ce problème. Cependant, ils ont une meilleure garantie d'approximation tout en conservant l'avantage de leur faible complexité temporelle. Une sous-catégorie d'heuristiques hors ligne est constituée des schémas d'approximation asymptotique. Ces algorithmes ont une garantie d'approximation de la forme pour une constante qui peut dépendre de . Pour un nombre arbitrairement grand, ces algorithmes se rapprochent arbitrairement de . Cependant, cela se fait au prix d'une complexité temporelle (drastiquement) accrue par rapport aux approches heuristiques.${\displaystyle (1+\varepsilon )\mathrm {OPT} (L)+C}$${\style d'affichage 1/\varepsilon }$${\displaystyle \mathrm {OPT} (L)}$${\displaystyle \mathrm {OPT} (L)}$

Heuristique en ligne

Dans la version en ligne du problème de l'emballage des bacs, les articles arrivent les uns après les autres et la décision (irréversible) où placer un article doit être prise avant de connaître le prochain article ou même s'il y en aura un autre. Un ensemble diversifié d'heuristiques hors ligne et en ligne pour le bin-packing a été étudié par David S. Johnson dans le cadre de son doctorat. thèse.

Algorithmes à classe unique

Il existe de nombreux algorithmes simples qui utilisent le schéma général suivant :

• Pour chaque élément de la liste d'entrée :
  1. Si l'article rentre dans l'un des bacs actuellement ouverts, placez-le dans l'un de ces bacs ;
  2. Sinon, ouvrez un nouveau bac et placez-y le nouvel élément.

Les algorithmes diffèrent par le critère selon lequel ils choisissent le bac ouvert pour le nouvel article à l'étape 1 (voir les pages liées pour plus d'informations) :

• Next Fit (NF) conserve toujours un seul bac ouvert. Lorsque le nouvel élément ne rentre pas dans celui-ci, il ferme le bac actuel et ouvre un nouveau bac. Son avantage est qu'il s'agit d'un algorithme à espace limité, puisqu'il n'a besoin de garder qu'un seul bac ouvert en mémoire. Son inconvénient est que son rapport d'approximation asymptotique est de 2. En particulier,, et pour chacunil existe une listetelle queet. Son taux d'approximation asymptotique peut être quelque peu amélioré en fonction de la taille des éléments :pour tousetpour tous. Pour chaque algorithmequi est un algorithme AnyFit, il contient que.${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$${\displaystyle N\in \mathbb {N} }$${\style d'affichage L}$${\displaystyle \mathrm {OPT} (L)=N}$${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 2}$${\displaystyle \alpha \geq 1/2}$${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\alpha )}$${\displaystyle \alpha \leq 1/2}$${\style d'affichage A}$${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{NF}^{\infty }({\text{size}}\leq \alpha )}$
• Next-k-Fit (NkF) est une variante de Next-Fit, mais au lieu de ne garder qu'un seul bac ouvert, l'algorithme garde les derniersbacs ouverts et choisit le premier bac dans lequel l'article tient. Par conséquent, on l'appelle unalgorithme d' espace k-borné . Pourle NkF, les résultats sont améliorés par rapport aux résultats du NF, cependant, augmenterjusqu'à des valeurs constantes supérieures àn'améliore pas davantage l'algorithme dans son comportement le plus défavorable. Si l'algorithmeest unalgorithmeAlmostAnyFit,alors.${\style d'affichage k}$${\displaystyle k\geq 2}$${\style d'affichage k}$${\style d'affichage 2}$${\style d'affichage A}$${\displaystyle m=\lfloor 1/\alpha \rfloor \geq 2}$${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{N2F}^{\infty }({\text{size}}\leq \alpha )= 1+1/mois}$
• First-Fit (FF) maintient tous les bacs ouverts, dans l'ordre dans lequel ils ont été ouverts. Il essaie de placer chaque nouvel élément dans le premier bac dans lequel il tient. Son rapport d'approximation est, et il existe une famille de listes d'entréepour lesquellescorrespond cette borne.${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$${\style d'affichage L}$${\style d'affichage FF(L)}$
• Best-Fit (BF) maintient également tous les bacs ouverts, mais tente de placer chaque nouvel article dans le bac avec lacharge maximale dans laquelle il tient. Son rapport d'approximation est identique à celui de FF, c'est-à-dire :, et il existe une famille de listes d'entréepour lesquellescorrespond cette borne.${\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$${\style d'affichage L}$${\style d'affichage BF(L)}$
• Worst-Fit (WF) tente de placer chaque nouvel article dans le bac avec la charge minimale . Il peut se comporter aussi mal que Next-Fit, et le fera sur la liste des pires cas pour cela . De plus, il tient cela . Puisque WF est un algorithme AnyFit, il existe un algorithme AnyFit tel que .${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$${\displaystyle R_{WF}^{\infty }({\text{size}}\leq \alpha )=R_{NF}^{\infty }({\text{size}}\leq \alpha )}$${\displaystyle R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )}$
• Presque pire (AWF) tente de placer chaque nouvel élément dans le deuxième bac ouvert le plus vide (ou le bac le plus vide s'il y en a deux). S'il ne rentre pas, il essaie le plus vide. Il a un rapport asymptotique dans le pire des cas de .${\style d'affichage 17/10}$

Afin de généraliser ces résultats, Johnson a introduit deux classes d'heuristiques en ligne appelées algorithme tout ajustement et algorithme presque tout ajustement :

• Dans un algorithme AnyFit (AF) , si les cases non vides actuelles sont B ₁ ,..., B _j , alors l'élément actuel ne sera pas emballé dans B _{j+1 à} moins qu'il ne rentre dans aucun de B ₁ ,.. ., B _j . Les algorithmes FF, WF, BF et AWF satisfont à cette condition. Johnson a prouvé que, pour tout algorithme AnyFit A et tout :${\style d'affichage \alpha }$

${\displaystyle R_{FF}^{\infty }(\alpha )\leq R_{A}^{\infty }(\alpha )\leq R_{WF}^{\infty }(\alpha )}$.

• Dans un algorithme AlmostAnyFit (AAF) , si les bacs non vides actuels sont B ₁ ,..., B _j , et parmi ces bacs, B _k est l'unique bac avec la plus petite charge, alors l'article actuel ne sera pas emballé dans B _k , à moins qu'il ne rentre dans aucun des bacs à sa gauche. Les algorithmes FF, BF et AWF satisfont à cette condition, mais pas WF. Johnson a prouvé que, pour tout algorithme AAF A et tout :${\style d'affichage \alpha }$

${\displaystyle R_{A}^{\infty }(\alpha )=R_{FF}^{\infty }(\alpha )}$ En particulier : . ${\displaystyle R_{A}^{\infty }=1.7}$

Algorithmes raffinés

De meilleurs ratios d'approximation sont possibles avec des heuristiques qui ne sont pas AnyFit. Ces heuristiques conservent généralement plusieurs classes de bacs ouverts, consacrés à des éléments de différentes tailles (voir les pages liées pour plus d'informations):

• L'emballage de bac raffiné (RFF) divise les tailles d'articles en quatre plages :,,, et. De même, les bacs sont classés en quatre classes. L'élément suivantest d'abord affecté à sa classe correspondante. À l'intérieur de cette classe, il est affecté à un bac à l'aide de first-fit . Notez que cet algorithme n'est pas un algorithme Any-Fit puisqu'il peut ouvrir une nouvelle corbeille malgré le fait que l'élément actuel rentre dans une corbeille ouverte. Cet algorithme a été présenté pour la première fois par Andrew Chi-Chih Yao, qui a prouvé qu'il a une garantie d'approximation deet a présenté une famille de listesavecpour.${\style d'affichage (1/2,1]}$${\style d'affichage (2/5,1/2]}$${\style d'affichage (1/3,2/5]}$${\style d'affichage (0,1/3]}$${\displaystyle i\in L}$${\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5}$${\style d'affichage L_{k}}$${\displaystyle RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3}$${\displaystyle \mathrm {OPT} (L)=6k+1}$
• Harmonic-k partitionne l'intervalle de tailles enfonction d'une progression harmonique enmorceauxpourettels que. Cet algorithme a été décrit pour la première fois par Lee et Lee. Il a une complexité temporelle deet à chaque étape, il y a au plusdes bacs ouverts qui peuvent être potentiellement utilisés pour placer des éléments, c'est-à-dire qu'il s'agit d'unalgorithme d'espace borné. Pour, son rapport d'approximation satisfait, et il est asymptotiquement serré.${\style d'affichage (0,1]}$${\style d'affichage k-1}$${\displaystyle I_{j}:=(1/(j+1),1/j]}$${\style d'affichage 1\leq j<k}$${\displaystyle I_{k}:=(0,1/k]}$${\displaystyle \bigcup _{j=1}^{k}I_{j}=(0,1]}$${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$${\style d'affichage k}$${\style d'affichage k}$${\displaystyle k\rightarrow \infty }$${\displaystyle R_{Hk}^{\infty }\environ 1.6910}$
• Refined-harmonic combine des idées de Harmonic-k avec des idées de Refined-First-Fit . Il place les éléments plus grands quesimilaires comme dans Refined-First-Fit, tandis que les éléments plus petits sont placés à l'aide de Harmonic-k. L'intuition de cette stratégie est de réduire les énormes déchets pour les bacs contenant des pièces juste plus grandes que. Cet algorithme a été décrit pour la première fois par Lee et Lee. Ils l'ont prouvé caril tient cela.${\style d'affichage 1/3}$${\style d'affichage 1/2}$${\style d'affichage k=20}$${\displaystyle R_{RH}^{\infty }\leq 373/228}$

Limites inférieures générales pour les algorithmes en ligne

Yao a prouvé en 1980 qu'il ne peut y avoir d'algorithme en ligne avec un ratio concurrentiel asymptotique inférieur à . Brown et Liang ont amélioré cette limite à . Par la suite, cette borne a été améliorée par Vliet. En 2012, cette borne inférieure a de nouveau été améliorée par Békési et Galambos à . ${\style d'affichage 3/2}$${\style d'affichage 1.53635}$${\style d'affichage 1.54014}$${\displaystyle 248/161\environ 1.54037}$

Tableau de comparaison

Algorithme	Garantie approximative	Liste des pires cas ${\style d'affichage L}$	Complexité temporelle
Ajustement suivant (NF)	${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$	${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$	${\displaystyle {\mathcal {O}}(|L|)}$
Premier ajustement (FF)	${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor }$	${\displaystyle FF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor }$	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$
Meilleur ajustement (BF)	${\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor }$	${\displaystyle BF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor }$	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$
Le pire ajustement (WF)	${\displaystyle WF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$	${\displaystyle WF(L)=2\cdot \mathrm {OPT} (L)-2}$	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$
Presque pire ajustement (AWF)	${\displaystyle R_{AWF}^{\infty }\leq 17/10}$	${\displaystyle R_{AWF}^{\infty }=17/10}$	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$
Premier ajustement raffiné (RFF)	${\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5}$	${\displaystyle RFF(L)=(5/3)\mathrm {OPT} (L)+1/3}$(pour ) ${\displaystyle \mathrm {OPT} (L)=6k+1}$	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$
Harmonique-k (Hk)	${\displaystyle R_{Hk}^{\infty }\leq 1.69103}$ pour ${\displaystyle k\rightarrow \infty }$	${\displaystyle R_{Hk}^{\infty }\geq 1.69103}$	${\displaystyle {\mathcal {O}}(|L|\log(|L|)}$
Harmonique raffiné (RH)	${\displaystyle R_{RH}^{\infty }\leq 373/228\environ 1.63597}$		${\displaystyle {\mathcal {O}}(|L|)}$
Harmonique modifié (MH)	${\displaystyle R_{MH}^{\infty }\leq 538/33\environ 1.61562}$
Harmonique modifié 2 (MH2)	${\displaystyle R_{MH2}^{\infty }\leq 239091/148304\environ 1.61217}$
Harmonique + 1 (H+1)		${\displaystyle R_{H+1}^{\infty }\geq 1.59217}$
Harmonique ++ (H++)	${\displaystyle R_{H++}^{\infty }\leq 1.58889}$	${\displaystyle R_{H++}^{\infty }\geq 1.58333}$

Algorithmes hors ligne

Dans la version hors ligne de l'emballage des bacs, l'algorithme peut voir tous les articles avant de commencer à les placer dans des bacs. Cela permet d'obtenir des rapports d'approximation améliorés.

Approximation multiplicative

La technique la plus simple utilisée par les algorithmes hors ligne est :

• Classement de la liste d'entrée par taille décroissante ;
• Exécutez un algorithme en ligne sur la liste ordonnée.

Johnson a prouvé que tout algorithme AnyFit A qui s'exécute sur une liste classée par taille décroissante a un rapport d'approximation asymptotique de

${\displaystyle 1.22\approx {\frac {11}{9}}\leq R_{A}^{\infty }\leq {\frac {5}{4}}=1.25}$.

Certains algorithmes de cette famille sont (voir les pages liées pour plus d'informations) :

• First-fit-decreasing (FFD) - classe les articles par taille décroissante, puis appelle First-Fit. Son rapport d'approximation est, et celui-ci est serré.${\displaystyle FFD(I)=11/9\mathrm {OPT} (I)+6/9}$
• Next-fit-decreasing (NFD) - trie les éléments par taille décroissante, puis appelle Next-Fit . Son rapport approximatif est légèrement inférieur à 1,7 dans le pire des cas. Il a également été analysé de manière probabiliste. Next-Fit emballe une liste et son inverse dans le même nombre de bacs. Par conséquent, Next-Fit-Increasing a les mêmes performances que Next-Fit-Increasing.
• Premier ajustement-décroissant modifié (MFFD) - améliore le FFD pour les articles de plus d'un demi-bac en classant les articles par taille en quatre classes de taille grand, moyen, petit et minuscule, correspondant aux articles de taille > 1/2 bac, > 1/3 bac, > 1/6 bac et articles plus petits respectivement. Sa garantie d'approximation est.${\displaystyle MFFD(I)\leq (71/60)\mathrm {OPT} (I)+1}$

Fernandez de la Vega et Lueker ont présenté un PTAS pour l'emballage des bacs . Pour chaque , leur algorithme trouve une solution avec une taille au plus et s'exécute dans le temps , où désigne une fonction uniquement dépendante de . Pour cet algorithme, ils ont inventé la méthode de l'arrondi d'entrée adaptatif : les nombres d'entrée sont regroupés et arrondis à la valeur du maximum dans chaque groupe. Cela donne une instance avec un petit nombre de tailles différentes, qui peuvent être résolues exactement en vérifiant toutes les configurations possibles. ${\displaystyle \varepsilon >0}$${\displaystyle (1+\varepsilon )\mathrm {OPT} +1}$${\displaystyle {\mathcal {O}}(n\log(1/\varepsilon ))+{\mathcal {O}}_{\varepsilon }(1)}$${\displaystyle {\mathcal {O}}_{\varepsilon }(1)}$${\style d'affichage 1/\varepsilon }$

Approximation additive

Karmarkar et Karp ont présenté un algorithme avec un polynôme d'exécution dans et . Leur algorithme trouve une solution de taille au plus . ${\style d'affichage n}$${\style d'affichage 1/\varepsilon }$${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log ^{2}(OPT))}$

Rothvoss a présenté un algorithme qui génère une solution de taille au plus . ${\displaystyle \mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))}$

Hoberg et Rothvoss ont amélioré cet algorithme pour générer une solution de taille au plus . L'algorithme est aléatoire et son temps d'exécution est polynomial dans le nombre total d'éléments. ${\displaystyle \mathrm {OPT} +O(\log(\mathrm {OPT} ))}$

Tableau de comparaison

Algorithme	Garantie approximative	Le pire des cas
Premier ajustement décroissant (FFD)	${\displaystyle FFD(I)\leq 11/9\mathrm {OPT} (I)+6/9}$	${\displaystyle FFD(I)=11/9\mathrm {OPT} (I)+6/9}$
Diminution du premier ajustement modifié (MFFD)	${\displaystyle MFFD(I)\leq (71/60)\mathrm {OPT} (I)+1}$	${\displaystyle R_{MFFD}^{\infty }\geq 71/60}$
Karmarkar et Karp	${\displaystyle KK(I)\leq OPT(I)+O(\log ^{2}{OPT(I)})}$
Rothvoss	${\displaystyle HB(I)\leq OPT(I)+O(\log {OPT(I)}\log \log {OPT(I)})}$
Hoberg et Rothvoss	${\displaystyle HB(I)\leq OPT(I)+O(\log {OPT(I)})}$

Algorithmes exacts

Martello et Toth ont développé un algorithme exact pour le problème de bin-packing 1-D, appelé MTP. Une alternative plus rapide est l'algorithme Bin Completion proposé par Korf en 2002 et amélioré par la suite.

Une autre amélioration a été présentée par Schreiber et Korf en 2013. Le nouvel algorithme d'achèvement de bac amélioré est jusqu'à cinq ordres de grandeur plus rapide que l'achèvement de bac sur des problèmes non triviaux avec 100 éléments, et surpasse le BCP (branche-et- cut-and-price) de Belov et Scheithauer sur des problèmes qui ont moins de 20 cases comme solution optimale. L'algorithme qui fonctionne le mieux dépend des propriétés du problème telles que le nombre d'éléments, le nombre optimal de bacs, l'espace inutilisé dans la solution optimale et la précision de la valeur.

Goemans et Rothvoss ont présenté un algorithme pour le conditionnement en bacs avec d différentes tailles d'articles, où il peut y avoir plusieurs articles avec chaque taille. Leur algorithme est polynomial lorsque d est fixe et tous les nombres sont donnés en codage binaire.

Conditionnement des bacs avec contraintes de cardinalité

Il existe une variante de l'emballage des casiers dans laquelle il existe des contraintes de cardinalité sur les casiers : chaque casier peut contenir au plus k éléments, pour un entier fixe k .

• Krause, Shen et Schwetman présentent ce problème comme une variante de l'ordonnancement optimal des tâches : un ordinateur possède quelques k processeurs. Il y a quelques n tâches qui prennent un temps unitaire (1), mais ont des exigences de mémoire différentes. Chaque unité de temps est considérée comme un seul bac. L'objectif est d'utiliser le moins de casiers (=unités de temps) possible, tout en s'assurant que dans chaque casier, au plus k tâches s'exécutent. Ils présentent plusieurs algorithmes heuristiques qui trouvent une solution avec au plus des bacs.${\style d'affichage 2OPT}$
• Kellerer et Pferschy présentent un algorithme avec run-time , qui trouve une solution avec au plus des bins. Leur algorithme effectue une recherche binaire pour OPT. Pour chaque valeur recherchée m , il essaie d'emballer les articles dans des bacs de 3 m /2.${\displaystyle O(n^{2}\log {n})}$${\displaystyle \lceil {\frac {3}{2}}\mathrm {OPT} \rceil }$

Problèmes connexes

Dans le problème de l'emballage des bacs , la taille des bacs est fixe et leur nombre peut être agrandi (mais doit être le plus petit possible).

En revanche, dans le problème de partitionnement de nombres à plusieurs voies , le nombre de cases est fixe et leur taille peut être agrandie. L'objectif est de trouver une partition dans laquelle les tailles de bacs sont aussi presque égales que possible (dans la variante appelée problème d' ordonnancement multiprocesseur ou problème de fabrication minimale , le but est précisément de minimiser la taille du plus grand bac).

Dans le problème d' emballage inverse des bacs, le nombre de bacs et leurs tailles sont fixes, mais les tailles des articles peuvent être modifiées. L'objectif est d'obtenir la perturbation minimale du vecteur de taille des articles afin que tous les articles puissent être emballés dans le nombre prescrit de bacs.

Dans le problème d' emballage de casiers de ressources maximales , l'objectif est de maximiser le nombre de casiers utilisés, de telle sorte que, pour certaines commandes de casiers, aucun article d'un casier ultérieur ne rentre dans un casier antérieur. Dans un problème double, le nombre de bacs est fixe et le but est de minimiser le nombre total ou la taille totale des articles placés dans les bacs, de sorte qu'aucun article restant ne rentre dans un bac non rempli.

Dans le problème de recouvrement de bacs, la taille des bacs est bornée par le bas : le but est de maximiser le nombre de bacs utilisés de telle sorte que la taille totale dans chaque bac soit au moins un seuil donné.

Dans le problème de répartition équitable des tâches indivisibles (une variante de la répartition équitable des éléments ), les éléments représentent des tâches, et il existe différentes personnes dont chacune attribue une valeur de difficulté différente à chaque tâche. Le but est d'attribuer à chaque personne un ensemble de tâches avec une borne supérieure sur sa valeur de difficulté totale (ainsi, chaque personne correspond à un bac). De nombreuses techniques d'emballage en bacs sont également utilisées dans ce problème.

Dans le problème de la coupe à la guillotine , les articles et les "bacs" sont des rectangles bidimensionnels plutôt que des nombres unidimensionnels, et les articles doivent être coupés du bac en utilisant des coupes bout à bout.

Dans le problème égoïste de l'emballage des poubelles , chaque article est un acteur qui veut minimiser son coût.

Il existe également une variante de l'emballage des bacs dans laquelle le coût qui doit être minimisé n'est pas le nombre de bacs, mais plutôt une certaine fonction concave du nombre d'articles dans chaque bac.

D'autres variantes sont l' emballage bidimensionnel , l' emballage tridimensionnel , l' emballage avec livraison ,

Implémentations

• En ligne : visualisation d'heuristiques pour le conditionnement des bacs 1D et 2D
• Python : le package binpacking contient des algorithmes gourmands pour résoudre deux problèmes typiques de binpacking : (i) emballer des articles dans un nombre constant de bacs, (ii) emballer des articles dans un petit nombre de bacs de taille constante.
• C++ : Le package bin-packing contient divers algorithmes gloutonnes ainsi que des données de test.
• Le package OR-tools contient des algorithmes d'emballage bin en C++, avec des wrappers en Python, C# et Java.
• C : Implémentation de 7 algorithmes classiques de compactage approximatif en C avec résultats et images
• PHP : Classe PHP pour compresser des fichiers sans dépasser une limite de taille donnée
• Haskell : Une implémentation de plusieurs heuristiques d'emballage de casiers, dont FFD et MFFD.
• C : Fpart : outil en ligne de commande open-source pour compresser des fichiers (C, sous licence BSD)
• C# : Bin Packing and Cutting Stock Solver
• Java : caparf - Cadre de recherche sur les algorithmes de découpe et d'emballage , comprenant un certain nombre d'algorithmes d'emballage et de données de test.

Les références