7

您好，我为一家以这种方式运作的制造公司工作

我们得到一卷特定尺寸的材料，我们的供应商让我们说每卷 8000 米。然后我们收到不同客户的订单，例如 2000 米、3000 米等。我想知道我应该如何创建一个软件，让他们只需输入他们当前的卷筒尺寸和我们目前的不同订单就可以了生成切割不同卷材的最佳方式，以最大限度地减少浪费。

例如在特定时间点我们可能有以下订单 2 件 3000 米 2 件 4000 米 6 件 1500 米

然后我们只需要输入上述订单以及供应商为我们提供的卷筒尺寸，我们假设它是 8000 米。

然后软件应生成输出，例如 Roll 1 - 两片 4000 米 Roll Wasted 0 Roll 2 - 两片 3000 米和 1 片 1500 (Roll Wasted 500) Roll 3 - 五片 15000 (Roll Wasted 500)

脚本应该优化，因为上面的例子很小。通常我们一次会订购大约 200 件

我正在考虑在 PHP 和 MYSQL 中执行此操作，因此它可以基于 Web，并且公司周围的人都可以使用它。

我知道我们可以通过蛮力尝试每种组合来做到这一点。但是在这种情况下是否有任何其他排序算法和技术可以提供帮助。

4

2 回答 2

1

这是众所周知的切割库存问题，您希望在完成所有订单后最大限度地减少浪费。

维基百科是这样描述它的：

切削问题是一个优化问题，或者更具体地说，是一个整数线性规划问题。它源于工业中的许多应用。想象一下，您在一家造纸厂工作，您有许多固定宽度的纸卷等待切割，但不同的客户需要不同数量的不同尺寸宽度的纸卷。你将如何切割面包卷以最大限度地减少浪费（剩余量）？

一般情况是 NP-hard，这意味着没有快速算法来产生最优结果。

但是，您可以编写一个算法来生成计算速度快且“合理”好的近似解。

编辑（礼貌@David）：

如果你从制造商那里得到的原始卷总是相同的尺寸，在这种情况下是 8,000 米，那么下料问题就简化为一维装箱问题，这更容易解决（但仍然是 NP-hard .)

@David 在其已删除的答案中提出的贪婪解决方案是获得近似解决方案的一种快速且廉价的方法。

编辑2：

我有点说错了。对于装箱问题，没有已知的多项式时间近似方案。不过，贪心算法实际上还不错。

于 2012-04-28T19:08:55.167 回答
0

您正在寻找一维装箱算法。有很多策略可以解决它，First-Fit、Best-Fit、Random-Fit。我在 phpclasses.org 上写了一个 php 解决方案。你可以免费下载我的程序（bin-packing）。事实上，我已经为此获奖了。如果您的问题不是那么大，我会尝试一种蛮力方法。

于 2012-04-28T19:06:55.213 回答