排样问题属于下料、布局问题,广泛存在于机械制造、造船、汽车、航空、轻工等行业。传统的手工排样存在效率低、质量依赖于排样人员经验等缺陷。计算机辅助排样(Computer Aided Nesting,CAN)克服了手工排样的缺点,具有排样速度快,质量好且稳定的特点。采用CAN有助于提高企业的生产效率,降低企业的生产成本,增强企业的市场竞争力。因此,对计算机辅助排样技术的研究具有十分重要的意义。 目前,对于一维和一维半排样问题,通过现行规则已基本上得到解决,矩形排样的方法已比较成熟,而二维不规则形状零件的排样还在进一步探索之中,成为当前研究的热点。 本文总结了平面零件排样的类型及其相应的计算机辅助排样方法;对不规则零件在不规则板料上的复杂排样问题进行了新的探索;最后探讨了通用排样软件的开发方法。本文主要研究内容为: 1.一种应用于不规则零件排样的快速解码算法的设计。在利用遗传算法解决平面不规则零件排样的过程中,需要对个体进行解码。该算法首先平行线化零件和板料,然后采用左下角策略驱动零件在板料上向x,y两个方向移动;引入零件之间的顶点碰撞特性,以加快获得零件在x方向上的定位坐标;提出板料基线提高策略,以加快获得零件在y方向上的定位坐标。实验表明,该算法解码速度快,易于实现。 2.两种应用于平面不规则零件排样的并行遗传算法模型的设计。这两种模型是针对遗传算法在排样应用中计算量很大的缺陷而设计的。两种模型均建立在局域网环境中,以客户机/服务器结构为主框架。第一种是主从式模型,服务器协调遗传算法的并行运行,将种群中的个体发送到客户机;客户机负责解码计算以获得个体适应度,并将适应度发回服务器。第二种是粗粒度模型,种群被分散到多个客户机上形成子种群,并在客户机中独立进行子种群进化;采用无约束迁移策略驱动子种群间优秀个体的传播。实验表明,应用主从式模型可以大大加快遗传算法的运行速度;应用粗粒度模型不但可以加快计算速度,而且还可以提高解的质量。