# One dimensional cutting algorithm with minimum waste

Can anybody point me to some resources about "cutting algorithm"?

The problem:

• have rods with length of `L` meters, 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).

Alternatively, if someone can point me to some "spreadsheet" solution, or to anything what helps.

Ps: in addition, need care about the "cutting line width" too, whats means than from the 6m long rod 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) ;(.

-
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. stackoverflow.com/questions/tagged/bin-packing – George Duckett Oct 19 '12 at 10:22
Regarding cutting width just increase all the required lengths by that cutting width. – George Duckett Oct 19 '12 at 10:26
@GeorgeDuckett , With your help i identified than this is the "cutting stock" problem. en.wikipedia.org/wiki/Cutting_stock_problem . Now will be easy to find a right method. Thank you. Write you comment as answer, will accept it. – jm666 Oct 19 '12 at 10:40