algorithm - Calculating a cutting list with the least amount of off cut waste

Question

I am working on a project where I produce an aluminium extrusion cutting list.

The aluminium extrusions come in lengths of 5m.

I have a list of smaller lengths that need to be cut from the 5m lengths of aluminium extrusions.

The smaller lengths need to be cut in the order that produces the least amount of off cut waste from the 5m lengths of aluminium extrusions.

Currently I order the cutting list in such a way that generally the longest of the smaller lengths gets cut first and the shortest of smaller lengths gets cut last. The exception to this rule is whenever a shorter length will not fit in what is left of the 5m length of aluminium extrusion, I use the longest shorter length that will fit.

This seems to produce a very efficient (very little off cut waste) cutting list and doesn't take long to calculate. I imagine, however, that even though the cutting list is very efficient, it is not necessarily the most efficient.

Does anyone know of a way to calculate the most efficient cutting list which can be calculated in a reasonable amount of time?

EDIT: Thanks for the answers, I'll continue to use the "greedy" approach as it seems to be doing a very good job (out performs any human attempts to create an efficient cutting list) and is very fast.

Answer 1

This is a classic, difficult problem to solve efficiently. The algorithm you describe sounds like a Greedy Algorithm. Take a look at this Wikipedia article for more information: The Cutting Stock Problem