排样优化问题普遍存在于钣金、钢结构、船舶、服装、皮革和纸制品、玻璃等行业生产过程中，是制造业自动化中从设计到板料切割中的一个关键环节。实现排样自动化，将有利于节省提高劳动效率和资源利用率，保证制造业自动化的良好实现。 排样问题总目标是在给定的几何图形上不重叠地放置更多的满足要求的几何图形(一维、二维)，使材料利用率最大。具体到不同的行业以及切割、排样环境，表现为不同的约束形式。这是一类NP-hard问题。特别的，大规模规则件排样和不规则件排样问题随着问题规模的增大，计算复杂度更是飞速增长。如何缩短排样时间同时提高板料利用率，是该问题研究的难点，也是本文讨论的重点。 本文的主要工作和研究成果有： (1) 将聚类思想引入排样问题，提取排样图形匹配的有效数据特征，并对该数据特征进行分析，设计了适合于排样图形匹配的聚类算法和分类器算法。 (2) 为了保证排样图形聚类匹配中的数据特征的有效提取，给出了基于位图的实用外包圆、外包矩形集及近似长短轴的计算算法。提出了选择合适的外包策略的原则。 (3) 对排样图形进行了编码研究，利用(2)所获得的图形匹配的有效特征，在排样数据库中补充了排样图形的特征信息，提高了排样图形的检索速度。 (4) 引入免疫机制，针对排样问题提出了更为有效的相似度定义，帮助遗传算法有效避免早熟收敛。 (5) 为了判断改进免疫遗传算法的免疫算子是否真正起作用，提出了免疫算子假设，并提出和设计了统计分析测试算法对该假设进行测试分析，指导相似度定义及其参数的设定。 (6) 基于对排样问题编码上位效应分析，通过排样过程中建立对好基因片的反馈信息，指导遗传算法交叉率和变异率大小选择、交叉和变异发生位置选择，有效避免了遗传算法的欺骗问题和链接问题。 (7) 针对遗传算法不具有良好的局部搜索特性的局限性，建构了遗传算法和邻域搜索算法的混合算法；而因为组合优化问题中，解空间是离散的，邻域搜索算法是否真正起到了良好的局部搜索效果并不是一定的，本文针对遗传算法+邻域搜索算法，进一步提出了邻域假设；并研究了邻域假设是否被满足，给出了设计满足邻域假设的方法和测试已有邻域结构是否满足邻域假设的统计测试算法。