One dimensional cutting algorithm with minimum waste

Posted by jm666 on Programmers See other posts from Programmers or by jm666
Published on 2012-10-19T10:18:04Z Indexed on 2012/10/19 11:23 UTC
Read the original article Hit count: 270

Filed under:

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

© Programmers or respective owner

Related posts about algorithms