hi people,
was wondering if you could tell me what would be the best thing to do for creating something to calculate the best way to cut a full length piece of wood int different, smaller lengths so as to have the smallest amount of waste. ie. say we have 50 lengths a 4.8m and 50 at 3.6m and we need to cut 4 at 2.3m, 4 at 1.8m and 16 at 1.7m and obviously all the off cuts would be avalaible to be used again. please help because its hurting my head!

thanks,

Iain

right off the bat, I can see that cutting 2 3.6 meter lenths in 1/2 gives you the 4 1.8m lengths you need.


Use that to reduce your problem.



now. IMO
The best solution would be to use the 4.8 lengths to create the 2.3m lengths, then create the 16 1.7m from the 3.6 meter lentgths


total waste: 2 meters

thanks, now what i need is some sort of program to actually do those calculations but for say 100 different lengths form 5 different starting lengths, you see my problem now? currently we are able to work for the current building (this is for making garden sheds btw) and maybe the next one, but i would like to be able to work atleast a week in advance to reduce waste. its a very difficult problem to do mentally so i'm hoping a computer with its ability to do repeatitive boring sums over and over again without needing a break or 12 hours will solve the problem


thanks people,

Iain

Yeesh! what an algorithm to create


You could always do it the ugly way and go through all the permutations.



But basically you have two sets of input, and you have to find a best match between them.


Hrm, I'll go poke at my linear book later, maybe this could be solved using a least squares method.... I dont know

its a good one isn't it, i woud be happy to settle for trying every combanation, but i cant even get my head round how to set that out.

now your actual full blown algorythms sound interesting, cant wait to see what you come up with, i'm gonna continue to sit with brain freeze over the idea.

thanks

Iain

everyones stumped!

i'm starting to think its more and more impossible, i only want to do it by going through every permutation but even at that its extremely hard.

ok lets call the full length z and each of the others a b c etc

you take z and take as many of a's as you can, then with whats left over you take as many b's as you can and so on until the bit left over is too short for anything, then take the last bit you cut and un cut it, then see if whats left over from that divides up better with whats required,

then say that makes a k and a longer bit left over you still have the possibility of a j bit fitting and having a small bit left over, then basically work all the way back untill you've done it every7 possible way and keep track of the best

now all that does is find the best way to divide up one length of wood into any number of the rquired lengths and doesnt take into consideration that you may only want 1 b,

please help if this is an easy one for you

It sounds to me like this is an NP-complete problem, specifically the bin packing problem. The upshot of this is that you should expect it to be difficult to find an optimal solution for a sufficiently large number of inputs in a reasonable amount of time. However, as the link above notes, you can approximate the optimal solution using some of the heuristics it suggests. Take a look at that page and see if it sparks any ideas. Think of the lengths from which you want to cut as the bins, and the actual pieces you want to end up with as the objects. Your problem is muddied a little bit by having multiple bin sizes, but I suspect that shouldn't make much of a difference.

thats great thanks, but boy does that hurt your head! the multiple sizes of bins are ok i can either make some have bits at the bottom that doesnt get counted to pad them up or use a while loop to go through all the bins, but if i can get it to work with just one size i'll be just about happy.

thanks again for the great input

Regards, Iain