优化排样是研究如何下料使得原材料利用率最高,在实际生产中应用广泛。服装制造业、皮革制品制造业、体育用品制造业、机械制造业等行业中存在大量的下料问题。国内有成千上万家这样的企业,绝大部分企业仍处于手工下料阶段,下料利用率较低,造成原材料的浪费。因此有效提高原材料的利用率,降低生产成本,是增加企业效益的有效途径之一。提高原材料利用率问题是一个系统工程问题,需要从生产管理、优化下料、决策支持等方面提供完备的一体化解决方案。这些环节中优化下料方案是提高原材料利用率最直接的方法,而优化下料方案的关键是构造有效的优化排样算法。本文研究的是圆形件排样问题,是二维下料问题的一个分支。国内外对二维下料问题研究给予了足够的重视,多为矩形毛坯和二维不规则性毛坯的排样问题,而对圆形排样问题的研究较少。实际当中遇到圆形件排样问题时,常采用手工排样方案下料,这样的下料方法容易造成原材料的浪费。因此本文在借鉴其它二维下料问题算法的基础上,提出适合圆形件排样的算法。理论上可以采用传统的动态规划、线性整数规划方法、爬山法、分枝定界法等排样算法;也可以采用禁忌搜索、模拟退火算法、遗传算法、神经网络算法等现代优化算法。而传统的寻优方法只能解决实际应用当中的简单问题,对于稍微复杂的问题就需要向启发式的优化方法寻求解决方案。本文研究的圆形件排样问题,是指将卷材切成若干圆形毛坯,使所产生的废料尽可能地少。由于卷材长度远远大于毛坯直径,在算法设计时可以将其作为无限长处理。所排零件包括多种尺寸的圆形件,其需求必须精确满足。该问题已经被证明属于相当困难的NP 完全问题。本文提出一种排样算法(简称ASA),按指定的顺序,依次将圆形毛坯排列到卷材上。对于当前要排入卷材的毛坯,ASA 首先将可行位置的搜索范围进行离散,也就是选择搜索范围的一个子集进行搜索。这个子集比文献中的算法所考虑的搜索范围大,有利于提高解的质量。然后利用圆形件的形状特性,排样方式的性质等,避免对搜索范围中部分不可行区域的搜索,以缩短求解时间。ASA按指定的顺序将圆形毛坯排入卷材,因此所得排样方案的材料利用率,取决于给定的毛坯顺序。本文采用混合遗传算法(简称HGA)指导搜索,以考虑多种毛坯顺序。每种顺序对应一个排样方案,从中可选出材料利用率高的排样方案。基于毛坯编号进行编码;将随机技术与经验相结合生成初始群体;在进化