二维多阶段矩形剪切排样算法(精)

《二维多阶段矩形剪切排样算法(精)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３２卷第５期计算机应用与软件Ｖｏｌ３２Ｎｏ．５２０１５年５月ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅＭａｙ２０１５二维多阶段矩形剪切排样算法孔令熠陈秋莲（广西大学计算机与电子信息学院广西南宁５３０００４）摘要讨论有需求约束的二维剪切矩形排样问题：将一张板材剪切成一组已知尺寸的毛坯，使排样价值（板材中包含的毛坯总价值）最大，约束条件是排样方式中包含每种毛坯数量都不能超过其需求量。采用普通条带多阶段排样方式，每次剪切都从板材上产生一根水平或者竖直的普通条带，条带中可以包含不同尺寸毛坯。引入分支限界与贪婪

2、策略，以提高算法效率。实验结果表明，该算法可以有效提高排样价值。关键词有约束二维剪切多阶段排样方式普通条带分支限界贪婪策略中图分类号　ＴＰ３９１　　　　文献标识码　Ａ　　　　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００３８６ｘ．２０１５．０５．０５６ＭＵＬＴＩＳＴＡＧＥＴＷＯＤＩＭＥＮＳＩＯＮＡＬＲＥＣＴＡＮＧＵＬＡＲＮＥＳＴＩＮＧＡＬＧＯＲＩＴＨＭＷＩＴＨＣＵＴＴＩＮＧＢＹＧＵＩＬＬＯＴＩＮＥＫｏｎｇＬｉｎｇｙｉ　ＣｈｅｎＱｉｕｌｉａｎ（ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒａｎｄＥｌｅｃｔｒｏｎｉｃＩｎｆｏｒｍａｔｉ

3、ｏｎ，ＧｕａｎｇｘｉＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｎｉｎｇ５３０００４，Ｇｕａｎｇｘｉ，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ　　Ｗｅｄｉｓｃｕｓｓｔｗｏｄｉｍｅｎｓｉｏｎａｌｃｕｔｔｉｎｇｒｅｃｔａｎｇｕｌａｒｎｅｓｔｉｎｇｐｒｏｂｌｅｍｗｉｔｈｃｏｎｓｔｒａｉｎｅｄｒｅｑｕｉｒｅｍｅｎｔ：ｉｎｗｈｉｃｈａｓｉｎｇｌｅｐｌａｔｅｉｓｃｕｔｉｎｔｏａｇｒｏｕｐｏｆｒｏｕｇｈｃａｓｔｐｉｅｃｅｓｗｉｔｈｇｉｖｅｎｓｉｚｅｓａｎｄｍａｋｅｓｔｈｅｎｅｓｔｉｎｇｖａｌｕｅ（ｔｏｔａｌｖａｌｕｅｏｆｐｉｅｃｅｓｃｏｎｔａｉｎｅｄｉｎｔｈｅｐｌ

4、ａｔｅ）ｍａｘｉｍｉｓｅｄ，ｔｈｅｃｏｎｓｔｒａｉｎｔｓａｒｅｔｈａｔｉｎｔｈｅｎｅｓｔｉｎｇｐａｔｔｅｒｎｔｈｅｎｕｍｂｅｒｏｆｅａｃｈｐｉｅｃｅｃａｎｎｏｔｅｘｃｅｅｄｉｔｓｄｅｍａｎｄ．Ｗｅａｄｏｐｔｇｅｎｅｒａｌｓｔｒｉｐｓａｎｄｍｕｌｔｉｓｔａｇｅｄｎｅｓｔｉｎｇｐａｔｔｅｒｎ，ｔｈｅｒｅｗｉｌｌｐｒｏｄｕｃｅｏｎｅｈｏｒｉｚｏｎｔａｌｏｒｖｅｒｔｉｃａｌｓｔｒｉｐｆｒｏｍｔｈｅｐｌａｔｅｉｎｅｖｅｒｙｃｕｔ，ｗｈｉｃｈｃａｎｃｏｎｔａｉｎｔｈｅｐｉｅｃｅｓｏｆｄｉｆｆｅｒｅｎｔｔｙｐｅｓ．Ｂｒａｎｃｈａｎｄ

5、ｂｏｕｎｄａｎｄｇｒｅｅｄｙｓｔｒａｔｅｇｙａｒｅｉｎｔｒｏｄｕｃｅｄｔｏｅｎｈａｎｃｅｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｉｎｄｉｃａｔｅｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｃａｎｅｆｆｅｃｔｉｖｅｌｙｉｍｐｒｏｖｅｔｈｅｖａｌｕｅｏｆｎｅｓｔｉｎｇ．Ｋｅｙｗｏｒｄｓ　　Ｃｏｎｓｔｒａｉｎｅｄｔｗｏｄｉｍｅｎｓｉｏｎａｌｃｕｔｔｉｎｇｐｒｏｂｌｅｍｓ　Ｍｕｌｔｉｓｔａｇｅｎｅｓｔｉｎｇｐａｔｔｅｒｎ　Ｇｅｎｅｒａｌｓｔｒｉｐ　Ｂｒａｎｃｈａｎｄｂｏｕｎｄ　Ｇｒｅ

6、ｅｄｙｓｔｒａｔｅｇｙ［７］ＤＴ）：从Ｌ×Ｗ的板材上切下ｍ种毛坯，其中第ｉ种毛坯的尺寸０　引言和价值分别是ｌｉ×ｗｉ和ｃｉ，需求量为ｄｉ。使用冲压机剪裁方式［８］对矩形板材进行切割，使板材中包含的价值最大。排样问题广泛应用机械制造、电机、航空航天、木材的分割、假设在某种排样方式中排入板材的第ｉ种毛坯的数量为ｚ，ｉ皮革的剪裁等领域。经典的排样问题可描述为将板材切割成较Ｎ表示非负整数的集合，可得到ＣＴＤＣ的数学模型可用公式表小的矩形毛坯，在毛坯不超过其需求量的约束条件下，使板材中示为：包含的毛坯价值之和达到最大。好的排样算法不仅

7、可以极大提ｍ高材料的利用率，还能增加经济效益。ｍａｘ（∑ｃｉｚｉ）ｚｉ∈Ｎｚｉ≤ｄｉ　１≤ｉ≤ｍ（１）ｉ＝１对于此类问题，文献［２］提出了一种基于背包问题的两阶１．２　相关概念段算法，简化了切割流程。文献［４］使用启发式算法解决此类１．２．１　多阶段排样方式问题，但不能保证解的效率与质量。文献［６］提出了一种同质多阶段排样方式是指每次对板材剪切时都产生一根水平或条带精准算法，此算法减少其运行时间，求解速度快，但价值不［９］者竖直的条带。由于每根条带的产生可能需要多个阶段，所高。本文提出普通条带多阶段排样算法，采用分支限界技术

8、提以被称为多阶段排样方式。如图１所示箭头表示切割的方向，高算法的效率。多组对比实验表明，本文算法在大多数实验测箭头上的数字表示切割的顺序。每次剪切从标号最小的箭头开试中表现良好。始，每次都将产生水平或者竖直的条带，然后对这些条带使用冲压机方式剪切生成毛坯。图１中使用普通条带（具体定义１．２