Calculation of the optimal stock length
This is similar to the problem with the cutting disc , but with a slight difference. I want to know what is the optimal stock length based on the cut sizes.
Potential complications:
-
Wikipedia article on stock cutting problem. I suspect that understanding how to fix this problem might be critical to solving my own problem.
-
Some cut lengths are more common than others. Anything less than 2 feet is considered scrap, so we'd rather make the cut leaving a large piece of waste. On the other hand, we do not want to depend on numerous pieces of a partial stock in the hope that we might need one of them one day.
source to share
I understand correctly: you have different cut lengths (3.6, 10.2, 8.3, 7.3, ...) and want to know what is the best stock length to give you the least waste reduction? Do you want to find just one background length or several? is there a maximum length, minimum length? If you don't have a maximum length, your best bet is to use one very long stock in which all the cut lengths fit exactly, but I don't think that's what you want.
UPDATE I've been working on this issue for a while as part of my job, we have a product that does this (and more). For a simple solution, you can implement the First Fit Decreasing heuristic that works with a given headroom length. Then randomly use multiple stock lengths and use heuristics each time to fill them. Remember the length of the stock with minimal waste.
If you need a more advanced algorithm, I advise you to buy our software :-)
source to share
The problem also depends on the amount of stock you want to use.
If S = 1, then the stock length must be the sum of the dimensions of all the cuts.
If S> 1, then you want to divide the section size into S-groups and minimize the difference between summing the section sizes in each group. This is very close to the NP-hard partition problem .
source to share