计算切割清单以最少的断减少浪费 [英] Calculating a cutting list with the least amount of off cut waste

问题描述

我的工作，我产生一个铝挤压切割列表中的项目。

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

铝合金型材进来5米的长度。

The aluminium extrusions come in lengths of 5m.

予有较小的长度需要被从铝合金型材的5米长度切断的列表。

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

更小的长度需要产生最少的断减少浪费的铝合金型材的5米长度的顺序进行切割。

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.

目前我命令切削列表以这样的方式，其通常最长的小长度被第一切割和最短的长度更小的被最后切割。例外的规则是什么时留下的铝挤压5米长度更短的长度不适合，我用的时间最长的长度较短，将适合。

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?

编辑：谢谢你的答案，我会继续用贪婪的方法，因为它似乎是做了很好的工作（出执行任何人试图建立一个高效的切割列表）和速度非常快

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.

推荐答案

这是一个典型的，棘手的问题有效解决。您所描述的算法听起来像一个贪心算法。看看这个维基百科文章的详细信息：的料问题

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

这篇关于计算切割清单以最少的断减少浪费的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！