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.

Denver

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

Sideslip

Answer 2

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.

Fruity

Answer 3

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.

Spandrel

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!)

Kirwan

Answer 5

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.

Phew

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

Mccandless

Answer 7

The Column generation algorithm will quickly find a solution with the minimum possible waste.

To summarize, it works well because it doesn't generate all possible combinations of cuts that can fit on a raw material length. Instead, it iteratively solves for combinations that would improve the overall solution, until it reaches an optimum solution.

If anyone needs a working version of this, I've implemented it with python and posted it on GitHub: LengthNestPro

Shanghai

Answer 8

I am starting on a similar task now. My plan is to start simple, than move on to algorithms of increasing complexity. Final choice will depend on performance (waste amount) and speed on larger datasets. For others who've found this post (as OP seems to have a solution) I would recommend starting with some online heuristic algorithms, as they are easy to implement, than move to their offline versions. Online heuristics are usually versions of greed algorithms.

So far I've implemented:

• First Fit (online)
• First Fit Decreasing (offline)
• Refined First Fit Decreasing (offline)

Refined first fit decreasing has good performance so far! (90-98% depending on the dataset I use). Usually performs about 5% better than first fit and 2-3% better than First Fit Decreasing. I'll be trying Column Generation next, wish me luck haha. It's been a while since I've tried any Linear Programming. Mostly been using the Bin packing problem Wiki to find these.

Kenakenaf