基于层次聚类模型的矩形优化排样问题研究

王竹婷 邹乐

(合肥学院计算机科学与技术系，合肥 230601)

矩形优化排样问题是国内外制造业领域研究的热点问题之一。在这些行业的原材料切割工艺中使用优化后的排样方案，可以极大地降低成本，提高企业的经济效益。但该问题目前已被证明为一类NP完全问题，即随问题规模扩大，此类问题的计算复杂度呈指数级增长。如何在合理的时间范围内计算出优化的排样方案成为该领域研究的重点。

目前较常用于求解排样问题的算法主要有遗传算法［1］(Genetic Algorithm，GA)、模拟退火算法［2］(Simulated Annealing Algorithm，SA)、微粒群算法［3］(Particle Swarm Algorithm，PSA)等通用型的智能优化算法，将这些算法与最下最左算法［4］(Bottom－Left，BL)，基于 BL 的填充算法［5］(Bottom － Left Filling，BLF)、最低水平线法［6］(lowest horizontal line，LHL)等作为解码方法相结合使用，可以得到较好的排样结果。但智能算法迭代次数多，时间复杂度较高，在求解大规模排样问题时的时间效率偏低。

为降低排样算法的时间复杂度，本文将凝聚的层次聚类模型［7］引入排样问题中，并给出两矩形件之间结合度的概念，按层次聚类的思想，将结合度较高的矩形件合并成矩形簇，最终将所有矩形件合并到一个簇中，排样结束。最后设计算法程序，引用标准数据集测试算法性能，测试结果表明本文所提出算法可有效求解大规模排样问题。

1 矩形优化排样问题描述

矩形件优化排样问题，就是在一张或几张给定长度和宽度的矩形板材上切割指定规格和数量的矩形零件，要求所消耗的原材料最少。为方便描述此类问题，本文只讨论原材料为单一板材的情况。……