Embedded Files
My design and implementation of an algorithm to maximize cost efficiency in lumber projects. (3-6 min read)
If you've ever started on a woodworking project where you know ahead of time exactly how many of what size cuts you need, as I did for my shelf project, you know that figuring out how much lumber your project requires is not much more than a guessing game. Do I guess at combinations of what boards to cut from until I get a plan that feels good? Do I just buy a bunch of lumber and hope for the best? Instead, I decided there has to be a better way and made a program to tell me what to buy. The math for this got surprisingly spicy, and made for a fun project.
To view the full code, click one of these buttons to view or download the code. For an overview of the project, read on below.
To articulate the problem clearly, I want a program that will accept a set of desired lengths as an input along with what length of boards it has to choose from to make those cuts. It will then return to me which cuts to make from which boards in order to waste as little lumber as possible.
First, some information is gathered from the user such as if they want an SAE cutting guide in addition to metric(filthy Americans, we are), what method of importing they'll use to declare the cuts they desire, and what lengths of wood they have available.
The program is written in full here, with a description of the algorithm below for optional reading.
With all of my information gathered, the Algorithm can process the data to return my results.
In short, my algorithm efficiently tests literally every single possible way that the cuts I desire can be produced from the lumber I have available, of which there can easily be over a billion possible combinations. My algorithm iterates through a series of simulations using the Combinations Equation, all while accounting for manufacturing tolerances of your typical DIY woodworker. It will return to me the method with the least lumber wasted, and in the next step we will use that information to make a tidy little set of instructions to export as a .pdf file.
For a longer more detailed explanation of my algorithm, including the ways I optimized the code for larger projects, click here.
The theory of my algorithm can be described as this:
1. First, it considers the longest board length available, and confirms that there are no cut sizes too large for the longest board length.
2. Considering all of the cuts of wood required that are stored in the variable cuts_needed, the algorithm finds every possible combination of ways to get the lengths required from the boards available(skipping over some combinations that are impossible, such as those that would exceed the length of the board available, and minimizing the number of combinations to find so as to reduce computational complexity), while prioritizing large boards over smaller boards(larger boards are cheaper than smaller boards per foot). Additionally, the manufacturing inaccuracies of common lumber is accounted for in the calculations, as well as the inevitable lumber wasted by making cuts(an estimation of the width of the saw used).
2a. If the user needs a lot of cuts of wood(greater than about 21) the algorithm becomes prohibitively slower due to the math behind how the number of combinations is found. So, my program is designed in such a way that if more than 21 individual cuts need to be generated, the algorithm is modified.
2b. The set of cuts required(say, 60 cuts total) is randomly split into groups of similar size not to exceed 21 each. So in this case our three(60 cuts/21 cuts per group= <3 groups) groups are then run through the algorithm mentioned in step 2 individually, and their outcomes combined afterwards to form one set of cutting instructions. This set of instructions is stored for later analysis.
2c. Now the problem with that of course is that splitting the cuts into groups means that I'm likely shooting myself in the foot. What if two cuts from group 1 should most ideally be combined with a cut in group 3? My solution to this is to perform Step 2b a large number of times(I found 100 iterations to be high enough to consistently yield good results, and low enough to give acceptably quick computation times), each time randomizing which values are put into which groups. Doing this makes it statistically very likely that a highly ideal result will emerge that wastes very, very little lumber. Notably, this method is imperfect, but computing all of the values at once is not realistically possible. Given the nature of the project, a bit of imprecision is acceptable, as we're realistically talking about wasting a couple inches of lumber in a worst case scenario. Once all the iterations have been run, the program now has a collection of 100 sets of cutting instructions which are stored in the variable cut_sets_results.
2d. Each of those cutting instructions are compared with one another by finding the set of instructions that wastes the least amount of lumber.
3. The final results of which cuts to make from which boards are stored in the variable lumberpurchased. This information is then processed in various ways to get useful outputs, including converting all values to inches with fractions so that a common SAE tape measurer can be used(assuming the user opted in to this when starting the program).
This is the finished, printable product that gets saved to my computer, ready to be printed out and taken to Home Depot. As you can see the first table describes what materials I should purchase. The second table tells me in the first column which board to grab, and in the right column which cuts I'll be making from that board.
For my project that inspired this program, I ended up saving about 15-20% in lumber costs by using this calculator as compared to my best guess through traditional methods. Now imagine how much money could be saved if I were building something huge, like a house.
I'm pleased with this program for the moment, but I do have things I would like to change in the future to include:
Making the program use multiple processor cores for quicker computing times.
Implement functionality for 2 dimensional cuts, instead of just "board length" as it is currently configured.
Make the pdf exporting code a little prettier.
Publish a usable website where people can use this as a calculator for their own woodworking projects.
I hope you enjoyed my writeup. I have other python programming experience including making data analysis programs for my job as a photovoltaics performance analysis engineer with PVAMPS, personal finance calculators, engineering calculators, and more.
Page updated
Google Sites
Report abuse