在石材加工领域,单一矩形石材的排样加工是最常见的问题。天然的石材都是不规则形状,对于不规则石材大板内单一矩形零件排样的问题,通常做法是找到其最大内部矩形,然后在最大内部矩形中进行矩形零件的排样。这种排样方式得到的最后结果往往不是最优的,并且不规则图形内部的最大矩形求解是一个很困难的问题。为了得到最优的排样结果以及提高排样效率,本文进行了二维不规则图形内的单一矩形排样研究,主要的研究内容可以分为以下几个方面:(1)矩形单一排样中最常见的是“一刀切”问题。因此,首先研究了经典PLP问题,基于动态规划算法建立了 PLP问题“一刀切”的数学模型,并且利用数学模型进行逆推得到了矩形工程板的最优排样方案;按照单一排样中各根条带排样的顺序,确定了桥式切机的切割路径,实现了桥式切机的自动化切割。利用机器视觉检测,通过对大板的非接触扫描和图像处理,得到二维不规则多边形的边界;基于边界坐标,直接在不规则图形内进行“一刀切”的单一矩形排样;实验结果证明了本文的方法能快速高效的解决不规则石板内矩形单一排样的问题。(2)针对天然石材的不规则性,研究了直接在任意凸多边形内进行单一矩形排样的问题。将求解在凸多边形中的单一矩形问题,转化为求解在凸多边形内部排放m个矩形零件的问题;通过不断增大m的值,找到排放最多矩形零件的排样结果。通过凸多边形的顶点坐标得到每条边的直线方程,将任意凸多边形表示若干条直线表示的封闭图形。在凸多边形中排矩形零件的排样需要满足两个限制条件:矩形零件必须全部位于凸多边形内部以及矩形零件之间不能重叠,即包含约束条件以及不重叠约束条件。利用上述的两个约束条件,建立无约束最优化的目标函数;利用经典遗传算法,求数学模型的最优解;最优解对应的决策变量就是所排矩形的坐标点。实验结果说明本章算法的高效性以及优越性。(3)针对天然石材的不规则性,研究了直接在任意凹多边形内进行单一矩形排样的问题。由于凹多边形的特性,凹多边形与矩形零件相对位置难以确定。本文采用最近流行的IFP方法来判断矩形零件与任意凹多边形的包含关系,并且给出了一种新的求一个凸多边形和一个凹多边形IFP的方法。在判断矩形零件重叠的条件上,给出了新排入的矩形零件与已排入的矩形零件不重叠的判断条件。通过在NFP与IFP上建立同种精度的网格,对多边形进行离散化的处理。在离散化处理的基础上,给出了一种类似于搜索树的启发式搜索算法。实验结果表明这种启发式算法具有高效性。本论文通过对以上内容的研究,对二维任意图形内的单一尺寸矩形排样问题,进行了基础理论研究并且提出了相应的算法和解决方案,大大提高了企业生产效率。