矩形件优化排样问题是指在矩形的板材上,要排放多种不同尺寸的矩形件,如何使这些矩形件既不互相重叠,又不超出板材边界的条件下,使得材料的利用率达到最高。它广泛应用于玻璃、钢板、木材和皮革等。从数学计算复杂性理论看,优化排样问题属于具有较高计算复杂性的NP完全问题,至今还无法找到解决该问题的有效多项式时间算法[1]。好的排样结果可以提高生产效率,提高材料的利用率,降低生产成本,提高企业的竞争力。对矩形件优化排样问题的研究具有深远的理论意义和实际意义。本文在分析矩形件优化排样问题特点的基础上,建立了该问题的数学模型,描述了一些常见的优化算法和排样算法。在一定的约束条件下,应用遗传算法方法对矩形件排样问题进行优化求解,对算例的求解结果进行比较与分析。首先介绍了矩形件优化排样问题的数学模型和矩形件排样问题的排样算法,如剩余矩形匹配法、BL算法、下台阶算法、基于最低水平线的搜索算法。比较了这些算法的优缺点。其次介绍了在大规模生产中矩形件的下料工艺,如“一刀切”;为了提高生产效率,相同的零件尽可能排放在一起;在加工时,要有安全距离的保障等。再次介绍了遗传算法的基本原理,采用遗传算法对矩形件排样问题进行求解。在求解过程中,给出了遗传算法的编码与解码方法、适应度函数的定义方法、遗传算子的设计方法以及关键参数。通过对具体的算例进行求解,对求解的结果进行分析比较。最后,基于以上理论,用VB.NET开发了矩形件优化排样系统。其中包括用户登录模块,零件与板材管理模块,利用优化算法进行排样的模块等。本文将遗传算法与基于最低水平线的搜索算法相结合应用到矩形件排样优化中,产生的排样结果满足“一刀切”和相同的矩形件尽量排放在一起等工艺要求,并且使板材的利用率在94%左右,可以应用到企业的实际生产中。