可减少排样方式数的二维下料顺序启发式算法

摘要

讨论矩形件二维下料问题,将板材成本最小作为主要优化目标,将排样方式数最少作为辅助优化目标。提出一种可减少排样方式数的下料算法。该算法基于顺序启发式框架,按顺序逐个产生排样方式满足剩余矩形件的部分需求量,直到矩形件的所有需求量均得到满足为止。它采用一种分组技术选择可用来生成下一个排样方式的矩形件,用这些矩形件生成下一个排样方式后根据顺序价值校正方法调整矩形件的价值,其中每个排样方式均采用动态规划程序生成。将本文下料算法与两种文献算法进行对比,实验结果表明,本文下料算法使用的板材面积比文献算法分别节省了1.12%和0.89%,排样方式数比文献算法分别减少了45.56%和30.79%,且计算时间与文献算法接近。