随着中国加入WTO,制造行业的企业面临着更为激烈的市场竞争。为了在竞争中立于不败之地,企业必须想方设法提高经济效益,而提高经济效益的重要途径之一就是通过提高材料的利用率来降低成本。矩形件排样在工业上有广泛的应用,目标是使下料过程中的切割损失减少到最少,使得原材料的利用率最高。优化排样算法的研究既有实际应用价值,又有理论意义。矩形排样问题属于组合最优化问题和NP完全问题,因为存在计算上的复杂性,在一定时间内求其精确全局最优解是相当困难的。对于矩形排样问题,任何算法都难以保证总能得到最优解,目前解决的方法多为各种启发式算法。提高原材料利用率问题是一个系统工程问题,需要从生产管理、优化下料、支持决策等方面提供完备的一体化解决方案。其中优化下料环节中,构造有效的优化算法是关键。矩形件排样不仅适用于矩形零件的排放,而且也是不规则零件排放的基础。本文研究的问题是无约束非剪切单一卷材矩形件的优化下料,其中卷材为定宽无限长,要排放的矩形件数量和规格都是已知的,要求在排放完所有给定矩形件的前提下使所消耗的卷材长度最小。遗传算法是借鉴生物的自然选择和进化机制的一种全局优化自适应概率搜索算法,具有快速随机的全局搜索能力。对于非常复杂、高度非线性问题的优化求解,表现出比其它传统优化方法更优越的性能,是21 世纪智能计算中的核心技术之一。本文对遗传算法做了系统介绍,包括遗传算法的特点、基本实现技术等。对求解矩形件优化排样问题的遗传算法的设计及具体实现进行了详细讨论。本文所做的主要工作如下: 分析了排样问题的研究现状,对中外学者在矩形件优化排样方面提出的多种算法进行了认真的比较,在矩形件排放算法-“基于最低水平线的搜索算法”基础上,提出了一种改进算法:“基于最低水平线的空闲区域可再利用搜索算法”,它克服了其它排放算法对某些排样图不能给出的缺点,满足“最左最下”条件。改进算法和原算法相比,改进之处表现在:能够对最低水平线发生提升时产生的废弃空闲区域进行回收利用,通过对矩形件排放过程中动态产生的空闲区域的位置关系进行判断,改进算法能够对相邻的空闲区域进行有效合并,通过对空闲区域进行适当的填充从而实现对空闲区域的再利用,因此能够在一定程度上提高卷材的利用率。通过比较要排放矩形件的长宽与空闲区域的尺寸大小,最终确定矩形件的较优排放次序及矩形件在卷材上的确切排放位置。本文把“基于最低水平线的空闲区域可再利用搜索算法”和遗传算法结合起来,共同求解矩形件优化排样问题:先通过遗传算法确定矩形件较优的排放顺序和排放方式,然后按照“基于最低水平线的空闲区域可再利用搜索算法”生成排样图,通过比较不同的矩形件排放序列对应的卷材利用率,最终得到较优的排样方案。根据提出的改进算法,开发出了计算机辅助优化排样系统,测试数据表明了改