论文部分内容阅读
金属板材是船舶制造中消耗的主要原材料之一。船舶制造中一个关键环节是如何设计板料的切割和利用方案。船体建造板材套料系统能够提高生产效率和资源使用率,保证船舶制造的智能化、数字化。排样问题的目标是在给定的几何图形上不重叠地叠放更多的几何图形,使材料利用率最高。这是一类NP-hard问题,而且大规模规则件排样和不规则件排样问题随着问题规模的增大,计算复杂度更是爆炸性增长。如何缩短排样时间同时提高板料利用率,是该问题研究的重点和难点。本文从排样的数据结构、优化理论、算法分析以及协同计算等方面进行了深入的研究,提出了一系列解决方案和算法并开发了一个排样实验系统对算法进行了验证和分析。研究成果和创新点可概括如下:1.对排样问题提出了一套基于图像处理的数据表示和评价方法对于排样问题的研究,目前学者们绝大部分是采用基于图形的方法。但其实基于图像的方法有独特的优势,论文对这方面进行了探索。论文提出了一种基于图像颜色数据分析的重叠检测、出界检测和评价方法,并通过为图像建立“角边链”(描述零件像素坐标和相交等信息)和“信息板”(描述板材像素已被哪个零件占据)数据结构并依据这些数据绘图,使得在试排图像中基于边就可以实现分析评价,使基于图像的二维排样问题复杂度由面积级降至线性级。2.提出了动态邻域及并行模拟退火的算法基于图像的方法的一个缺点是精度不足,为了增加精度,可以扩大图像的尺寸,但这会引起计算的复杂度和排样时间的飞速增加。为了解决这个矛盾,论文对二维排样模拟退火算法的邻域机制和接受新解的机制进行了改进,提出一套动态邻域及并行模拟退火算法,从而解决了“离散”类方法中的精度与时间的矛盾,并使得用模拟退火求解二维排样问题的速度得到了极大提高。3.提出一种基于“开放边集”的解码方法。“开放边集”是一种对后续零件入排有指导意义的轮廓或孔洞边段的有序集合。基于开放边集,论文提出一种用百分比和入排角度组成的编码方法,该方法可以表示所有可能的入排位置。基于这种百分比编码,可以实现快速搜索入排方案,从而实现构造解码。基于开放边集的解码方法不同于传统的BL、BLF、最低水平线、剩余矩形等方法,也不用计算临界多边形(NFP),排样无需进行矩形化预处理和零件靠接后处理,无论矩形件还是不规则件都适合,是一种新的入排解码思路。论文继续提出基于该解码算法与遗传算法结合的混合排样算法,并进一步提出一些加速排样的新技术,如配角初排、开边挑选、分布式方案。这些算法使得排样的板材利用率比前人有所提高,多个实验算例打破了已有报道的最高利用率。4.对余料管理进行了研究,并提出了一个基于余料的套排规划算法合理利用余料是提高板材利用率的一个好思路。论文研究了板材排样完成后余料图像的提取、余料的分解以及余料自动再参排的方法,并实现了套排规划与排样优化的同一化,一方面使得板材选件更加自动化,另一方面使得多次排样后板材利用率进一步提高。5.根据以上核心算法,编写了排样程序系统。实验证明,该排样系统效果良好。