论文部分内容阅读
本文的主要研究对象是二维不规则件排样问题，该问题普遍存在于现代生产制造业中的多个领域，如机械制造业、服装制造业、微电子排版等。在排样效果上的微小提高，即可节省大量的原材料，提高经济效益和缓解资源紧缺造成的环境压力。二维不规则件排样由于待排零件为不规则形状，其求解难点表现在不规则图形的碰撞检测和排放顺序、角度、位置的组合优化上。在碰撞检测方面，本文使用基于临界多边形的碰撞检测方法，在临界多边形的生成上采用了Burke等人提出的滑动生成算法的思想，并提出基于可能碰撞区的时间优化方法对该算法进行了有效的时间优化。理论分析得出，在求解问题的多边形平均边数e大于某值后，时间优化有效，且时间优化比率随e值的增加而增大。16个基准测试的结果证明了该理论分析的正确性。在所有测试中，正向时间优化比率平均为20.45%，最高时间优化比率为50.29%。在排样算法方面，本文提出了基于重心NFP与边适应度的GEF排放策略，并基于此策略结合FFDA选件策略、Weiler-Atherton多边形裁减算法提出了GEF启发式排样算法。算法经过16个基准测试，并在与两款商业软件的11个基准测试的对比中，获得了7/11个相对最优的排样面积利用率，充分证明了GEF启发式排样算法的排样能力。同时，本文采用孙艳丰提出的GATS混合智能算法的主要思想，结合本文的GEF启发式排样算法，研究并实现了GEF混合智能排样算法。在16个基准测试中，该算法的所有测试结果均优于GEF启发式排样算法，平均排样利用率提高比率为10.97%。在与现有的4个优秀智能排样算法的对比中，GEF混合智能排样算法在平均排样利用率方面接近现有算法的平均排样利用率，但在最优排样利用率方面与当前最优者有一定的差距。综合测试和对比结果，本文的GEF混合智能排样算法具有较好的排样能力。