二维不规则板材排样(2DIBPP)是二维排样问题的一种,这种问题在工业生产中应用十分广泛。如家具板材加工、造船工业、汽车工业、钣金加工工业、服装生产、皮革加工等都需要处理排样问题。尽管不同工业领域中的排样有各种不同的限制约束,但是它们共同的基本问题在于找到所需部件在原材料上一种有效的放置,提高原材料板材的面积利用率,尽可能多地节约原材料。对于2DIBPP问题,本文提出了针对单规格板材二维不规则切片的一种排样放置算法(LS),由三个主要部分组成:第一个部分是指派策略算法,采用了快速且众所周知的最佳适用下降算法(BFD);BFD直接按照切片面积的递减给所有切片排序,按照排好的顺序来将切片按面积指派到矩形板材中。第二个部分是单板排样算法,首先采用左下算法来将切片放置到每块板材,得到切片的初始位置;然后在板材内部交换两个切片;最后采用重叠最小化算法在重叠值最小的情况下找到它们的新位置,从而得到一个初始可行解。第三个部分是局部搜索算法,在两块矩形板材之间进行多边形切片的一对多交换,然后调用第二个部分的单板排样算法得到更好的可行解,直到利用率F不再提高或达到时间限制,停止迭代并结束。在介绍排样算法之前,本文对课题相关的点、线段、多边形等几何概念进行了定义,因为切片和板材都可以看成由不规则的多边形组成。然后对排样问题和排样解进行了定义。最后对可行解的评价指标进行了定义,选择了更加节约材料的评价指标F。同时,本文还介绍了相关的重叠碰撞技术和最小二乘方法。经典的重叠碰撞技术有三种:包络矩形法、像素法和临界多边形(NFP)法;我们用临界多边形对重叠值进行了定义。然后我们介绍了线性最小二乘问题的正规方程算法和非线性最小二乘问题的高斯牛顿法;并将它们用来设计重叠最小化算法。本文有两种实验数据集:嵌套实例和拼图实例;用这两种实验数据集对LS算法进行了实验测试,跟目前文献中取得最好解的算法进行了比较。在嵌套实例集,我们的结果取得明显的优势,对于拼图实例集,也取得了更好的排样可行解,只是时间上要稍微大一些。最后我们的算法被运用在板式家具切割下料生产过程中,取得了更好的结果。