一种启发式矩形毛坯带排样算法研究

作者：李霞; 陈弦

来源：山西大学学报(自然科学版), 2011, (02): 215-218.

DOI：10.13451/j.cnki.shanxi.univ(nat.sci.).2011.02.002

• 排样问题
• 遗传算法
• 递归 packing problem
• genetic algorithm
• recursion

介绍一种两维矩形毛坯带排样问题的改进启发式递归算法,它基于递归结构和分支定界技术.首先初始化板材作为一个块,考虑目前的块,算法选择一个毛坯,将毛坯放在块的左下角,然后用水平或竖直的剪切线将未使用空间分为两个更小的块,便于进一步递归求解.使用上下界来去除无用的分支,缩短运算时间.将该算法和遗传算法相结合,先通过遗传算法确定所有矩形毛坯较优的排放顺序和排放方式,然后使用递归排样生成排样图,通过比较不同的矩形排放序列对应的板材利用率,最终得到较优的排样方案.测试数据表明了该启发式优化算法的有效性.

• 单位
  运城学院