面向玻璃切割机的排样优化算法设计与实现

摘要

计算机自动排料技术的不断发展为很多排样优化领域带来了效益,面向玻璃切割机的排样优化正是二维图形排样的一个应用分支。二维图形的排样是一个NP完全问题,它有较高的计算复杂度,这对面向玻璃切割机的排样优化带来了一定的挑战——算法必须具备可行性。针对排样领域的特定需求,本文从研究几个核心算法着手,分别探索并设计了矩形件和非规则件的排样优化算法。
　　 对于矩形件的排样,本文分别对贪心算法和最低水平线算法进行改进、设计与Matlab仿真,实现了改进的贪心算法和基于最低水平线的组合算法,经过性能测试、比较与分析,得出改进的贪心算法可以获得很高的排样利用率,并且它的耗时性能具有较大的改进空间;基于最低水平线的组合算法能有效改善最低水平线算法的中心空白区域,可以作为进一步研究并改进最低水平线算法的新渠道。结合面向玻璃切割机的排样需求,本文选择了贪心算法用于实际排样,在此基础上,对改进的贪心算法进行策略性的两次改进与VC实现。VC实现的第一个改进贪心算法即第二次改进的贪心算法,主要是对算法的外部控制进行改进,通过测试数据的验证、比较与分析,证实改进后的贪心算法相对于第一次仿真时的改进在排样时间上稍有改善,可以保证排样结果的紧密度,获得较高的排样利用率,适用于种类较多、尺寸相对于板材不大的中等数量规模的矩形玻璃件排样优化;VC实现的第二个改进贪心算法即基于条料的贪心算法,是针对第二次改进的贪心算法而做的进一步改进,它采用条料思想减少了占角对象,从根本上有效改善排样时间,通过测试数据的验证、比较与分析,证实它在排样时间上大为改善,适用于大规模的矩形玻璃件排样优化。
　　 对于非规则图形的排样,本文从描述图形形状的数学理论着手,自设靠接规则,将最低水平线算法运用于非规则图形排样领域,通过对算法数据结构、主要模块以及总体流程的设计实现了基于最低水平线的靠接算法,通过测试数据的排样显示证实该算法可以实现快速排样,且利用率也较满意,可以运用于面向玻璃切割机的排样优化领域。