排样是计算机技术和现代经济发展的产物。排样问题的目标就是尽最大可能在材料上放置尽可能多的零件,以减少材料损失。计算机辅助排样是广泛应用的计算机辅助技术之一,具有板材利用率高,耗时短,费用低等优点。计算机辅助优化排样的目的在于寻求某种优化的布局方式,使平面区域的面积利用率较高。凡是需要进行材料分割的行业,都可以应用计算机排样技术。排样问题属于典型的组合优化问题,在现实生活中有着广泛的应用,具有很高的计算复杂性。对于规模较大的排样问题,不但手工排样不可能做到真正的优化,即使采用计算机也必须开发高效的算法,才能实现利用率相对较高的优化切割。本文利用启发式搜索方法,使得在较短的时间内,能够求得问题的近优解。本文研究的问题是用宽度固定、长度无限的矩形板材切出一组尺寸已知的矩形毛坯,使得所消耗的板材面积尽可能小,即要求排完全部毛坯所占用的板材长度尽可能小。要求矩形毛坯的边和板材的边平行,能够用剪床下料。这个问题称为矩形带排样问题(Rectangular Strip Packing),它是两维条带排样(2D-SPP,two dimensional strip packing problem)问题的RG子类型,这里R表示允许毛坯转90度排列,G表示可以剪切下料。本论文研究的目标:紧密结合企业的实际生产需要,以提高原材料的利用率、降低企业的原材料成本为主要研究内容,开发出相应的排样软件,能够给出材料利用率较高的排样方式,供理论研究和实际应用参考。本文包括两个部分:(1)前面部分给出一个两维矩形毛坯带排样问题的改进启发式递归算法。它基于递归结构和分枝定界技术。为了使切出全部毛坯所需板材的总长度尽可能小,使用了一些改进的启发式方法。首先初始化板材作为一个块。考虑目前的块,算法选择一个毛坯,将毛坯放在块的左下角,然后用水平或竖直的剪切线将未使用空间分为两个更小的块,便于进一步递归求解。使用上下界来去除无用的分枝,使用改进的启发式方法来缩短运算时间。测试结果表明,该算法的计算速度比文献中最近报道的一种启发式递归算法要快。(2)本文后半部分是一个遗传算法与上述改进的递归方法相结合的算法。首先对遗传算法做了系统介绍,包括遗传算法的特点、基本实现技术等。遗传算法是借鉴生物的自然选择和进化机制的一种全局优化自适应概率搜索算法,具有快速随机的全局搜索能力。对于非常复杂、高度非线性问题的优化求解,表现出比其它传统优化方法更优越的性能,是21世纪智能计算中的核心技术之一。对求解矩形件优化排样问题的遗传算法的设计及具体实现进行了详细讨论。这个算法主要是基于遗传算法和启发式目标的递归结构。算法同样选择一个毛坯放置在板材的左下角,由水平或竖直剪切线将板材分割为两个更小的块,如此递归循环。使用改进启发式规则以及遗传算法寻找更优解。本文所做的主要工作如下:本文的主要内容分两个部分:前面部分把启发式方法和递归排样相结合。先将毛坯按照面积由大到小进行排序作为一个基本序列,然后使用一些启发式方法考察多个序列,减少不必要的检索,缩短排样的时间,通过比较不同的矩形排放序列对应的板材利用率,最后使用递归排样得到排样图;后面部分把遗传算法和启发式递归排样结合起来,共同求解矩形件优化排样问题。先通过遗传算法和启发式方式确定所有矩形毛坯较优的排放顺序和排放方式,然后使用递归排样生成排样图,通过比较不同的矩形排放序列对应的板材利用率,最终得到较优的排样方案。本文的特点之一,是允许根据优化的需要,对遗传算法生成的序列进行调整,即允许在递归排样时变更原染色体中基因的顺序。根据提出的算法,开发出了计算机辅助优化排样系统,测试数据表明了启发式优化算法的有效性。这对指导企业节约原材料、降低产品成本、提高经济效益,具有积极的意义。在文章最后,对本文工作进行了总结,并指出有待进一步深入的研究工作。