工业分区问题

Question

我们正在谈论金属制品厂。有机器可以将较长的铁棒切割成较小的部件，这些部件后来用于制造各种产品。

例如，我要求生产以下长度和数量的条： 2件248mm， 5个1150毫米， 6个，2843毫米， 3个3621毫米。

这是分区输出。

在输入端我有（例如） 3条2500毫米， 2条5000毫米， 6条8000毫米 和3个10000毫米的棒。

我应该找到一种如何最佳地切割输入条的方法 - 切割后的其余部分（其余部分太小而不能使用）应该尽可能小。

我创建了算法，只需创建所有可能的组合，然后在其中选择最好的组合。代码有效，但只要输入和输出稍微大一些，计算就可以持续很长时间，所以我必须找到解决问题的新方法。

你有任何提示吗？

Answer 1

您的问题是运筹学中非常常见的问题。看着 减少库存问题。这个问题基本上是NP难的，因为你已经想到了自己。它不能很好地扩展。

如何解决？在能够找出模型之后，最好调用一些混合整数编程求解器。我之前使用的是 LPSolve 5.5

可能有一些简单的算法可以代码处理这个问题。当您需要添加作者未想到的一些辅助约束时，通常会出现这些算法的问题。 MIP求解器是更通用的工具。

Answer 2

这称为可变大小的装箱问题。这是NP难，这意味着你的解决方案总是会因大输入而失败。这篇文章，这里，遗憾的是我也没有访问权限，地址这个问题以金属切削行业为例。

Answer 3

线性编程是你的朋友。请参阅 http://en.wikipedia.org/wiki/Linear_programming ，特别是， http://en.wikipedia.org/wiki/Linear_programming#Uses ，< a href =“http://en.wikipedia.org/wiki/Linear_programming#Algorithms”rel =“nofollow noreferrer”> http://en.wikipedia.org/wiki/Linear_programming#Algorithms 。

Answer 4

看起来它类似于背包问题（知道非常讨厌）我在NIST DADS（方便参考）上发现这比非ACM的ACM更容易获得 Bin装箱