排样问题是指在下料的过程中尽量减少材料的损失,使材料的利用率达到最高。它广泛存在于加工生产中,如板材切割、集装箱装载、服装和家具制造等。解决好这一问题,不仅可以节省原材料,降低企业生产成本,而且还可提高企业生产效率。矩形件排样问题是二维排样问题的一个分支。国内外许多学者对其进行过深入和广泛地研究,理论上证明其属于NP完全问题。当遇到较大规模时,势必会带来计算量的组合爆炸,因此很难在一定时间内取得最优解。针对上述问题,目前解决的方法多为启发式方法。因此,研究矩形件排样问题既有实际应用价值,又有理论意义。启发式方法的特点是解决问题时,利用过去的经验规则,选择行之有效的方法。对于大规模问题的优化求解,其具有快速随机的全局搜索能力,大大减少了计算量,表现出比其它方法更优越的性能。除此以外,启发式方法简单易行、易于理解,具有良好的可扩展性,是解决排样问题的重要工具。本文研究的是二维矩形件排样问题,即在多张规格相同的矩形板材上排放一定需求量的毛坯,使得消耗板材的总面积达到最小。基于上述考虑,为了求解该问题,本文以“最小浪费优先策略”为基础,提出了一种分组搜索的启发式算法。与其它文献中报道的实例测试对比,板材利用率均有所改善,验证了本文算法的有效性。本文所做的主要工作如下:第一,认真分析了中外学者提出的多种启发式算法,经过仔细比较,在总结其优缺点的基础上,对“最小浪费优先策略”进行了改造。“最小浪费优先策略”是从浪费区域的角度考虑,即毛坯排入后是否产生浪费区域以及产生浪费区域的大小。本文在其基础上提出了两种改造策略,第一,增加了一个限制条件,即毛坯排入后如果产生的浪费区域大于某值,则取消其排入。修改后的策略避免了一些不良方案的出现。第二,是毛坯排入的方向。早期的策略使用“最左原则”排入毛坯,取得了很好的效果。本文在其基础上进行改造,增加了一个“最右原则”。改造后可能会增加毛坯摆放的多样性,对提高板材的利用率或许起到帮助。第二,考虑优化计算时间过长,以及排样方案不均衡等问题,本文提出了一种分组策略,即把所有的毛坯按面积大小均分三组,每次生成当前方式前,都从三组中各选择适当的块数,用于生成当前方式。在分组的过程中,有一些参数可以依据实际情况进行调整。例如,为了确定适当的块数,从一组中挑选出的毛坯面积和应该定为何值,本文规定其最大为1倍的板材面积,最小为0.3倍的板材面积。经过分组操作后,选择了一个毛坯集合的子集,从而缩短生成当前方式所需时间。第三,将改造的最小浪费优先和分组策略相结合,提出了一种启发式算法——分组搜索算法。算法中如何产生排样序列是其关键步骤。在现有的启发式算法中,有些学者应用遗传学的原理来生成排样序列,已经取得了较好的效果。本文引用随机局部搜索,利用随机交换两个毛坯的相对顺序,来生成新的排样序列。在随机操作中,需要使用一些技巧,当随机产生两个小矩形件的位置时,如果产生的位置相同,或者两个位置上小矩形件是同种,则把其中一个位置逐渐递加,直到位置上的两个小矩形件是不同种类为止,这样尽量增加序列的多样性,避免重复序列的生成。经过整体重复计算后,通过比较结果,保存较好的解,得到最终排样方案。分组搜索算法是一个组合算法,文中给出了其详细的伪码描述。第四,通过对矩形件优化排样系统框架的分析,分别实现了其四个主要模块功能。包括数据输入模块、优化排样模块、排样结果显示模块、系统帮助模块。其中算法模块是整个框架的核心部分。本文选取了三组文献中的测试实例,其均与本文研究问题的排样规则相似,因此本文的算法与其测试结果具有可比性。经过测试后,并将实验结果与其进行了比较和分析,板材利用率均有所提升,验证了本文算法的有效性。第五,对己完成的工作进行了总结,提出了需要进一步改进之处。