二维不规则零件排样算法及系统的研究

作     者：刘月明 

作者单位：华南理工大学 

学位级别：硕士

导师姓名：胡跃明;李胜

授予年度：2012年

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：不规则排样 最小包络矩形 启发式规则 几何特征比较 

摘      要：二维排样问题，也就是平面布局优化问题，是指如何在二维板材区域内找出待排零件较好的布局，其目的是为了用最少的板材生产出这些零件。二维排样问题在许多行业领域中都有广泛的应用，如造船业、服装、报刊排版、冲裁件切割等。在生产水平不高的企业，大部分是凭借人的经验进行手工排样。在现在经济高速发展的时代，只要零件的排样效率稍微提高一点就可能产生很大的经济效益。因此也吸引了国内外众多学者对不同的二维排样问题进行了几十年的研究。而其中的二维不规则排样问题，计算复杂，难度较大，至今仍没有较好的方法来解决这一类问题。虽然有研究表明基于临界多边形（NFP）算法和遗传算法能有较高的材料利用率，但对于NFP的计算比较复杂，实际应用起来的难度比较大。针对上述存在的问题，本文研究二维不规则零件排样问题的快速排样启发式算法，主要做了以下的工作： （1）提出了一种简单求取不规则零件的最小包络矩形的方法，在此基础上提出了基于不同水平高度下放包络矩形，间接对零件进行排样的方法，这种方法能快速地对不规则零件进行排样，同时避免了单纯使用基于最左最下（BL）算法导致较大空洞的缺陷。 （2）提出了利用不规则零件的几何特征比较进行直接排样的方法，判断板材的某个边界区域与零件的几何形状的匹配度，以此作为零件排样的定位基准条件，这样就可以不用计算零件的临界多边形（NFP），以较快的速度找出排放零件的贴合位置。在排样的过程中动态地对零件进行组合排样，提高板材的利用率。 （3）结合前面两种算法，分析已排区域上的基准排样点，将零件放在具有最小废区面积的基准位置，再通过“摇晃式的移动使零件逐步靠近已排区域，同时减少空白区域，从而实现对零件的直接排样，简化了不规则零件排样的复杂度，提高零件排样的速度。 （4）最后结合本文中的各种排样算法，设计了一个能与AutoCAD进行数据交互的软件平台，把排样算法用于求解实际中的排样问题。