1-dimensions de la nidification de l'algorithme

Ce qu'est un algorithme efficace pour la nidification 1 dimensions longueurs en prédéfinies longueurs de stock?

Par exemple, Si vous avez exigé des barres d'acier dans les quantités et les longueurs,

• 5 x 2 mètres
• 5 x 3 mètres
• 5 x 4 mètres

et ceux-ci peuvent être coupés à partir de 10 mètres de bars.
Comment calculer le modèle pour couper les barres de 10m de sorte que le nombre minimum de bars sont utilisés?

En outre, comment pourriez-vous intégrer plusieurs longueurs de stock dans l'algorithme?

---

J'ai eu un peu de temps pour travailler sur ce que je vais écrire comment je l'ai résolu. J'espère que ce sera utile à quelqu'un.Je ne suis pas sûr si c'est ok pour répondre à ma propre question comme ça. Un modérateur peut modifier cette une réponse, si cela est plus approprié.

D'abord merci à tous ceux qui ont répondu. Cela m'a signalé l'algorithme approprié; la coupe du stock de problème.

Cet article a aussi été utile; "Le calcul d'une coupe de liste avec le moins de hors réduire les déchets".

Ok, à la solution.

Je vais utiliser la terminologie suivante dans ma solution;

• Stock: d'une longueur de matériel qui seront coupés en petits morceaux
• Coupe: d'une longueur de matériau qui a été coupé à partir du stock. de nombreuses coupures peuvent être prises à partir de la même pièce de stock
• Des déchets: la longueur de matériau qui est laissé dans une pièce de stock après toutes les coupes ont été faites.

Il y a trois principales étapes pour résoudre le problème,

1. Identifier tous les possible de couper les combinaisons
2. Identifier les combinaisons qui peuvent être prises à partir de chaque morceau de stock
3. Trouver la combinaison optimale de coupe de combinaisons.

Étape 1

Avec N coupe, il y a 2^N-1 unique coupe combinaisons. Ces combinaisons peuvent être représentés sous forme binaire table de vérité.

Où A,B,C sont uniques coupes;

A B C | Combination
-------------------
0 0 0 | None
0 0 1 | C
0 1 0 | B
0 1 1 | BC
1 0 0 | A
1 0 1 | AC
1 1 0 | AB
1 1 1 | ABC

D'une boucle for avec certains opérateurs au niveau du bit peut être utilisé pour rapidement créer des regroupements de chaque coupe combinaison.

Cela peut-être assez de temps pour de grandes valeurs de N.

Dans ma situation, il y a plusieurs instances de la même coupe. Ce produit dupliquer des combinaisons.

A B B | Combination
-------------------
0 0 0 | None
0 0 1 | B
0 1 0 | B (same as previous)
0 1 1 | BB
1 0 0 | A
1 0 1 | AB
1 1 0 | AB (same as previous)
1 1 1 | ABB

J'ai pu exploiter cette redondance afin de réduire le temps de calculer les combinaisons. J'ai regroupé le double de l'ensemble des coupes et calculé les combinaisons uniques de ce groupe. J'ai ensuite ajouté la liste des combinaisons pour chaque combinaison unique dans un deuxième groupe pour créer un nouveau groupe.

Par exemple, avec des coupures AABBC, le processus est comme suit.

A A | Combination
-------------------
0 1 | A 
1 1 | AA

Appeler ce groupe X.

Ajouter X à des instances uniques de B,

B B X | Combination
-------------------
0 0 1 | A 
      | AA
0 1 0 | B
0 1 1 | BA
      | BAA
1 1 0 | BB 
1 1 1 | BBA
      | BBAA

Appeler ce groupe Y.

Ajoutez Y les instances uniques de C,

C Y | Combination
-----------------
0 1 | A 
    | AA
    | B
    | BA
    | BAA
    | BB 
    | BBA
    | BBAA 
1 0 | C
1 1 | CA 
    | CAA
    | CB
    | CBA
    | CBAA
    | CBB 
    | CBBA
    | CBBAA 

Cet exemple produit 17 combinaisons uniques au lieu de 31 (2^5-1). Une économie de près de la moitié.

Une fois que toutes les combinaisons sont identifiés, il est temps de vérifier comment cela s'inscrit dans le stock.

Étape 2

Le but de cette étape est de dresser la carte de la coupe combinaisons identifié à l'étape 1 pour le stock disponible tailles.

C'est un processus relativement simple.
Pour chaque coupe combinaison,

   calculate the sum of all cut lengths.
   for each item of stock, 
        if the sum of cuts is less than stock length,
            store  stock, cut combination and waste in a data structure.
            Add this structure to a list of some sort.

Le résultat sera une liste de imbriqués valides couper les combinaisons.
Il n'est pas strictement nécessaire pour stocker les déchets comme cela peut être calculée à partir des longueurs de coupe et le stock de longueur. Toutefois, le stockage des déchets réduit de traitement nécessaire à l'étape 3.

Étape 3

Dans cette étape nous permettra d'identifier la combinaison de coupes qui produit le moins de déchets. Ceci est basé sur la liste de validité des nids généré à l'étape 2.

Dans un monde idéal, nous permettrait de calculer toutes les possibilités et de choisir le meilleur. Pour tout non-trivial ensemble de coupes qu'il prendrait une éternité pour calculer tous. Nous n'aurons qu'à être satisfaits avec une non solution optimale.
Il existe plusieurs algorithmes pour la réalisation de cette tâche.

J'ai choisi une méthode qui va chercher un nid avec le moins de déchets. Il répétez cette opération jusqu'à ce que toutes les coupes ont été comptabilisés.

Commencer avec trois listes

• cutList: une liste de toutes les coupes requises (y compris les doublons).
• nestList: La liste des nids généré à l'étape 2. Ce sont triées de la plus basse des déchets à la plus élevée des déchets.
• finalList: Initialement vide, cela permettra de stocker la liste de couper les combinaisons qui seront de sortie à l'utilisateur.

Méthode

pick nest from nestList with the least waste
  if EVERY cut in the nest is contained in cutList
     remove cuts from cutList
     copy this nest into the finalList
  if some cuts in nest not in cutList
      remove this nest from nestList             
repeat until cutlist is empty

Avec cette méthode j'ai réussi à obtenir un total de déchets de l'ordre de 2 à 4% pour les données de test. J'espère que je vais obtenir de revoir ce problème à un certain point et avoir un aller à la mise en œuvre de la Retard de génération de colonnes algorithme. Cela devrait donner de meilleurs résultats.

J'espère que cela a aidé à toute autre personne ayant ce problème.

David