1

Hello,

I am trying to make a software for a sawmill. I have a list of boards that I will have to obtain and the diameter of the log that I have to cut.

The algorithm is relatively simple. I try to make a prism in the center of the log, then depending on the space that remains I try to put other boards. The problem is that I don't know what boards should I put to minimize losses.

I think I have to put thick boards in the centre and the thin boards in the remaining space, but the problem goes deeper. In the figure below, red represents the maximum width of a board (y axis) with a given thickness (x axis). What thickness should I consider from board list for optimal results? I must take into consideration width of the boards (I can put multiple boards on the same column, but they must have same thickness).

Image: http://img641.imageshack.us/i/cuthh.jpg/

Thank you!

flag
8 
 I recommend that you or the sawmill hire a mathematician as a consultant. If someone is going to make money out of this, why should anyone work on it free of charge? – Gerry Myerson May 5 2011 at 12:18
3 
 I second Gerry's comment, if only because this sounds like a really hard problem to solve in the abstract. To obtain a good solution, you would need to give a lot more details than you do here, but also I imagine that there are some practical considerations that must be taken into account. – Thierry Zell May 5 2011 at 12:39
2 
 Dan, we'd need some more information. Suppose R is the diameter of the log. I see two length scales (relative to R) for the logs in your diagram (let's call them l and b) - what are the minimal l and b allowable? - what are the maximal l and b allowable? - are we optimizing over numbers of boards, or numbers of boards of a given l (or b)? - are you obligated to start with a prism? – Nilima Nigam May 5 2011 at 15:29
A Web search will give you more information on the topic than will this forum. However, once you have decided on your central prism, it is just a matter of optimizing use of the left overs. For this, you can try a brute force search of arrangements over allowed board types on each chordal piece. (You can even build a library of such arrangements, to optimize real-time performance.) The web search should give other approaches. Gerhard "Ask Me About System Design" Paseman, 2011.05.05 – Gerhard Paseman May 5 2011 at 21:27
Thank you for your answers! Gerry, I just asked for an opinion, not for complicated formulas. I already received valuable answers. Nilima, a board would have minimum 1x1 and maximum 100x100 (cm). A log can have maximum 200 cm. I try to get maximum volume for a list of boards with given sizes. I am not obligated to start with a prism, but a cut must be form one end to another (some small exceptions). Gerhard, Thierry, a library which should be generated every time when a new board is requested is not a pleasant thing but is the best idea at this time. Thank you! – Dan May 6 2011 at 12:09

closed as off topic by Gerry Myerson, Andrew Stacey, Steven Gubkin, Pete L. Clark, Zev Chonoles May 5 2011 at 15:37

Browse other questions tagged or ask your own question.