View Question
Q: What is the process to derive the minimum lumber needed ( Answered ,   0 Comments )
 Question
 Subject: What is the process to derive the minimum lumber needed Category: Science > Math Asked by: cmaury-ga List Price: \$3.00 Posted: 18 Jun 2004 10:16 PDT Expires: 18 Jul 2004 10:16 PDT Question ID: 363007
 ```I have a woodworking project that calls for various lengths of lumber in various quantities (e.g. (4) 2x4x34", (4) 2x4x32, (1) 2x4x33, and (4) 2x4x27.25" pieces). I have some available lumber, and I can tell that I will need to purchase more. For example, I own (1) 2x4x53", (1) 2x4x66", and (1)2x4x96" pieces - certainly not enough. I want to maximize the use of my existing lumber, and buy the least amount of additional lumber that will result in minimal waste. Eventually, I would like to build a computer calculator (I work with various development languages) for my own use with other projects. [Difficulty] Intuitively, it seems that I should be able to calculate the optimum ways to cut the lumber, perhaps using an iterative calculation where I compare the results. However, the permeations seem to grow quickly beyond manageability. I have considered arrays, and algebra seems to be applicable, but I have not been able to "see" the solution.``` Request for Question Clarification by smudgy-ga on 18 Jun 2004 10:20 PDT ```Hi cmaury, Nice problem. This is close to a classic "bin packing" problem, and the sad truth is that there is no efficient way to come up with an ideal solution to an arbitrary bin packing problem. There do exist algorithms for coming up with "good" (though not necessarily optimal) solutions to this problem. Would such an algorithm be of any interest to you as an answer? Thanks, smudgy.``` Clarification of Question by cmaury-ga on 18 Jun 2004 10:28 PDT ```At the risk of sounding ignorant, would the "bin packing" problem be a 3 dimensional problem verses a single dimensional problem I have here? My problem is that I can cut a board in various, finite combinations. Furthermore, I can purchase finite quantities of standard lengths (96", 120", 144"). The worst solution to any variation of my problem would be to buy 1 piece of lumber for each cut I require, assuming my required piece is <= length of purchased piece. So, if I need 12 "parts", I could simply buy 12 pieces of lumber <= length of each required "part". Good for the lumber store, bad for me! LOL.``` Request for Question Clarification by smudgy-ga on 18 Jun 2004 10:39 PDT ```Bin packing problems are generally phrased something like, "We have several bins, each of which can hold various amounts of weight. If we have a bunch of discrete items each of which has a different weight, what are the fewest number of bins we need in order to bin all the items?" This is basically equivalent to your problem, with bins replaced by stock lumber, items replaced by cut lumber, and weight replaced with length. It's still essentially a one-dimensional problem in the sense you're thinking of, inasmuch as the bins are only measured in one dimension. In fact, "bin packing" style problems are often framed as lumber-cutting problems in textbooks. Does this sound like it might be helpful?``` Clarification of Question by cmaury-ga on 18 Jun 2004 10:49 PDT `Sure, let's give it a shot!`
 ```Hi cmaury, I hope you find the following answer satisfying. If not, please request a clarification before rating and I will do my best to explain further. There are several different heuristics for solving the bin-packing (or in this case, lumber-cutting) problem, and while none of them can guarantee optimal efficiency, there are several that can get us reasonably close to an ideal solution. The algormithm I will provide is the "first-fit-decreasing" algorithm, which is well-suited to situations, such as this one, where you know all the lengths that you will need to cut the lumber into beforehand. The basic algorithm goes something like this. 0: Usually in this algorithm every "bin" (or piece of lumber) is the same size. This condition is not a huge hurdle to overcome and I don't think the fact that your already-available pieces of lumber are different sizes will affect the outcome too much. But for the purposes of introducing the algorithm, assume that you have a bunch of stock lumber, all of the same length. 1: First, make a list of all the lengths that the lumber needs to be cut into, from largest to smallest. 2: Now, on the first piece of stock lumber, mark off the length of the first piece you need to cut. 3: Look at the second length on the list. Can this be cut out of the remainder of the first piece of stock? If so, then mark that distance off too. If not, mark this distance off on a second piece of stock lumber. 4: Repeat this process for every length in your list. First see if it fits in the remainder of the first piece of stock, then the second, etc. When you get to a piece of stock that has enough space to "fit" the new cut, mark off that new cut. When you are done with the list, you will have marked off two or three or four cuts on most pieces of lumber, and in such a way that short cuts are paired with long cuts relatively efficiently. An example: Let's say we have a bunch of boards that are 15 inches long. We need to cut the following lengths in inches: 10, 8, 8, 7, 7, 7, 5, 5, 4, 2, 2, 2 On the first board, we mark off 10 inches. We can't mark off a further 8 inches on the first board, so we mark it on the second board. Likewise, we can't mark off 8 more inches on the first or second board, so we mark it off on a third board. We can't mark off a further 7 inches on the first board, but we -can- on the second board. etc. At the end of the process, this is how our boards are being cut up: 10+5 8+7 8+7 7+5+2 4+2+2 In this case, we have one inch of unused lumber on the second to last piece of stock, and seven inches of unused lumber on the last piece of stock. However, we can be relatively assured that we are not using many more boards than is strictly necessary to use. In your case, I feel that the algorithm can be modified simply by letting the first three pieces of lumber be of the size that you have on hand, and letting the remaining pieces of lumber be of some arbitrary stock length that you pick. I hope you find this answer satisfying! If you are not satisfied or if you are having trouble understanding the algorithm, please request a clarification and I will do my best to resolve any issues. Thanks, smudgy. Here is a web page describing a few different bin-packing algorithms: http://www.york.cuny.edu/~malk/tidbits/tidbit-bin-packing.html and another one describing the bin-packing problem in general: http://mathworld.wolfram.com/Bin-PackingProblem.html and a couple with java-based bin packing solvers: http://www.cs.ucf.edu/courses/cop3930H.01/JavaExamples/binpack.BinPack.html http://www1.minn.net/~dchristo/BinPacker/BinPacker.html http://www.research.compaq.com/SRC/JCAT/jdk10/binpacking/index.html (This last is a really nice animation showing the -exact- method that the algorithm described above uses. Check the box marked "first fit decreasing" before running the demo. Unfortunately you can't enter your own object sizes in this demo.) This page has some computer code for a bin-packing computer program. I'm not sure what language it's in... visual basic? You might be able to glean some information from the program if you're planning to write your own software: http://www.cs.arizona.edu/icon/oddsends/bpack/bpack.htm Search method: Google search Google search ```
 cmaury-ga rated this answer: ```Very good information provided. On a side note, it is amazing to me that as sophisticated as we humans are (Mars Landers, Men on the Moon, Great Pyramids, etc.), we haven’t been able to come up with a definitive method to determine the most efficient way to cut stock when building (or cutting or packing!)```