Can anybody point me to some resources about “cutting algorithm”?
The problem:
- have rods with length of
Lmeters, e.g. 6 m - need cut smaller pieces of different lengths, e.g. need:
- 4 x 1.2m
- 8 x 0,9m
- etc… (many other lengths and counts)
How to determine the optimal cutting, what will produce the minimum wasted material? I’m capable write an perl program, but haven’t any idea about the algorithm. (if here is already some CPAN module what can help, would be nice).
In addition, I need to take care about the “cutting line width” too, which means that from the 6m long rod it is impossible to cut 6 x 1m, because the cutting itself takes “3mm” width, so it is possible cut only 5 x 1m and the last piece will be only 98.5 cm (1m minus 5 x 3mm cut-width).
3
This sounds like the Bin Packing Problem where the bins are the size of your rods and the object sizes are the lengths of material required. See also stackoverflow.com/questions/tagged/bin-packing
Following comments, it’s known as the Cutting Stock Problem
1
I can recommend this website https://champcut.de
Similar to a spreadsheet solution, they offer a free function to assemble a solution to the 1D cutting stock problem yourself. You only have to enter the frequency and patterns and get a visual indication of violation of constraints. That is, you get red background cells indicating that you exceed rod width or did not fulfill rod demand. Besides you can also specify allowable overproduction which some customers might accept. Allowable overproduction provide flexibility to find solutions with higher yields.
If every cut adds an extra margin to the cut width, then you have to specify this in advance. Say instead of 1.0 m you specify 1.03 m.
Note that the website tool also provides solving capabilities. You can run the solver for free and can compare the yield of your manual solution with the solver one. If the solver solution is way better than yours, you can consider buying the license for this particular problem. Depending on the order at hand you have a business case for that or not.
Another extra free feature is the minimization of knife positionings by reordering the patterns and the cuts within each pattern.
Further constraints you might impose are (a) the maximum number of cuts per pattern (which corresponds to number of knives available if cutting takes place simultaneously) and (b) the maximum number of different cut width per pattern and (c) the the maximum number of patterns.
1