Calculating optimal stock length

Question

This is similar to the cutting stock problem, but with a slight difference. I want to find out what the optimal length of the stock is based on the sizes of the cuts.

Potential complications:

1. The Wikipedia article on the Cutting Stock Problem is way over my head. I suspect that understanding how to solve this problem might be critical to solving my own problem.

2. Some cut lengths are more common than others. Anything less than 2 feet is considered scrap, so we'd rather not make a cut that leaves a large piece of scrap. On the other hand, we don't want to hang on to numerous pieces of partial stock in the hopes that we might need one of them some day.

Answer 1

The problem also depends on the number of stocks S you want to use.

If S=1, then the stock length should be the sum of the sizes of all the cuts.

If S>1, then you want to divide the size of cuts into S groups, and minimize the difference between the summations of sizes of cuts in each group. This is very close to the partition problem, which is NP-hard.

Answer 2

It seems you have the "online" version of this or a similar optimization problem. Online means that you don't know all the information in advance, i.e. you have to make decisions as the orders come in.

Answer 3

Do I understand this correctly: you have different cut lengths (3.6, 10.2, 8.3, 7.3, ...) and you want to find out what stocklength is the best to give you the least cutoff waste? Do you want to find just one stocklength, or multiple? is there a maximum length, a minimum length? If you dont have a maximum length, the best choice is to use one very long stock where all cut lengths fit in exactly, but I don't think this is what you want..

UPDATE Ive been working on this problem for a while as part of my work, we have a product that does this (and more). For a simple solution, you could implement a First Fit Decreasing heuristic that works with a given stock length. Then randomly use several stock lengths and each time use the heuristic to fill them up. Remember the stock length with the minimum waste.

If you want a more advanced algorithm, I advise you to buy our software :-)