二维下料问题的顺序按叠分组启发式算法

发布时间：2021-08-24 16:02

　　提出顺序按叠分组启发式算法求解二维按叠下料问题,确定按叠下料方案。顺序按叠分组启发式算法按顺序生成组成下料方案的布局图,对于每一个布局图,先根据整叠规则选择毛坯（矩形件）形成的候选毛坯集,再按候选毛坯集分组排样生成当前布局图,并根据整叠规则确定该布局图的使用次数;重复此布局图的生成过程,直至所有毛坯的需求均得到满足,从而确定下料方案。每次生成一个布局图后,通过毛坯价值修正算法对毛坯价值进行修正,使毛坯价值趋于合理。经多次迭代,生成多个不同的下料方案,从中选择总成本最低者作为按叠下料问题的解。实验结果表明,基于整叠规则的顺序分组启发式算法可明显降低二维按叠下料的总成本。 

【文章来源】：锻压技术. 2020,45(09)北大核心CSCD

【文章页数】：6 页

【部分图文】：

图1 条带类型

本文算法的设计初衷是求解需求量较大的按叠切割下料问题，因此，从文献[14]中的Group 1A和Group 1B算例中选取两组数据作为样本数据，并以样本数据中每种毛坯的需求量扩大10倍作为新的毛坯需求量。新的算例分别用A和B来表示，每组例题中包含10组测试样本，每组测试样本中各有50种毛坯，使用的原材尺寸为3000 mm×1500 mm。在计算总成本时，假设每张原材成本和每叠切割成本均为60元。令每叠最大张数p=5，算法最大迭代次数Gmax=50，对取值范围内所有的(η，β)组合进行计算，选取总成本最小的方案作为最优解输出。表2列出了按叠分组与不分组的测试结果，其中，Δ为两种算法结果中相应参数的差值。从表2中可以看出:实施分组后的切割总叠数降低了29.82%，按叠分组与不分组的总成本分别为234120和254280元，前者较后者降低了20160元;叠数分别为873和1244，前者比后者减少了371叠。按叠分组与不分组相比，由于叠数减少使得下料成本大幅降低，总成本也明显降低。从计算时间来看，不分组算法的平均计算时间为6.17 s，分组算法的平均计算时间为2.83 s，分组算法优于不分组算法。由此可见，本文提出的顺序按叠分组启发式算法在减少叠数和降低总成本方面是有效的。4 结语

【参考文献】：
期刊论文
[1]考虑余料生成及利用的圆片下料算法[J]. 王婷婷,崔耀东,陈燕,王睿.  锻压技术. 2019(04)
[2]生成最优同质条带两阶段布局方式的精确算法[J]. 季君,张文增,邢斐斐,谢维,崔耀东.  现代制造工程. 2018(07)
[3]面向可加工性的矩形件优化下料方法[J]. 吴电建,阎春平,李俊,曹卫东.  计算机集成制造系统. 2018(06)
[4]圆形件下料顺序分组启发式算法的设计与实现[J]. 陈燕,谢琪琦,刘咏,崔耀东.  图学学报. 2017(01)
[5]应用精确两阶段排样图的板材下料算法[J]. 王严欣,崔耀东,李华.  计算机工程与应用. 2017(05)
[6]基于分组降维规则和遗传算法的人造板材矩形件优化下料方法[J]. 张国梁,侯晓鹏,苗虎,安源,周玉成,姚永和.  林业科学. 2014(06)
[7]基于零件相似性特征的大规模下料分组优化方法[J]. 尹震飚,阎春平,刘飞,曹智慧.  计算机辅助设计与图形学学报. 2007(11)
[8]基于线性规划的角钢优化下料算法研究[J]. 华中平,张立.  湖北工业大学学报. 2005(05)



本文编号：3360297