Comment fonctionne un optimiseur de découpe

Ranger des rectangles dans d’autres rectangles en perdant le moins de place possible. C’est tout. Ça ressemble à un jeu, et pourtant les mathématiciens s’y cassent les dents depuis les années 1960.

Le nom savant est le problème de découpe en deux dimensions, et il est NP-difficile. Traduction en français : le nombre de dispositions possibles explose avec le nombre de pièces, à un rythme que rien ne rattrape.

À quel point ? Prenons trente pièces. Rien qu’en comptant les ordres dans lesquels on peut les poser, on obtient 30 factorielle — un nombre à 33 chiffres. Plus que le nombre d’étoiles dans l’univers observable. Et ce n’est que l’ordre : à chaque pièce, il faut encore décider où la mettre et dans quel sens.

Aucune machine ne peut toutes les essayer. Aucun outil ne garantit donc l’optimum absolu, et méfiez-vous de celui qui l’affirmerait. Ce qu’on cherche, c’est une très bonne solution en un temps qui permet de recalculer dès qu’une cote change — quelques centaines de millisecondes.

Avant de placer quoi que ce soit, l’optimiseur doit intégrer trois réalités physiques. Ce sont elles qui séparent un vrai plan de coupe d’un joli dessin.

Un : le panneau n’est pas à ses cotes. Il faut déligner le pourtour avant de s’en servir.

Deux : la lame mange. Chaque coupe emporte 2 à 4 mm, à déduire entre deux pièces voisines — et à chaque fois, pas une seule.

Trois : la coupe traverse. C’est la contrainte guillotine, et elle mérite sa propre section plus bas.

Un optimiseur qui néglige l’une des trois affiche des taux de chute flatteurs et produit des plans inexécutables. C’est le premier critère pour juger un outil.

1. 1

   Réduire les cotes à ce qui sera découpé

   Les chants sont déduits ou ajoutés selon la convention choisie, et le panneau perd son délignage sur tout le pourtour. L’optimiseur ne travaille jamais sur les cotes finies : il travaille sur les cotes de coupe.

2. 2

   Trier les pièces, de plusieurs façons

   Par surface décroissante, par plus grand côté, par périmètre : chaque ordre donne un plan différent, et aucun n’est meilleur en toutes circonstances. L’optimiseur les essaie tous.

3. 3

   Placer en coupes traversantes

   Chaque pièce est posée dans un espace libre, qui se scinde alors en deux rectangles — trait de scie déduit. C’est le placement guillotine : il garantit un plan exécutable sur une scie à panneaux.

4. 4

   Choisir les formats à commander

   Pour chaque matériau, l’outil essaie les formats déclarés, garde la feuille la mieux remplie au meilleur coût, retire les pièces placées, et recommence. C’est ainsi qu’un panachage de deux formats peut battre un format unique.

5. 5

   Améliorer ce qui a été trouvé

   Une passe reprend les pièces mal placées et tente de les déplacer vers des espaces plus adaptés, tant que le résultat s’améliore. C’est la différence entre un premier jet correct et un plan serré.

6. 6

   Comparer et présenter

   Les meilleures dispositions sont évaluées sur quatre critères — coût, traits de coupe, surface de chutes, plus grande chute — puis proposées côte à côte. La décision revient à celui qui paie la matière.

Sans elle, on pourrait poser les pièces n’importe où et remplir davantage. Ça existe, ça s’appelle le nesting, et c’est ce qu’on fait au laser, au jet d’eau ou à la fraiseuse numérique — des machines qui attaquent la matière en n’importe quel point.

Une scie à panneaux, elle, ne sait faire qu’une chose : traverser de part en part. Chaque coupe sépare le panneau en deux morceaux, et chaque morceau se recoupe de la même façon, récursivement.

Le placement de gauche est plus compact. Il est aussi impossible : pour extraire la pièce du milieu, il faudrait s’arrêter en pleine matière.

Un optimiseur honnête accepte donc cette contrainte, quitte à afficher un taux de chute moins flatteur qu’un outil qui l’ignore. Le vrai gâchis, ce n’est pas 2 % de matière perdue : c’est un plan qu’on ne peut pas couper, découvert le samedi matin au magasin.

C’est la partie la plus contre-intuitive du calcul, et c’est celle qui fait la différence entre un résultat correct et un bon résultat.

On pourrait croire qu’il existe un bon ordre — commencer par les grandes pièces, par exemple, ce qui marche souvent. Mais « souvent » n’est pas « toujours », et l’ordre optimal dépend de la forme précise de votre débit.

Cette stratégie porte un nom : on parle d’heuristiques — des méthodes qui ne prouvent rien mais qui trouvent vite. Les essayer toutes et comparer coûte quelques millisecondes de plus, et gagne régulièrement un panneau.

C’est l’étape que beaucoup d’outils sautent, et elle vaut souvent plus que l’optimisation du placement lui-même.

Votre fournisseur ne vend pas un format, il en vend plusieurs — 2800 × 2070, 2500 × 1250, des demi-panneaux. Chacun a son prix et sa surface. Le réflexe naturel, « je prends le plus grand », est bon quand vos pièces sont grandes et mauvais quand elles ne le sont pas : un grand panneau à moitié utilisé coûte plus cher que deux petits bien remplis.

L’optimiseur procède donc en boucle : pour chaque matériau, il essaie chaque format disponible, garde la feuille la mieux remplie au meilleur coût, retire les pièces qui y tiennent, et recommence avec ce qui reste. Le panachage émerge tout seul de ce raisonnement.

Sur le projet d’exemple, ce mécanisme fait 34 € de différence pour le même nombre de panneaux — voir combien de panneaux pour mon projet.

Il faut aussi dire ce qu’un optimiseur ignore, parce que c’est là que votre jugement reprend la main.

Il ne connaît ni l’état de votre lame, ni le voile de vos panneaux, ni le fait que vous préférez couper les grandes pièces en premier pour manipuler moins de matière. Il ne sait pas que votre scie a une capacité de coupe de 1300 mm, ni que le magasin refuse les pièces de moins de 200 mm.

Il ne sait pas non plus qu’une chute de 800 mm vous rendra service le mois prochain — sauf si vous le lui dites, en réglant le seuil de chute réutilisable.

C’est exactement pour cette raison que le résultat se présente comme plusieurs propositions chiffrées plutôt que comme une réponse unique. La machine trie ; l’atelier décide. Un outil qui vous impose une seule solution vous cache un arbitrage qui vous appartient.

Les contraintes physiques évoquées ici ont chacune leur guide : le trait de scie, le sens du fil, et le délignage dans le guide du calepinage.

Et pour la question qui suit naturellement — que faire de ce que le plan laisse —, que faire de ses chutes explique pourquoi la forme des chutes compte autant que leur surface.