Solution du Problème N° 35 : Conditionnement des lots, ordonnancement d’atelier : un même casse-tête

Ce type de problème est connu des mathématiciens sous le nom de « Bin packing », problème proposant d’utiliser un nombre minimum de boites de capacité identique pour stocker une famille d’objets de poids ou de volumes différents.
Si on distingue l’ordre de chargement dans un même contenant, un rangement correspond au choix d’une séquence des lots à charger. Rechercher toutes les séquences pour trouver la meilleure parait illusoire. Dans notre exemple les 10 lots génèrent 10 ! = 10 × 9 × ..×2×1 = 3 628 800 rangements différents.
Compte tenu de la complexité de ce problèmes combinatoire, certaines heuristiques (règles simples fournissant une bonne solution sans assurer l’optimalité) ont été proposées. Ces règles tiennent compte de contraintes limitant le choix des solutions.
C’est le cas lorsqu’il faut charger les lots dans l’ordre de leur arrivée (on ne connaît pas les lots à venir) mais on disposent à l’instant t d’autant de camions que l’on veut, numérotés 1, 2, ...,n.
Une règle efficace est alors, dans la terminologie anglo-saxonne, la règle « Best Fit » qui préconise d’affecter le lot à ranger dans le camion dont la capacité disponible est la mieux ajustée au lot à charger.

Les lots a charger arrivent séquentiellement dans l’ordre du tableau ci-dessous et l’affectation est décrite au dessous :

Cette règle conduit à l’affectation séquentielle suivante : lot 1 camion 1, il reste 17 t disponibles pour placer le lot 2 qui laisse une capacité de 3t. Le lot 3 nécessite le chargement d’un nouveau camion ...
Il faut donc avec cette règle et cette information partielle 5 camions. On montre qu’en appliquant cette règle, bien que n’obtenant pas à coup sûr l’optimum, le nombre de camions utilisés est toujours inférieur à (11/9) ×(nombre optimal) + 1.

Dans le contexte de la situation 2 où on dispose par avance de toute l’information sur l’ensemble des lots à charger, il est alors possible d’exploiter une règle plus efficace en triant les lots de façon à placer les lots les plus encombrants en priorité. C’est la règle « First Fit Decreasing » : on trie les lots par poids décroissant et on affecte le lot à placer dans le premier camion présentant une capacité disponible suffisante. L’affectation est traduite dans le tableau suivant. Quatre camions seulement sont alors utilisés le taux de remplissage est de 100%.

On obtient ici la solution optimale. Mais répétons le, la règle ne garantit pas l’optimalité, elle permet seulement, dans le pire des cas, de ne pas dépasser 1,7 × (nombre optimal) + 2 camions.
Remarque : il est possible de trouver la solution optimal de ce type de problème en utilisant la programmation linéaire en nombres entiers.

Philippe Vallin