Databases
StackOverflow2013
Postsdbo
PO1-dimensional nesting algorithm
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO1-dimensional nesting algorithm
    primarykey
    data
    text
    <p>What is an effective algorithm for nesting 1 dimensional lengths into predefined stock lengths?</p> <p>For example, If you required steel bars in the following quantities and lengths,</p> <ul> <li>5 x 2 metres </li> <li>5 x 3 metres</li> <li>5 x 4 metres</li> </ul> <p>and these can be cut from 10 metre bars. How could you calculate the pattern for cutting the 10m bars so that the minimum number of bars are used?</p> <p>In addition, how could you incorporate multiple stock lengths into the algorithm?</p> <hr> <p>I've had a bit of time to work on this so I'm going to write up how I solved it. I hope this will be useful to someone.I'm not sure if it is ok to answer my own question like this. A moderator can change this to an answer if that is more appropriate.</p> <p>First thanks to everyone that answered. This pointed me to the appropriate algorithm; <a href="http://en.wikipedia.org/wiki/Cutting_stock_problem" rel="nofollow noreferrer">the cutting stock problem</a>.</p> <p>This post was also useful; <a href="https://stackoverflow.com/questions/22145/calculating-a-cutting-list-with-the-least-amount-of-off-cut-waste">"Calculating a cutting list with the least amount of off cut waste"</a>.</p> <p>Ok, on to the solution.</p> <p>I'll use the following terminology in my solution;</p> <ul> <li>Stock: a length of material that will be cut into smaller pieces</li> <li>Cut: a length of material that has been cut from stock. multiple cuts may be taken from the same piece of stock</li> <li>Waste: the length of material that is left in a piece of stock after all cuts have been made.</li> </ul> <p>There are three main stages to solving the problem,</p> <ol> <li>Identify all possible cut combinations</li> <li>Identify which combinations can be taken from each piece of stock</li> <li>Find the optimal mix of cut combinations.</li> </ol> <p><strong>Step 1</strong></p> <p>With N cuts, there are 2^N-1 unique cut combinations. These combinations can be represented as a binary truth table.</p> <p>Where A,B,C are unique cuts;</p> <pre><code>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 </code></pre> <p>A for-loop with some bitwise operators can be used to quickly create groupings of each cut combination.</p> <p>This can get quite time consuming for large values of N.</p> <p>In my situation there were multiple instances of the same cut. This produced duplicate combinations.</p> <pre><code>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 </code></pre> <p>I was able to exploit this redundancy to reduce the time to calculate the combinations. I grouped the duplicate cuts together and calculated the unique combinations of this group. I then appended this list of combinations to each unique combination in a second group to create a new group. </p> <p>For example, with cuts AABBC, the process is as follows.</p> <pre><code>A A | Combination ------------------- 0 1 | A 1 1 | AA </code></pre> <p>Call this group X.</p> <p>Append X to unique instances of B,</p> <pre><code>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 </code></pre> <p>Call this group Y.</p> <p>Append Y to unique instances of C,</p> <pre><code>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 </code></pre> <p>This example produces 17 unique combinations instead of 31 (2^5-1). A saving of almost half.</p> <p>Once all combinations are identified it is time to check how this fits into the stock.</p> <p><strong>Step 2</strong></p> <p>The aim of this step is to map the cut combinations identified in step 1 to the available stock sizes.</p> <p>This is a relatively simple process. For each cut combination, </p> <pre><code> 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. </code></pre> <p>This will result in a list of a valid nested cut combinations. It is not strictly necessary to store the waste as this can be calculated from the cut lengths and stock length. However, storing waste reduces processing required in step 3.</p> <p><strong>Step 3</strong></p> <p>In this step we will identify the combination of cuts that produces the least waste. This is based on the list of valid nests generated in step 2.</p> <p>In an ideal world we would calculate all possibilities and select the best one. For any non-trivial set of cuts it would take forever to calculate them all. We will just have to be satisfied with a non optimal solution. There are various algorithms for accomplishing this task. </p> <p>I chose a method that will look for a nest with the least waste. It will repeat this until all cuts have been accounted for.</p> <p>Start with three lists</p> <ul> <li>cutList: a list of all required cuts (including duplicates).</li> <li>nestList: The list of nests generated in step 2. This is sorted from lowest waste to highest waste.</li> <li>finalList: Initially empty, this will store the list of cut combinations that will be output to the user.</li> </ul> <p>Method </p> <pre><code>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 </code></pre> <p>With this method I managed to get a total waste of around 2-4% for some typical test data. Hopefully I will get to revisit this problem at some point and have a go at implementing the <a href="http://en.wikipedia.org/wiki/Delayed_Column_Generation" rel="nofollow noreferrer">Delayed column generation</a> algorithm. This should give better results.</p> <p>I hope this helped anyone else having this problem.</p> <p>David</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USDave Turvey
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. PO1-dimensional nesting algorithm
      1. USmartinus
      1. VTFavorite
    2. VO
      singulars
      1. PO1-dimensional nesting algorithm
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO1-dimensional nesting algorithm
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThis reads an awful lot like a homework question ...
      singulars
      1. PO1-dimensional nesting algorithm
      1. USNick Fortescue
    2. COmaybe it isn't homework - this is very much like an actual industrial problem i wrote a program for back around 1990
      singulars
      1. PO1-dimensional nesting algorithm
      1. USDarenW
    3. COI used a different algorithm. It's result can be seen at http://wood-cut.rhcloud.com . It does not give optimal solution, since it would require an enumerative approach but gives an acceptable solution. I have seen some softwares providing this at cost more than $50 and use Genetic Algorithm, and do not guarantee optimal solution, at times even give poorer result than http://wood-cut.rhcloud.com . I am working upon to optimize my site and will write that algorithm when I get time.
      singulars
      1. PO1-dimensional nesting algorithm
      1. USGaurav Sharma
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload