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

Question

我正在做一个制作铝挤压切割清单的项目。

铝型材的长度为 5m。

我有一个需要从 5m 长度的铝型材中切割的较小长度的列表。

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

目前，我以这样的方式订购切割清单，通常较短的长度中最长的长度首先切割，而较小长度中最短的长度最后切割。这条规则的例外是，只要较短的长度不适合 5m 长度的铝挤压件的剩余部分，我就会使用适合的最长的较短长度。

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

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

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

score 15 · Accepted Answer

这是一个经典的、难以有效解决的问题。您描述的算法听起来像贪心算法。请查看此 Wikipedia 文章以获取更多信息：切割库存问题

score 5 · Accepted Answer

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

以随机顺序放置要切割的长度，并根据它与理想解决方案的匹配程度给该顺序打分（大概是 0% 浪费）。

然后，迭代地对订单进行随机更改并重新评分。如果分数更高，则放弃结果。如果分数较低，请保留它并将其用作下次计算的基础。继续前进，直到您的分数在可接受的范围内。

score 3 · Accepted Answer

正如Wheelie所提到的，您所描述的确实被归类为切割库存问题，而不是装箱问题，因为您试图最大限度地减少浪费（剩余物的总和），而不是使用的挤压件数量。

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

score 2 · Accepted Answer

实际上，由于材料的大小是固定的，但要求不是，这是一个装箱问题。

（我可能也需要考虑工作，所以耶！）

score 1 · Accepted Answer

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

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

score 1 · Accepted Answer

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

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

库存尺寸5 m

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

**3,5

1

1,5**

您的解决方案：

3,5 | 1浪费 0,5

1,5剩余 3,5

看到问题了吗？

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

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

2 - 按他们的废物订购解决方案

3 - 选择最佳解决方案

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

5 - 转到 1

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

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

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

score 0 · Accepted Answer

列生成算法将快速找到可能浪费最少的解决方案。

总而言之，它运作良好，因为它不会生成适合原材料长度的所有可能的切割组合。相反，它迭代地求解可以改进整体解决方案的组合，直到达到最佳解决方案。

如果有人需要这个的工作版本，我已经用 python 实现了它并将它发布在 GitHub 上：LengthNestPro

7 回答 7