题
我正在开展一个项目,制作铝挤压切割清单。
铝型材的长度为 5m。
我有一份较小长度的清单,需要从 5m 长度的铝型材上切割下来。
较小的长度需要按照从 5m 长度的铝型材中产生最少量的切边废料的顺序进行切割。
目前,我以这样的方式订购切割清单:通常较小长度中最长的首先被切割,较小长度中最短的最后被切割。此规则的例外是,当 5m 长度的铝挤压件的剩余部分无法容纳较短的长度时,我会使用可以容纳的最长的较短长度。
这似乎产生了一个非常有效的(很少的切边浪费)切割清单并且不需要很长时间来计算。然而,我想,即使切割清单是 非常 高效,并不一定是 最多 高效的。
有谁知道一种方法来计算最有效的切割清单,可以在合理的时间内计算出来?
编辑:感谢您的回答,我将继续使用“贪婪”方法,因为它似乎做得非常好(超出了任何人类创建有效切割列表的尝试)并且速度非常快。
其他提示
恐怕没有关于这个问题的具体想法 - 但你可以研究一下“遗传算法'(这会去 某物 像这样)...
将要切割的长度按随机顺序排列,并根据该顺序与理想解决方案的匹配程度(大概是 0% 浪费)对该顺序进行评分。
然后,迭代地随机更改顺序并重新评分。如果分数更高,则放弃结果。如果分数较低,则保留它并用作下次计算的基础。继续下去,直到你的分数在可接受的范围内。
这是一个有趣的问题,因为我认为这取决于您生产的每个长度的数量。如果它们的数量相同,并且您可以将每个不同的长度放入一个 5m 的挤压件上,那么您就拥有了最佳的解决方案。
然而,如果它们不能全部安装到一个挤压件上,那么您就会遇到更大的问题。为了保持每个长度的切割量相同,您需要计算一个挤压件上可以容纳多少个长度(不一定按顺序),然后按顺序进行每个挤压件。
我也一直在努力解决这个确切的问题(我的问题的长度是 6 m)。
我正在研究的解决方案有点难看,但我不满足于你的解决方案。让我解释:
库存尺寸 5米
需要切割尺寸(各 1 个):
**3,5
1
1,5**
您的解决方案:
3,5 | 1 浪费 0.5
1,5 还剩 3,5
看到问题了吗?
我正在研究的解决方案 -> 暴力破解
1 - 测试所有可能的解决方案
2 - 按废物排序解决方案
3 - 选择最佳解决方案
4 - 从“宇宙”中删除解决方案中的项目
5 - 转到 1
我知道这很耗时(但我花了 1 小时 30 分去吃午饭......所以...:) )
我真的需要最佳解决方案(我在 Excel 中手动(+-)做了一个几乎最佳的解决方案),不仅因为我很敏锐,而且产品并不便宜。
如果有人有一个简单的更好的解决方案,我会喜欢它