排样问题是一种组合优化问题,即在固定的母版上,尽可能多的放置待排样片,样片之间相互不重叠且不超出母版范围。排样问题在制造业有着广泛的应用,例如在服装制造行业,皮革加工行业,家具制造业等,因此研究这个问题有着很大的实用价值。在不规则排样问题中,不仅待排样片的形状是不规则的,母版形状也是不规则多边形,这种不规则势必造成计算复杂度增加,排样效率下降,材料利用率降低。对不规则样片排样算法的研究主要是为了在满足工艺要求的基础上,提高板材的利用率,减少排样时间。本文主要针对不规则样片排样过程中算法复杂度较高,材料利用率较低的情况,提出了重心最低与重心集中的分区排样策略,并对求解的方案通过粒子群算法进行优化和检测优化,最终实现改进不规则排样算法的目的。论文主要工作如下:1.在结合工艺要求的条件下,提出求解不规则排样问题的思路。采用临界多边形来判断两个不规则样片的位置关系,减少了求交的运算量,同时采用基于重心的临界多边形应用于样片的定位策略。2.针对工艺要求,本文提出分区排样策略,在不同的质量区域采用不同的排样策略。在高品质的一级区域采用基于临界多边形的下沉式策略,二级区域采用基于重心集中的策略,使排样结果满足一级区域重心最低,二级区域上的样片更加集中分布。3.针对基础粒子群算法不能很好适应不规则排样问题的求解,本文提出了多级优化策略,即包括粒子群优化和检测优化,对不规则样片的排样效果进行优化。该策略在寻求最优排样结果方面具有搜索范围更广的优势。在优化的过程中,设计两种粒子的编码,并结合改进的排样策略来决定样片的最优位置,然后在排样结果上采用检测优化缩小间距,提高排样结果的质量。4.设计并实现了不规则排样的系统,在该系统中实现了上述算法,同时验证了这种排样策略与优化模式在提高母版的利用率上有着一定提高。