基于启发式动态分解算法的矩形件优化排样

本资料包含pdf文件1个，下载需要1积分

1 基于启发式的动态分解算法矩形件排样问题 是研究-组矩形物体如何在有限区域内互不重叠的布局优化问题，其研究成果应用于板材的切割、集装箱的货运、超大规模集成电路的布图、建筑装修的布局等中。该类问题直接影响到行业效率的提高，其研究具有广泛的实用价值，但该问题又被证明为-个 NP难问题 J。

NP难问题精确求解的难度极大，特别是在规南大的情况下，计算时间以万年为单位。因此，该类问题的快速求解吸引了国内外众多学者的研究。文献[3-12]中提出了多种求解二维矩形件排样问题的算法，如贪心算法、遗传算法、粒子群算法、启发式算法以及混合算法等；文献[13]提出了解决三维矩形件排样问题的拟人化算法，但上述研究成果的应用不具有普遍性，难以应用于其他嘲矩形件排样问题的求解。

本文基于动态”和分解”的思想，提出了基于启发式的动态分解算法，其具有良好的鲁棒性和适应性。另外，该算法可扩展为三维排样(三维装箱)和多个矩形容器的全局排样算法，并已在实际应用中得到验证。

1.1 矩形 Packing问题数学描述矩形件排样的问题可描述为：对于-个宽为 ，高为日的矩形容器s，需要将n个矩形块R。， ，， ，其中矩形的宽为W ，高为h ，互不干涉且旧能多地放进容器.s中，如图1所示。矩形容器s的左下角为坐标原点，矩形容器的下底边为 轴，左边为y轴，