Découpe linéaire. Problème de découpe unidimensionnelle

Découpe unidimensionnelle de barres avec types de profil, stock limité et largeur de coupe. Plan pour chaque barre, chutes, utilisation du matériau et deux objectifs d'optimisation.

Cette page existe grâce aux efforts des personnes suivantes :

Timur

Timur

Créé: 2026-11-22 12:35:51, Dernière mise à jour: 2026-11-22 14:08:09

La découpe linéaire consiste à répartir des pièces sur des barres, des armatures, des tubes ou d'autres matériaux de longueur donnée. Les pièces peuvent être permutées : ce qui compte n'est pas leur position initiale dans la liste, mais celles qu'il convient de découper dans une même barre.

Le calculateur ci-dessous établit un plan pour plusieurs types de profil, tient compte des quantités disponibles et de la largeur de coupe, puis indique la chute de chaque barre. Vous pouvez supprimer les valeurs par défaut, qui servent uniquement d'exemple. Les formules et un peu de théorie se trouvent sous le calculateur.

PLANETCALC, Découpe linéaire de barres

Découpe linéaire de barres

Matériau de départ

Type de profilLongueurQuantité
objets par page:

Pièces

Type de profilLongueurQuantité
objets par page:

À égalité du critère principal, le plan ayant le meilleur critère secondaire est sélectionné.
Longueur supplémentaire réservée à chaque pièce placée ; dans les mêmes unités que les longueurs des tableaux.
État
 
Barres utilisées
 
Pièces placées
 
Total des pièces
 
Longueur du matériau utilisé
 
Longueur des pièces placées
 
Largeur de coupe totale
 
Chutes totales
 
Utilisation du matériau, %
 
Borne inférieure du nombre de barres
 
Le fichier est très volumineux; un ralentissement du navigateur peut se produire pendant le chargement et la création.
Le fichier est très volumineux; un ralentissement du navigateur peut se produire pendant le chargement et la création.
Le fichier est très volumineux; un ralentissement du navigateur peut se produire pendant le chargement et la création.
Le fichier est très volumineux; un ralentissement du navigateur peut se produire pendant le chargement et la création.

Matériau de départ, pièces et profils

Le matériau de départ est la barre initiale, et une pièce est le morceau à obtenir. Les tableaux utilisent les champs suivants :

  1. Type de profil désigne le matériau ou le produit laminé, par exemple « Armature A500C ». Une pièce ne peut être placée que sur un matériau ayant le même type de profil. Il ne faut pas mélanger une armature en acier et un tube en aluminium dans un même plan, même si leurs longueurs se combinent convenablement.
  2. Longueur est la longueur du matériau ou de la pièce. Toutes les longueurs doivent utiliser les mêmes unités : si le mètre est choisi, 80 centimètres s'écrivent 0,8.
  3. Quantité est le nombre de positions identiques. Le calculateur la développe en pièces ou barres individuelles ; une ligne « longueur 3, quantité 2 » signifie donc deux pièces de longueur 3.

Une chute est la partie d'une barre utilisée qui n'est devenue ni une pièce ni une perte de coupe. Elle peut encore servir ; il n'est donc pas toujours correct de la considérer comme un déchet irrécupérable. Les barres inutilisées ne sont pas du tout comptées parmi les chutes.

Un exemple avec deux barres

Supposons que nous disposions d'une barre de 12 mètres et d'une barre de 9 mètres. Nous avons besoin de quatre pièces : 8, 7, 4 et 2 mètres.

Un plan complet se présente ainsi :

Matériau Pièces Chute
12 m 8 + 4 m 0 m
9 m 7 + 2 m 0 m

La longueur totale des pièces est de 21 mètres, exactement celle du matériau utilisé. L'utilisation du matériau est de 100 %. Il s'agit de l'exemple par défaut du calculateur, mais une chute nulle n'est évidemment pas promise pour d'autres données.

Pourquoi tenir compte de la largeur de coupe

Lors du sciage, une petite partie du matériau se transforme en copeaux. Cette largeur est appelée largeur de coupe (kerf). Si on l'ignore, un beau plan à l'écran peut ne pas tenir sur une barre réelle.

Le calculateur applique une règle prudente : une largeur de coupe est réservée pour chaque pièce. Si des pièces de longueur L_1,\ldots,L_n sont placées sur une barre et que la largeur de coupe est k, la longueur occupée est

U=\sum_{i=1}^{n}L_i+nk

où n est le nombre de pièces sur la barre. Le plan n'est réalisable que si U\leq L, où L est la longueur du matériau. La chute est calculée comme suit :

R=L-U

Pourquoi nk et non (n-1)k ? La règle n-1 convient lorsqu'une barre est entièrement divisée en n morceaux. Mais s'il reste une chute après la dernière pièce, celle-ci doit encore en être séparée. Pour ne pas introduire d'exception cachée en cas d'égalité exacte des longueurs, le calculateur réserve toujours une coupe par pièce.

Par exemple, deux pièces de 5 mètres avec une largeur de coupe de 1 mètre nécessitent 12 mètres au lieu d'une barre de 10 mètres. Un tel plan demande deux barres, si elles sont disponibles.

Ce qui est exactement optimisé

Le mot « optimisation » a ici deux sens différents. On peut utiliser moins de barres ou laisser moins de matériau sur les barres utilisées. Ces objectifs ne coïncident pas toujours.

Supposons qu'il y ait une barre de 12 mètres et deux de 5 mètres, et que deux pièces de 3 mètres soient nécessaires :

  1. Nombre minimal de barres. Les deux pièces tiennent sur une barre de 12 mètres. La chute est de 6 mètres, mais les deux barres courtes restent intactes.
  2. Minimum de chutes totales. Chaque pièce est placée sur sa propre barre de 5 mètres. Deux barres sont utilisées, mais les chutes totales ne sont que de 4 mètres.

C'est pourquoi le calculateur permet de choisir l'objectif. Par défaut, le minimum de chutes est sélectionné. À égalité du critère principal, le critère secondaire est utilisé : on compare d'abord les chutes totales ou le nombre de barres, puis inversement.

Pour évaluer le résultat, l'utilisation du matériau est utile : c'est la part de la longueur des pièces finies dans la longueur du matériau utilisé :

\eta=\frac{\sum_i \ell_i}{\sum_b L_b}\cdot100\%

où \ell_i est la longueur de la i-ème pièce et L_b la longueur de la b-ème barre utilisée. La largeur de coupe n'entre pas au numérateur. Par conséquent, l'utilisation du matériau, la part des coupes et la part des chutes totalisent 100 %.

Pourquoi ne peut-on pas simplement promettre le meilleur plan

Il s'agit d'un problème de découpe unidimensionnelle (one-dimensional cutting-stock problem), proche du problème de bin packing. Dans sa formulation classique, un ensemble donné d'objets doit être placé dans un nombre minimal de conteneurs identiques. Notre problème tient compte en outre de matériaux de longueurs différentes, de quantités limitées et de la compatibilité des profils.

Même le bin packing classique est NP-difficile.1 Cela ne signifie pas qu'une réponse exacte soit impossible. Pour un petit ensemble, on peut énumérer les variantes ; les grands problèmes sont résolus par programmation en nombres entiers et génération de schémas de découpe.2 Mais un tel solveur exact exigerait des limites spécifiques et une implémentation beaucoup plus complexe.

Le calculateur utilise des heuristiques — des règles qui construisent rapidement un bon plan sans démontrer son optimalité. Le résultat doit donc être compris comme « le meilleur plan trouvé » et non « le meilleur de tous les plans possibles ».

Fonctionnement de l'algorithme

Le problème est d'abord séparé par type de profil. Ce n'est pas une approximation : une pièce ne peut de toute façon pas passer sur un matériau d'un autre profil. Ensuite, quatre variantes de construction sont exécutées pour chaque profil :

  1. pièces par longueur décroissante ou croissante ;
  2. à l'ouverture d'une nouvelle barre, d'abord la plus courte appropriée ou d'abord la plus longue appropriée.

Pour la pièce suivante, la règle du meilleur ajustement (best fit) choisit la barre déjà ouverte où il restera le moins de place après le placement. Si aucune ne convient, une autre barre inutilisée est ouverte.

Les plans obtenus sont ensuite améliorés localement :3

  1. Suppression d'une barre. L'algorithme essaie de déplacer ses pièces vers d'autres barres déjà utilisées. S'il réussit, la barre est libérée.
  2. Permutations. Si un simple déplacement ne suffit pas, l'algorithme essaie un nombre limité d'échanges de pièces et recommence la suppression.
  3. Remplacement du matériau. Si le même groupe de pièces tient sur une barre inutilisée plus courte du même profil, le remplacement est effectué.

Il ne reste qu'à comparer les variantes selon l'objectif choisi. Il n'y a ici aucun essai aléatoire : un nouveau calcul avec les mêmes données donne le même plan.

Borne inférieure du nombre de barres

Pour un profil, la longueur totale des pièces peut être divisée par la plus grande longueur de matériau disponible, puis arrondie à l'entier supérieur :

B_0=\left\lceil\frac{\sum L_i}{L_{\max}}\right\rceil

où B_0 est la borne inférieure du nombre de barres et L_{\max} la longueur maximale disponible pour ce profil. Les bornes des profils sont additionnées.

Cette borne est volontairement simple : elle ne tient compte ni de la largeur de coupe, ni des limites de quantité, ni des combinaisons de longueurs défavorables. Si le plan trouvé utilise exactement B_0 barres, leur nombre est démontré minimal. Cela ne prouve pas que les chutes soient minimales.

Comment lire le résultat

Le plan de découpe contient une ligne par barre utilisée. L'inscription « 8 + 4 » signifie deux pièces des longueurs correspondantes ; leur ordre de découpe ne modifie pas la consommation de matériau. Chaque ligne rappelle la longueur des pièces, la réserve de coupe, la chute et l'utilisation du matériau.

Le résumé par profil aide à vérifier la répartition entre les types de matériau. Matériau non utilisé indique le stock restant. Si aucun plan complet n'est trouvé, le tableau Pièces non placées énumère ce que l'algorithme n'a pas pu placer.

Qu'est-ce que cela signifie en pratique ? Le matériau est peut-être réellement insuffisant, ou une pièce est plus longue que toute barre appropriée. Mais un autre cas est possible : l'heuristique n'a pas trouvé un plan existant. Par conséquent, « aucun plan complet n'a été trouvé » ne prouve pas que la découpe soit impossible.

Limites d'application

  1. L'optimalité n'est pas garantie. La faisabilité du plan et tout le bilan des longueurs sont vérifiés, mais pas le caractère minimal du résultat parmi tous les plans possibles.
  2. Les profils ne sont pas mélangés. Leurs noms sont comparés exactement, y compris la casse. Remplacer un matériau par un autre exige une décision technique distincte, et non une règle de rangement.
  3. Les pièces ne sont pas divisées. Chaque pièce doit tenir entièrement sur une seule barre.
  4. Les nouvelles chutes ne deviennent pas automatiquement du matériau de départ. Pour les utiliser dans un travail ultérieur, ajoutez manuellement les chutes appropriées au tableau du matériau.
  5. Limites de saisie. Jusqu'à 100 barres et 100 pièces après développement des quantités sont prises en charge, avec six décimales au maximum. Il s'agit d'une limite du calcul dans le navigateur, et non d'une propriété du problème.
  6. Seule la longueur est prise en compte. Le coût d'achat, la coupe des extrémités, les dispositifs de serrage, la chute utile minimale, l'ordre des opérations de la machine et le temps de coupe ne font pas partie du modèle.

Si la largeur et la hauteur de rectangles sont données au lieu d'une longueur, il s'agit d'un autre problème. Pour cela, utilisez le calculateur de bin packing bidimensionnel. Pour des conteneurs identiques, sans profils ni plan pour chaque barre, les calculateurs Problème de bin packing et Problème de bin packing 2 peuvent être utiles.


  1. Richard E. Korf. A New Algorithm for Optimal Bin Packing. AAAI 2002. Définitions du problème, heuristiques et complexité. Article. ↩

  2. P. C. Gilmore, R. E. Gomory. A Linear Programming Approach to the Cutting-Stock Problem. Operations Research, 1961. Schémas de découpe et génération de colonnes. Article. ↩

  3. A. C. F. Alvim, C. C. Ribeiro, F. Glover, D. J. Aloise. A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics, 2004. Un exemple de combinaison de la construction et de l'amélioration locale des plans. Article. ↩

URL copiée dans le presse-papiers
PLANETCALC, Découpe linéaire. Problème de découpe unidimensionnelle

commentaires