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

That's an interesting problem because I suppose it depends on the quantity of each length you're producing. If they are all the same quantity and you can get Each different length onto one 5m extrusion then you have the optimum soloution.

However if they don't all fit onto one extrusion then you have a greater problem. To keep the same amount of cuts for each length you need to calculate how many lengths (not necessarily in order) can fit on one extrusion and then go in an order through each extrusion.

Answer 2

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

Answer 3

No specific ideas on this problem, I'm afraid - but you could look into a 'genetic algorithm' (which would go something like this)...

Place the lengths to cut in a random order and give that order a score based on how good a match it is to your ideal solution (0% waste, presumably).

Then, iteratively make random alterations to the order and re-score it. If the score is higher, ditch the result. If the score is lower, keep it and use it as the basis for your next calculation. Keep going until you get your score within acceptable limits.

Answer 4

Actually, since the size of material is fixed, but the requests are not, it's a bin packing problem.

Again, wikipedia to the rescue!

(Something I might have to look into for work too, so yay!)

MSN

Answer 5

What you described is indeed classified as a Cutting Stock problem, as Wheelie mentioned, and not a Bin Packing problem because you try to minimize the waste (sum of leftovers) rather than the number of extrusions used.

Both of those problems can be very hard to solve, but the 'best fit' algorithm you mentioned (using the longest 'small length' that fits the current extrusion) is likely to give you very good answers with a very low complexity.

Answer 6

I've been struggling with this exact ( the lenght for my problem is 6 m) problem here too.

The solution I'm working on is a bit ugly, but I don't settle for your solution. Let me explain:

Stock size 5 m

Needs to cut in sizes(1 of each):

**3,5

1

1,5**

Your solution:

3,5 | 1 with a waste of 0,5

1,5 with a left over of 3,5

See the problem?

The solution I'm working on -> Brute force

1 - Test every possible solution

2 - Order the solutuion by their waste

3 - Choose the best solution

4 - Remove the items in the solution from the "Universe"

5 - Goto 1

I know it's time consuming (but I take 1h30 m to lunch... so... :) )

I really need the optimum solution (I do an almoust optimum solution by hand (+-) in excel) not just because I'm obsecive but also the product isn't cheap.

If anyone has an easy better solution I'd love it