1

我被要求为我的学校开发一个用于制造环境的简单软件。

这是场景：

我得到了一个尺寸列表 - 每个尺寸都反映了一块木板，例如，我有一块 24" x 30" 的木板、30" x 30"、30" x 48" 等等。这些板是他们切割原材料的过程的副产品。

原材料采用两种不同类型的板尺寸 60" x 120" 和 48" x 96"。

他们想知道从原材料中切割板材的最佳方式——“最佳”方式被定义为原材料和残留物最少的方式。他们还想知道将使用的原材料数量，例如 30 块 60 英寸 x 120 英寸的板和 3 块 48 英寸 x 96 英寸的板。

他们能够水平或垂直切割任何板，这意味着 24" x 30" 可以切割成 24" x 30" 或 30" x 24"。

如果给我总共 50 个板（可能是相同尺寸），我可以有 2^50 种不同的组合 - 这对我来说似乎太长了，因为他们将在数千个不同尺寸的板上运行软件。

我想知道是否有人知道可能适合这种情况的算法。

谢谢！

4

3 回答 3

3

用于矩形二维切割和包装问题的经典简单算法是Wang 算法

然而，纯王的算法能够产生最佳的断头台切割模式，即所有切割从剩余材料的一个边缘一直移动到相对边缘的模式。它不能产生如下一种非断头台图案

+---------+---+
|         |   |
+---+-----+   |
|   |     |   |
|   |     |   |
|   +-----+---+
|   |         |
+---+---------+

然而，对于许多应用来说，断头台切割模式被认为是足够好的。因此，您可能需要考虑该算法（因为它非常简单）。

还有基于模拟退火技术的近似随机算法（详细描述可以在VLSI 设计的模拟退火一书中找到（在网上找不到），它们能够产生非断头台图案。

在任何情况下，为此类问题找到精确的解决方案通常需要大量的计算来生成和分析各种可能的变体，这在大多数情况下是不切实际的。大多数时候，人们更喜欢坚持使用好的近似/启发式算法，这些算法工作得更快。Wang 的算法可以使用启发式过滤器的数量进行定制，从而加快搜索速度（冒着丢失最佳解决方案并将其替换为“几乎”最佳解决方案的风险）。

于 2012-07-19T05:29:15.883 回答
0

首先想到的是，您可以使用装箱算法从给定的一块原材料中包装尽可能多的板。

您也可以尝试并使用遗传算法来搜索最佳切割模式。GA 可能（也可能不会）像装箱算法一样持续有效，但是您可以在 GA 上规定运行时间，例如，在一定时间后选择最佳解决方案。

话虽如此，我认为工厂倾向于使用相同尺寸的材料进行批处理，因此最好在实际切割发生之前允许（可能更慢的）装箱算法运行。

于 2012-07-19T05:18:33.090 回答
0

这是一个难题，它与切削库存问题非常相似。另见装箱问题。

于 2012-07-19T05:19:42.680 回答