I work in the timber construction industry, and I’m looking to develop a script to solve a relatively common problem. The goal is to cut wooden parts of varying lengths from standard 5 m stock bars, while minimizing the number of bars used.
This is essentially a 1D bin packing or cutting stock problem: given a list of part lengths, how can they be grouped so that each group’s total length does not exceed 5 m, and the total number of groups (i.e., bars used) is minimized?
There are tools like OpenNest (for 2D/3D nesting) or Galapagos (a genetic solver in Grasshopper), but they are either overkill or too complex to implement for a problem that is,mathematically simple.
For example, with Galapagos, I have to manually create a “slider” (gene) for each wood part, which becomes unmanageable when the number of parts increases or varies from project to project.
I’m therefore looking for a simple and flexible solution:
Inputs: a list of part lengths to cut and a list of stock length
Output: an optimized grouping into stock bars
If you know of any libraries, algorithms, or approaches well-suited to solving this 1D cutting stock problem, I’d love to hear your suggestions.
This sounds like a good use case for a greedy algorithm to me. The pseudocode for such an algorithm would be as follows:
Sort your stock and part lengths in descending order (largest to smallest).
For each part length, see if it can fit on the first stock length in the list.
2a. If it can, assign the part length that stock length and subtract the part length from the stock length.
2b. If it can’t, go to the next stock length and try again.
2c. If it reaches the end without being assigned, the piece cannot be cut.
Repeat until all parts are assigned.
There are edge cases where this could fail or not be optimal, so if you want, you can permute through the arrangements of stock lengths and test for a minimal remainder or something like that. I would personally write the algorithm as a C# or Python component so you can work with loops - let me know if you need help writing such a thing.
Best,
~CH
This is an ancient problem in computer science and is proved NP-hard, so unless your cut list is very short, you’ll only ever get a good-enough result. The solution will require loops, so best suited to scripting.
A quick search on SOF found this python example. My eyes start to glaze over when reading code so I’ve no idea if it’s suitable for translation to the GH environment, nor how efficient the algorithm is!
this is the greediest and least intelligent way to do that
it takes input lengths, bar length, and extra space (extra space because let’s say you know your saw blade deletes 1.5mm of material each time it cuts… but you can also set it to zero)
it sorts lengths in descending way (longest first) then goes one by one through them
it tries to put that length in the first bin: if it can be contained then that length is assigned to that bin, otherwise the next bin is checked… until all bins are checked
if no available bin can contain it, a new bin is created, with that length as first element of that bin
very stupid, very greedy, very python noob (myself )
)