论文部分内容阅读
随着经济的高速发展,科技的不断进步,提高资源利用率和制造效率十分重要。在生产过程中,优良的排样方案可以很好地提升材料的利用率及切割效率。因此,研究二维矩形件排样问题具有重要的实际应用意义和理论价值。二维矩形件排样问题是经典的NP难度问题。受前人研究成果启发,结合人类的生活习惯得到整齐度的概念。该概念主要融合了角区和放置空间,并希望已摆放的小矩形块和剩余空间越平整越好。整齐度不仅考虑了目前矩形块的摆放状态,还考虑了剩余空间的状态,为之后的格局做好可持续发展准备。论文中设计了以整齐度为核心,动作自由度为辅助的占角动作挑选策略。在此策略的基础上得到了基本算法。该算法的主要思想是,每一步根据占角动作挑选策略选择出最好的占角动作,再根据占角动作的指示对矩形块进行放置,直到矩形框放不下或矩形块全部放完为止,此时得到终止格局。一个好的挑选策略,不仅能提高基本算法的精度,还能减少基本算法花费的时间。为了扩宽解空间的搜索领域,从而得到更优质的解,结合基本算法和集束搜索策略,设计了加强算法。在加强算法中,每一步按照占角动作挑选策略挑选出若干个占角动作,将挑选出来的占角动作进行试放。每一个试放的占角动作都运用基本算法走到终止格局,最终挑选终止格局面积利用率最大的占角动作成为这一步的实际占角动作,重复以上过程,在未到终止格局的某一步停止该过程,当前最优终止格局为该算法的解。本文在挑选出若干个占角动作并进行试放的过程中,固定了占角动作的挑选个数,增加了算法的稳定性。此外,该算法固定了步数的值,即只在第一步到给定步数的范围里进行占角动作的试放处理。相比于基本算法,该搜索策略的范围更广,更容易得到最优解,相比于每一步都试放占角动作,该算法节约了一定的时间。因整齐度依赖于角区和放置空间个数,每当发生占角动作时,需要更新角区和放置空间,所以角区和放置空间的更新策略是该算法的重要部分之一。通过计算著名算例C21和N13,验证了算法的有效性,该类算法可以很好的应用于板材切割领域。