圆形件卷材排样问题的一种定序定位算法
2018-07-12潘卫平
图学学报 2018年3期
陆 涛,潘卫平
圆形件卷材排样问题的一种定序定位算法
陆 涛1,潘卫平2
(1. 南宁学院信息工程学院,广西 南宁 530200;2. 广西大学计算机与电子信息学院,广西 南宁 530004)
圆形件卷材排样问题是指将一组不同半径的圆形件互不重叠的排放在宽度指定的卷材上,使得占据的卷材长度最小。针对该问题提出一种定序定位启发式优化算法。设计基于最大穴度的定位算法,对于每个特定排样序列,计算待排样圆形件在当前布局的所有可行放置位置的穴度,选择穴度最高的一个位置放置圆形件;更新当前布局,继续排放剩余圆形件,直到所有圆形件均排放进卷材为止。采用遗传算法对排样序列进行遗传进化得到多种不同的排样方案,选择耗费卷材长度最小的一种排样方案作为最终解。实验结果表明,本文算法排样方案耗费卷材长度较小,且算法计算时间相对合理。
卷材排样问题;圆形件;优化排样;排样算法;定序定位算法
在机械制造领域,经常需要将金属卷材切割成圆形件用来生产各种家用商品,譬如水桶,盘子,杯子等。对圆形件在卷材中的排样方式进行优化,可以减少卷材资源消耗,降低企业生产成本[1-2]。本文研究圆形件卷材排样(circular parts coiled sheet packing,CCSP)问题,该问题在文献[3]的切割与装填布局分类中属于二维开放维度布局问题,在计算理论上属于NP难范畴,具有很高的计算复杂度[4]。

本文针对CCSP问题,提出一种耗时较少的定序定位求解算法。首先构造圆形件的定位算法,计算圆形件在当前布局中各个可行放置位置的穴度,按照穴度最大原则确定圆形件的放置位置;……
登录APP查看全文
