计算边角废料最少的切割清单

题

我正在开展一个项目，制作铝挤压切割清单。

铝型材的长度为 5m。

我有一份较小长度的清单，需要从 5m 长度的铝型材上切割下来。

较小的长度需要按照从 5m 长度的铝型材中产生最少量的切边废料的顺序进行切割。

目前，我以这样的方式订购切割清单：通常较小长度中最长的首先被切割，较小长度中最短的最后被切割。此规则的例外是，当 5m 长度的铝挤压件的剩余部分无法容纳较短的长度时，我会使用可以容纳的最长的较短长度。

这似乎产生了一个非常有效的（很少的切边浪费）切割清单并且不需要很长时间来计算。然而，我想，即使切割清单是非常高效，并不一定是最多高效的。

有谁知道一种方法来计算最有效的切割清单，可以在合理的时间内计算出来？

编辑：感谢您的回答，我将继续使用“贪婪”方法，因为它似乎做得非常好（超出了任何人类创建有效切割列表的尝试）并且速度非常快。

解决方案

这是一个经典的、难以有效解决的问题。您描述的算法听起来像是贪心算法. 。请查看这篇维基百科文章以获取更多信息：下料问题

其他提示

恐怕没有关于这个问题的具体想法 - 但你可以研究一下“遗传算法'（这会去某物像这样）...

将要切割的长度按随机顺序排列，并根据该顺序与理想解决方案的匹配程度（大概是 0% 浪费）对该顺序进行评分。

然后，迭代地随机更改顺序并重新评分。如果分数更高，则放弃结果。如果分数较低，则保留它并用作下次计算的基础。继续下去，直到你的分数在可接受的范围内。

您所描述的确实属于切割库存问题，如前轮离地提到过，而不是箱式包装问题是因为您试图最大限度地减少浪费（剩余物的总和）而不是减少使用的挤压件数量。

这两个问题都很难解决，但是您提到的“最佳拟合”算法（使用适合当前挤压的最长“小长度”）可能会以非常低的复杂度为您提供非常好的答案。

实际上，由于物料的尺寸是固定的，但要求不是固定的，这是一个装箱问题。

（我可能也需要在工作中研究一些东西，所以耶！）

这是一个有趣的问题，因为我认为这取决于您生产的每个长度的数量。如果它们的数量相同，并且您可以将每个不同的长度放入一个 5m 的挤压件上，那么您就拥有了最佳的解决方案。

然而，如果它们不能全部安装到一个挤压件上，那么您就会遇到更大的问题。为了保持每个长度的切割量相同，您需要计算一个挤压件上可以容纳多少个长度（不一定按顺序），然后按顺序进行每个挤压件。

我也一直在努力解决这个确切的问题（我的问题的长度是 6 m）。

我正在研究的解决方案有点难看，但我不满足于你的解决方案。让我解释：

库存尺寸 5米

需要切割尺寸（各 1 个）：

**3,5

1,5**

您的解决方案：

3,5 | 1 浪费 0.5

1,5 还剩 3,5

看到问题了吗？

我正在研究的解决方案 -> 暴力破解

1 - 测试所有可能的解决方案

2 - 按废物排序解决方案

3 - 选择最佳解决方案

4 - 从“宇宙”中删除解决方案中的项目

5 - 转到 1

我知道这很耗时（但我花了 1 小时 30 分去吃午饭......所以...:) ）

我真的需要最佳解决方案（我在 Excel 中手动（+-）做了一个几乎最佳的解决方案），不仅因为我很敏锐，而且产品并不便宜。

如果有人有一个简单的更好的解决方案，我会喜欢它

许可以下： CC-BY-SA 和归因