二维排样问题在许多工业领域均有应用,比如:冲裁件加工、造船、服装、皮革切割等。排样效率的微小提升可为这些行业带来巨大的经济效益。另外排样算法属于一类组合优化问题,具有极高的计算复杂度,国内外学者对此进行了几十年持续不断的研究。二维不规则零件排样问题存在两大瓶颈:临界多边形(NFP)和计算机速度。多数排样算法都是基于NFP的,但其计算时间与零件类型数(N)和转角个数(RN)成平方关系,因此当零件数量很大或旋转角数目很多时,NFP的计算时间将成为一个巨大障碍。另外排样优化算法历来是一个需要多次迭代的耗时算法,排样优化问题为了得到一个较为理想的结果,往往需要几个小时的时间。针对以上问题,本文主要做了如下几个方面的工作。(1)提出了一种基于矢量格式的零件靠接算法,突破了“矢量图形靠接速度慢”的论断。该靠接算法包含两部分内容:多边形分离判据和进退法。多边形分离判据将多边形之间的相对关系归结为点与多边形的包含关系以及直线段之间相交关系。至于进退法,其思路如下:如果零件分离,则进;如果零件重叠,则退;直至靠接误差满足精度要求。本文通过一个算例证明了该算法的高效性。(2)提出了基于最小势能原理的不规则零件排样算法(HAPE),揭示了零件排样问题的物理意义:零件总是试图通过平移和旋转运动尽量降低零件的重心高度,从而得到更加紧密的排列。为了寻找最优排样姿态使零件重心最低,需要在母材上均匀布置一些点,让零件在每个点间隔一定的角度进行旋转。算例表明HAPE是可靠的,且物理意义明确,不需要计算临界多边形,可以处理任意不规则形状零件。(3)将HAPE与爬山算法(HC)和模拟退火算法(SA)结合产生了两种混合排样算法。通过大量测试和对比分析,研究了这两种混合算法的性能,尤其是RN以及PPD (排样点间距)对于排样密度的影响。对混合算法表现出来的“甜蜜”RN现象进行了初步的研究。(4)排样问题并行化在国内外尚处于前沿研究阶段。本文成功地将并行计算应用于不规则排样算法。测试结果表明并行技术能够大幅度提高排样的计算速度,但考虑到通信开销,并行计算更适合求解大规模排样问题。