布局问题广泛存在于多种生产实践领域,诸如卫星舱布置、服装裁剪、板材下料和电子线路设计等领域,其研究具有理论价值和实际应用价值。Packing和Nesting问题,又称为装填问题和排版问题,是两类典型的布局问题。本文以课题来源单位大型起重机制造为背景,研究基于聚类和区域寻优的零部件排版问题。其特点是零部件种类繁多、形状差异很大且多为不规则形状。目前课题来源单位使用的是美国开发的排版软件SigmaNest10,但对于批量板材的大规模多形状零部件排版本问题求解却是不尽于人意,只好对其排版方案采用人工调整。为此,本文基于概率论、运筹学、计算机图形学和人工智能理论,对该问题展开研究,提出了解决瓶颈问题和技术难点的方法,申请了发明专利1项。本文的工作和创新如下:(1)提出了零部件CAD图形的DXF文件编码规则,开发了自动生成图元数据文件的软件。设计的编码规则和开发的软件适用于由线段、圆弧及圆图元组成多形状二维图形,图元数据文件包括其最小包络矩形。设计的算法的计算复杂度低,求解速度快。(2)提出了一种基于区域寻优的多形状零部件包络矩形排版的启发式搜索算法。基于区域寻优启发式搜索算法的排版方案,多形状二维零件间存在间隙。对此,本文进一步提出一种基于Lagrange乘子和kuhn-Tucker条件的邻界计算法,使得图形之间尽量靠紧,得到进一步优化的布局方案。(3)在批量钢板大规模多形状零件排版问题中,针对前面排版利用率高,后面排版利用率低这一难点,提出了一种基于聚类的启发式搜索算法,并且设计了排版流程步骤。通过对比实验表明,本文排版程序运行效率高,布局效果好,材料利用率较高。本文以某制造企业的大型起重机零部件排版问题为研究背景,针对单块矩形板排版问题,提出了基于区域寻优的启发式搜索算法和基于Lagrange乘子和kuhn-Tucker条件的邻界计算法;针对批量矩形钢板大规模多形状零部件排版问题,提出了一种基于聚类的启发式搜索算法。通过实验对比,得出本文算法具有较好的性能。