圆形件卷材排样问题的一种定序定位算法

圆形件卷材排样问题是指将一组不同半径的圆形件互不重叠的排放在宽度指定的卷材上,使得占据的卷材长度最小。针对该问题提出一种定序定位启发式优化算法。设计基于最大穴度的定位算法,对于每个特定排样序列,计算待排样圆形件在当前布局的所有可行放置位置的穴度,选择穴度最高的一个位置放置圆形件;更新当前布局,继续排放剩余圆形件,直到所有圆形件均排放进卷材为止。采用遗传算法对排样序列进行遗传进化得到多种不同的排样方案,选择耗费卷材长度最小的一种排样方案作为最终解。实验结果表明,本文算法排样方案耗费卷材长度较小,且算法计算时间相对合理。

圆形件卷材排样问题的启发式优化算法

圆形件卷材排样问题是将一组不同尺寸的圆形件排样在宽度指定的卷材上,使得占据的卷材长度最小。针对该问题提出一种基于先定序后定位思想的启发式优化排样算法,构建了圆形件卷材排样问题的数学模型,计算了待排样圆形件在当前布局的所有可行放置位置的优度指标,选择优度指标最高的位置放置圆形件,并通过对圆形件排放序列进行变换,得到多种不同的排样方案,选择耗费卷材长度最小的排样方案作为最终解。构造了半径非递增、首圆形件置换和子序列划分3种算法,并利用文献中的例题,比较了3种算法和文献算法排样的计算时间和卷材使用长度。实验结果表明：本文算法生成的排样方案耗费的卷材长度较小,且算法计算时间比较合理;子序列划分算法的求解质量最好,能较好地使大小圆形件在卷材中均匀分布。