Calculer une liste de coupe avec le moins de déchets coupés

Question

Je travaille sur un projet où je produis une liste de découpe d'extrusion d'aluminium.

Les extrusions d'aluminium sont disponibles en longueurs de 5 m.

J'ai une liste de longueurs plus petites qui doivent être coupées dans les longueurs de 5 m d'extrusions d'aluminium.

Les plus petites longueurs doivent être coupées dans l'ordre qui produit le moins de déchets coupés à partir des longueurs de 5 m d'extrusions d'aluminium.

Actuellement, j'ordonne la liste de coupe de telle manière que généralement la plus longue des plus petites longueurs soit coupée en premier et la plus courte des plus petites longueurs soit coupée en dernier.L'exception à cette règle est que lorsqu'une longueur plus courte ne rentre pas dans ce qui reste de la longueur de 5 m d'extrusion d'aluminium, j'utilise la longueur la plus longue et la plus courte qui conviendra.

Cela semble produire une liste de coupe très efficace (très peu de déchets coupés) et ne prend pas longtemps à calculer.J'imagine cependant que même si la liste de coupe est très efficace, ce n'est pas nécessairement le la plupart efficace.

Quelqu'un connaît-il un moyen de calculer la liste de coupe la plus efficace qui puisse être calculée dans un laps de temps raisonnable ?

MODIFIER:Merci pour les réponses, je vais continuer à utiliser l'approche "gourmande" car elle semble faire un très bon travail (surpasse toutes les tentatives humaines pour créer une liste de coupe efficace) et est très rapide.

Answer 1

Il s’agit d’un problème classique et difficile à résoudre efficacement.L'algorithme que vous décrivez ressemble à un Algorithme gourmand.Jetez un œil à cet article Wikipédia pour plus d’informations : Le problème du matériel de coupe

Answer 2

Je crains qu'il n'y ait pas d'idées spécifiques sur ce problème, mais vous pourriez vous pencher sur un 'algorithme génétique' (ce qui irait quelque chose comme ça)...

Placez les longueurs à couper dans un ordre aléatoire et attribuez à cet ordre une note en fonction de sa correspondance avec votre solution idéale (0 % de déchet, vraisemblablement).

Ensuite, apportez de manière itérative des modifications aléatoires à l’ordre et réévaluez-le.Si le score est plus élevé, abandonnez le résultat.Si le score est inférieur, conservez-le et utilisez-le comme base pour votre prochain calcul.Continuez jusqu'à ce que vous obteniez votre score dans des limites acceptables.

Answer 3

Ce que vous décrivez est en effet classé comme un Matériel de coupe problème, comme Wheelie mentionné, et non un Emballage des bacs problème car vous essayez de minimiser les déchets (somme des restes) plutôt que le nombre d'extrusions utilisées.

Ces deux problèmes peuvent être très difficiles à résoudre, mais l'algorithme de « meilleur ajustement » que vous avez mentionné (utilisant la « petite longueur » la plus longue qui correspond à l'extrusion actuelle) est susceptible de vous donner de très bonnes réponses avec une très faible complexité.

Answer 4

En fait, puisque la taille du matériel est fixe, mais que les demandes ne le sont pas, c'est un problème d'emballage des bacs.

Encore, Wikipédia à la rescousse !

(Quelque chose que je devrai peut-être aussi examiner pour le travail, alors oui !)

Answer 5

C'est un problème intéressant car je suppose que cela dépend de la quantité de chaque longueur que vous produisez.S'ils sont tous de la même quantité et que vous pouvez obtenir chaque longueur différente sur une extrusion de 5 m, vous avez alors la solution optimale.

Cependant, s'ils ne tiennent pas tous sur une seule extrusion, vous avez un problème plus grave.Pour conserver le même nombre de coupes pour chaque longueur, vous devez calculer le nombre de longueurs (pas nécessairement dans l'ordre) qui peuvent tenir sur une extrusion, puis passer dans un ordre à travers chaque extrusion.

Answer 6

J'ai également eu du mal avec ce problème précis (la longueur de mon problème est de 6 m).

La solution sur laquelle je travaille est un peu moche, mais je ne me contente pas de votre solution.Laisse-moi expliquer:

Taille des stocks 5 m

Doit être coupé en tailles (1 de chaque) :

**3,5

1

1,5**

Votre solution :

3,5 | 1 avec un gaspillage de 0,5

1,5 avec un reste de 3,5

Vous voyez le problème ?

La solution sur laquelle je travaille -> Force brute

1 - Testez toutes les solutions possibles

2 - Trier la solution par leurs déchets

3 - Choisissez la meilleure solution

4 - Supprimez les éléments de la solution de "l'Univers"

5 - Aller à 1

Je sais que ça prend du temps (mais je prends 1h30 pour déjeuner...donc...:) )

J'ai vraiment besoin de la solution optimale (je fais une solution presque optimale à la main (+-) dans Excel) non seulement parce que je suis obsédé, mais aussi parce que le produit n'est pas bon marché.

Si quelqu'un a une meilleure solution simple, je l'aimerais