线性下料. 一维下料问题
考虑型材类型、有限库存和切口宽度的一维棒料下料。给出每根棒料的方案、余料、材料利用率和两种优化目标。
本内容采用知识共享署名/相同方式共享许可协议3.0(未移植)进行许可。这意味着你可以在相同的许可条件下自由地重新发布或修改本内容,并且必须在你的网站上放置一个超链接到本作品https://zh.planetcalc.com/11038/,以注明原作者。此外,请不要修改本内容中对原作的任何引用(如果有的话)。
线性下料是把零件分配到棒料、钢筋、管材或其他定长原材料上。零件可以交换位置:重要的不是它们在列表中的原始位置,而是哪些零件适合从同一根棒料上切下。
下面的计算器可以为多种型材制定方案,考虑原材料数量和切口宽度,并显示每根棒料的余料。默认值可以删除,它们仅用于演示。公式和一些理论说明见计算器下方。
原材料、零件和型材
原材料是原来的棒料,零件则是需要得到的料段。表格中使用以下字段:
- 型材类型表示材料或轧制产品的种类,例如“A500C 钢筋”。零件只能放在型材类型相同的原材料上。即使长度恰好容易配合,也不应在同一个方案中混合钢筋和铝管。
- 长度是原材料或零件的长度。所有长度必须使用相同的单位:如果选择米,80 厘米应写成 0.8。
- 数量是相同项目的个数。计算器会把它展开为单独的零件或棒料,因此“长度 3、数量 2”表示两个长度为 3 的零件。
余料是已使用棒料中既没有成为零件、也没有被切削消耗的部分。余料仍可能有用,因此把它一律称为不可回收的废料并不正确。未使用的棒料完全不计入余料。
两根棒料的例子
假设我们有一根 12 米的棒料和一根 9 米的棒料,需要四个零件,长度分别为 8、7、4 和 2 米。
一个完整的方案如下:
| 原材料 | 零件 | 余料 |
|---|---|---|
| 12 米 | 8 + 4 米 | 0 米 |
| 9 米 | 7 + 2 米 | 0 米 |
零件总长为 21 米,恰好等于已用原材料的长度,材料利用率为 100%。这是计算器的默认示例;对于其他输入数据,当然不保证余料为零。
为什么要考虑切口宽度
锯切时,少量材料会变成切屑。这个宽度称为切口宽度(kerf)。如果忽略它,屏幕上漂亮的方案可能无法在实际棒料上实现。
计算器采用保守规则:每个零件都预留一个切口宽度。如果一根棒料上放置长度为 的零件,切口宽度为
,则占用长度为
其中 是棒料上的零件数。只有满足
时方案才可行,其中
是原材料长度。余料按下式计算:
为什么是 而不是
?
规则适用于把一根棒料完全分成
段。但如果最后一个零件之后仍有余料,还必须把这个零件从余料上切下来。为了避免在长度恰好相等时暗中设置例外,计算器始终为每个零件预留一次切割。
例如,两个 5 米长的零件加上 1 米的切口宽度,需要 12 米而不是一根 10 米棒料。如果有库存,这样的方案需要两根棒料。
究竟优化什么
“优化”在这里有两种不同含义:可以少用几根棒料,也可以让已用棒料上留下更少的材料。这两个目标并不总是一致。
假设有一根 12 米棒料和两根 5 米棒料,需要两个 3 米零件:
- 棒料数量最少。 两个零件都能放在一根 12 米棒料上。余料为 6 米,但两根短棒料保持不动。
- 总余料最少。 每个零件分别放在一根 5 米棒料上。使用了两根棒料,但总余料只有 4 米。
因此,计算器允许选择目标。默认选择总余料最少。主要标准相同时再比较次要标准:先比较总余料或棒料数量,然后按相反顺序比较。
评估结果时,材料利用率很有用,即成品零件长度占已用原材料长度的比例:
其中 是第
个零件的长度,
是第
根已用棒料的长度。切口宽度不计入分子。因此,材料利用率、切口所占比例和余料所占比例之和为 100%。
为什么不能直接保证最佳方案
这是一个一维下料问题(one-dimensional cutting-stock problem),与装箱问题(bin packing problem)密切相关。经典装箱问题要求把给定的一组物品装入数量最少的相同容器中。我们的问题还考虑不同的原材料长度、有限的数量和型材兼容性。
即使是经典装箱问题也是 NP 难的。1 这并不意味着无法得到精确答案。对于小规模集合,可以枚举各种方案;大型问题可以用整数规划和下料模式生成来求解。2 但这样的精确求解器需要单独的限制和更复杂的实现。
计算器使用启发式算法,即快速构造良好方案的规则,但不证明方案的最优性。因此,结果应理解为“已找到的最佳方案”,而不是“所有可能方案中的最佳方案”。
算法如何工作
首先按型材类型拆分问题。这不是近似处理:零件本来就不能移到另一种型材的原材料上。然后对每种型材执行四种构造方案:
- 零件按长度递减或递增排列;
- 启用新棒料时,先选最短适用棒料或先选最长适用棒料。
对于下一个零件,最佳适应规则(best fit)选择放置后剩余空间最小的已启用棒料。如果没有合适的棒料,就启用另一根未使用的棒料。
随后对所得方案进行局部改进:3
- 移除棒料。 算法尝试把其中的零件移到其他已使用的棒料上。如果成功,就释放这根棒料。
- 交换。 如果简单移动没有帮助,算法会有限度地尝试交换零件,然后再次尝试移除棒料。
- 替换原材料。 如果同一组零件能放在同型材的更短空闲棒料上,就进行替换。
最后只需按所选目标比较各个方案。这里没有随机试错:用相同数据重复计算会得到相同方案。
棒料数量的下界
对于一种型材,可以将零件总长除以可用的最长原材料长度,再向上取整:
其中 是棒料数量下界,
是这种型材可用的最大原材料长度。各型材的下界相加。
这个下界有意保持简单:它不考虑切口宽度、数量限制和不方便的长度组合。如果找到的方案恰好使用 根棒料,就可以证明棒料数量最少,但不能由此证明余料最少。
如何阅读结果
下料方案中每行对应一根已使用的棒料。“8 + 4”表示两个相应长度的零件;切割顺序不影响材料消耗。每行还会列出零件长度、切口预留量、余料和材料利用率。
按型材汇总有助于检查不同材料类型的分配情况。未使用的原材料显示剩余库存。如果没有找到完整方案,未分配的零件表会列出算法未能分配的零件。
这在实际中意味着什么?可能原材料确实不足,或者某个零件比任何合适的棒料都长。但也有另一种可能:启发式算法没有找到实际存在的方案。因此,“未找到完整方案”并不能证明无法下料。
适用范围和限制
- 不保证最优性。 计算器检查方案是否可行以及完整的长度平衡,但不检查结果在所有可能方案中是否最优。
- 不混合型材。 型材名称按精确字符串比较,包括字母大小写。用一种材料替代另一种材料需要单独的工程判断,而不是装箱规则。
- 零件不能拆分。 每个零件必须完整地放在一根棒料上。
- 新的余料不会自动成为原材料。 如果要在后续工作中使用,请手动把合适的余料添加到原材料表中。
- 输入限制。 按数量展开后,最多支持 100 根棒料和 100 个零件,最多六位小数。这是浏览器计算的限制,不是问题本身的性质。
- 只考虑长度。 采购成本、端部切边、夹具、最小可用余料、机床操作顺序和切割时间均不在模型内。
如果给出的不是长度,而是矩形的宽度和高度,那就是另一个问题。可以使用二维装箱计算器。对于没有型材、不需要逐棒料方案的相同容器,装箱问题和装箱问题 2计算器可能有用。
-
Richard E. Korf. A New Algorithm for Optimal Bin Packing. AAAI 2002. 问题定义、启发式算法和复杂度。论文。 ↩
-
P. C. Gilmore, R. E. Gomory. A Linear Programming Approach to the Cutting-Stock Problem. Operations Research, 1961. 下料模式和列生成。论文。 ↩
-
A. C. F. Alvim, C. C. Ribeiro, F. Glover, D. J. Aloise. A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics, 2004. 结合方案构造与局部改进的示例。论文。 ↩
评论