Nous utilisons Google OR-Tools pour modéliser le cutting stock comme un problème d'affectation / bin-packing optimisé. OR-Tools permet d'exprimer des contraintes (longueurs disponibles, quantités demandées, orientations, tolérances) et d'optimiser un objectif (minimiser le nombre de supports ou la longueur totale utilisée).
Nous combinons des méthodes exactes et heuristiques : génération de motifs (patterns), relaxation en PL, et recherche locale pour améliorer les solutions rapidement sur des instances industrielles. Cela donne de très bons compromis entre qualité et temps de calcul.
Après résolution, l'optimiseur génère des schémas de découpe (patterns) montrant quelles pièces vont sur quel support, ainsi que la longueur totale utilisée et la chute restante.
Minimiser le nombre de supports utilisés et réduire la chute totale.
Liste de patterns (ex. : {1200,1200,1200,1200,1200} sur 5 pièces) et la chute associée pour chaque support.
Ce logiciel est en cours de développement et n'inclut pas encore l'exploitation des chutes.
Le solveur s'appuie sur les capacités de programmation linéaire et de recherche par contraintes d'OR-Tools. Selon la taille de l'instance, nous générons d'abord des patterns par heuristique, puis nous résolvons un problème maître restreint pour combiner ces patterns de façon optimale. Des améliorations locales (ex. réaffectation entre patterns) sont ensuite appliquées si nécessaire.