矩形毛坯优化排样问题广泛用于机械制造业、家具制造业以及皮革制造业等行业。随着制造行业市场面临的竞争日益激烈,有效提高材料的利用率,降低生产成本,是增加企业效益的有效途径之一。由于矩形毛坯优化下料方案不仅可以提高材料利用率,节约生产成本,而且可以简化切割工艺,提高生产效率,所以对矩形毛坯优化排样问题的研究具有深远的理论和实际意义。矩形毛坯无约束两维剪切问题通常是指在一定数量的长和宽给定的板材上,尽可能多地排放所需要的矩形毛坯,从而使得所消耗的板材尽可能地少,以达到节省材料的目的。它属于典型的组合优化问题,己被证明是NP完全问题,即由于存在计算上的复杂性,在一定时间内求其精确全局最优解相当困难。国内外学者对于该问题的研究给予了足够的重视,并提出了许多算法。通常可以采用精确算法和提示算法解决此问题,精确算法只能用于解决规模较小的排样问题,实践中的排样问题,一般属于中大规模,常采用提示算法求解。与矩形毛坯无约束两维剪切问题紧密相关的矩形毛坯优化排样问题通常是指在满足对毛坯需求量的前提下,使得板材利用率最高,最大限度地减少废料,以达到节省材料的目的。通常采用线性规划求解矩形毛坯优化排样问题。线性规划是通过反复迭代求解,在每一次迭代过程中,都需要调用矩形毛坯无约束排样算法,生成一个排样方式。按是否允许在同一张板材中排入多种尺寸的毛坯,把相应的排样方式称为单一排样方式或套裁排样方式。和单一排样相比,套裁排样虽然切割工艺比较复杂,但能明显提高材料利用率。本文研究的是矩形毛坯套裁排样问题。矩形毛坯优化排样问题是一个多目标优化问题,一方面要考虑到板材的利用率,由于国内的许多企业仍处于手工下料阶段,下料利用率较低,造成原材料的浪费,提高板材利用率可以节约生产成本,减少环境污染,提高企业效益;另一方面要考虑到生产时的下料效率,生产中常采用剪冲下料工艺分两阶段将金属板材分割成毛坯,第一阶段称为剪切阶段,用平剪床将板材切成条带,第二阶段称为冲裁阶段,用冲床从条带上分离出毛坯,为了提高下料效率,在设计排样算法时,通常在保证利用率的前提下,要求生成的排样方式中所含的毛坯种类数尽可能的少,以便提高下料利用率。综合考虑这些因素,本文采用了三块排样方式生成算法,它基于背包问题和动态规划算法,可以生成无约束排样方式-最优三块排样方式,这种排样方式是用两条成T形的剪切线将板材分成三个矩形区域,每个区域中包含一个由同尺寸毛坯组成的均质块。在此基础上,本文通过对解的分析,采用三种策略缩小解的搜索范围,以缩短求解时间。本文把三块排样方式生成算法和线性规划结合后的算法称为三块排样方案生成算法,它可以生成最优三块排样方案,用于解决大规模的矩形毛坯排样问题。在具体求解过程中,本文采用单纯形法迭代求解线性规划,在每次迭代循环中,都调用最优三块排样方式生成算法,根据当前的毛坯单价,生成一个排样方式。在满足约束条件的情况下,得出最优三块排样方案。采用文献中报道的基准排样例题和生产实例对本文的算法进行实验。对文献中例题的计算结果表明,与经典二阶段排样方式相比,三块排样方式生成算法生成的最优三块排样方式在板材利用率和简化切割工艺两个方面都有比较好的效果;与典型排样算法(二阶段、T形、两段、三阶段排样算法)相比,三块排样方案生成算法在解决大规模矩形毛坯排样问题时,虽然板材利用率稍低,但生成的最优三块排样方案简单,每种排样方式中的毛坯种数最多不超过三种,能够简化切割工艺。对生产实例的计算结果表明,三块排样方案生成算法的计算时间可以满足实际应用的要求,生成的最优三块排样方案的板材利用率较高,排样方式较简单,能够简化切割工艺。因此,三块排样方案生成算法在生产实践中是一种值得推荐的算法。