Parts Sorting

Hi,

I am trying to optimize the process of cutting pieces of wood of different lengths from precut planks. In other words, I would like to waste the least amount of wood after the jof is done.

Here is the example.
I need to buy "n" 12in planks
I have to cut (neglecting the 1/16 waste produced by the cutting blade):
8 pieces of 1in
5 pieces of 3in
2 pieces of 5in

The trick is to find "n" and provide a list of the pieces per plank.

I need help creating a formula, macro or VB script to sort the pieces such that I maximize the total length of the cuts with respect to the plank length.

Cheers/

This is much more difficult than you think it is.

The minimum value of n can be established by rounding up the sum of the products of the lengths divided by the plank length. So, in your example the minimum value of n would be ((8x1)+(5x3)+(2x5))/12 = (8+15+10)/12 = 33/12 = 3

The maximum value of n is just the sum of the number of lengths, in your example (8+5+2) = 15

So we know that your example will require at least 3 12" planks, but no more than 15. I appreciate that isn't very helpful.

Solving the actual problem would require an iterative approach, but this could take quite a while. If we say that c is the number of cut pieces and d is the number of different lengths then the number of possible combinations is d^c. So in your example there are 3 different lengths (1", 3" and 5") and 15 pieces required, so there are 3^15 unique arrangements, which is 14,348,907.

Unfortunately in cases like this the only straightforward way for a computer to find the optimal combination is to try each one and compare it to all of the others, which is rather time consuming. The example you've given would probably take 30-60 seconds to calculate on a reasonably up-to-date desktop PC, if you've picked a simple example to start us off on then more complex calculations would take exponentially longer (for example, cutting 20 pieces of 5 different lengths has more than 95 billion unique cutting combinations).

I appreciate all of this waffle doesn't help you too much, but it might stop you spending too much time trying to work out a computerised solution to this one.

You could use Excel's Add-Ins Solver. It's not installed by default when Excel is installed. To install Solver go to "Tools"-> "Add-Ins" and tick the box marked "Solver".

If there is no box marked "Solver" select "Browse" normally you will find it under C:\Program Files\Microsoft Office\OFFICE11\Library\SOLVER
and the file you need is the "Solver.xla" file. Occasionally when you browse the browser is set for finding .dll files and then you will not find "Solver.xla". In this case change format to *.*

I've set up a Solver model for you but you need to have Solver installed if you want to test the model.

Alf