Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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) ;(.

share|improve this question
2  
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
1  
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

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
1  
And here is an ready-to-run program sources (C++). code.google.com/p/cspsol –  jm666 Oct 19 '12 at 11:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.