How Can I Efficiently Cut Wood Boards of Different Lengths?

[droobilicious]

Hi,

New to this forum so sorry if i am not posting in the right place.

I have a problem, I need to cut a number of pieces of wood to certain lengths (the width and depth are standard and not relevant here). I know the number and lengths of all the lengths I need, but i can only buy the wood in boards of 2400mm or 1800mm. What I would like to do is find the number of boards of each length that i need to buy, and how to cut them in the most efficient way. I would like to write a function to do this and and competent at coding but do not know how the logic of the function should work. I'd also like to try and generalize the function to work for any input sizes and quantities and any given board that can be purchased.

Here's my example:I want to create the following board quantities and lengths:

8 x 2060mm
14 x 450mm
2 x 458mm
4 x 283mm
2 x 197mm
2 x 486mmI can only purchase 2400mm or 1800mm length boards from which i must cut the above lengths.My only thought so far is to first arrange the boards into every possible combination, then line each order up against the 2400mm and 1800mm boards to see which uses least/produces least waste. There are 32 boards so i believe this gives me 32! positions that they could be in. This is obviously too large to do anything with. Clearly there are a lot of positions that i don't care about, for example it doesn't matter which of the 14 boards that are 450mm is at a given position in the order. It doesn't matter about orders that are the reverse of another order etc.

This way seems very inefficient and at the end still wouldn't identify any solutions that are more efficient by using only the shorter boards to cut from etc.Looking for any help you can give me to get my head around this problem.

If anyone wants to get really crazy then there is a per meter price difference

14.78 GBP for 2400 making 6.16 GBP/meter
11.82 GBP for 1800 making 6.57 GBP/meterIt would be great to figure out the function that gives the most efficient option in terms of price also.If I'm totally in the wrong place please feel free to point my in the right direction.

Thanks in advance
Droobilicious

 

[Opalg]

I want to create the following board quantities and lengths:

8 x 2060mm
14 x 450mm
2 x 458mm
4 x 283mm
2 x 197mm
2 x 486mm

Hi Droobilicious, and welcome to MHB!

I think that common sense will work better than fancy mathematics for this problem. To start with, each of your eight 2060mm lengths will require a 2400mm board, leaving eight leftover lengths of 340mm. You can use six of those leftover pieces to supply the four 283mm lengths and the two 197mm lengths. (The other two leftover lengths of 340mm are no good for any of your requirements and will have to be junked.)

That leaves you with the following board quantities and lengths:

14 x 450mm
2 x 458mm
2 x 486mm

At this point you should notice that 1800 = 4x450. So theoretically you could get four 450mm lengths from a single 1800mm board. In practice, I doubt whether that would work, because you would be bound to lose a few millimetres when making the saw cuts. However, you can comfortably cut three of any of the above lengths (450, 458 or 486mm) from an 1800mm board, and you can get five of any of those lengths from a 2400mm board. Altogether, you need 18 (14 + 2 + 2) of these lengths. Since 18 = 3x5 + 1x3, it looks as though your best bet would be to get three 2400mm boards and one 1800mm board (in addition to the eight 2400mm boards needed for the 2060mm pieces). So the total requirement would be for eleven 2400mm boards and one 1800mm board.

If you decide to go for four 450mm lengths from an 1800mm board, then you could get 12 of the 450mm lengths from three 1800mm boards. That would still leave you with the following board quantities and lengths:

2 x 450mm
2 x 458mm
2 x 486mm

For that, you would need another two 1800mm boards, giving a total requirement of eight 2400mm boards and five 1800mm boards.

 

[droobilicious]

Hi Opalg

Thanks very much for your reply. I believe you are probably right that some common sense and some trial and error are in order for this specific problem, I am sure that's what I will end up using and your reply will help very much with this.

As a bit a purist I am very much interested in what the maths behind an "ideal" solution would be because I have seen other applications for this maths. I could be wrong because I am in no way a mathematician but i think the problem boils down to a "bucket sort" function. I am also interested in the base problem of how you list all permutations that the cuts could be sorted into (the 32!) and then how you mathematically rule out the logically similar sorts (where the sort puts 2 different cuts of the same measurements in the same place, or the order is the exact reverse of another iteration etc).

Anyways, I guess i don't really have time to think about that now because these are the wood cuts needed to create an entertainment center to protect by material lined speakers from the kittens we just got, lol!

Thanks again, really appreciate your time

Droobilicious

 

[droobilicious]

As a follow up, here's the cuts. I laid them out pretty much as I could fit them on the 2.4m boards and then the leftovers on the 1.8. Worked out exactly as you said ;)

View attachment 7246

Thanks again

 

[I like Serena]

Heh. If I'm not mistaken, you're basically saying that in real life we are happy with a solution that does the job and that is not too expensive.
And indeed that's pretty much what it is all about.
If it is too expensive, we can try and see if we can optimize it a bit.
And certainly, some knowledge about applied mathematics and computer programming can certainly assist there.
But let's keep that as a backup option, when all else fails or is not good enough.