矩形件排样问题指在给定的板材上排放所需要的矩形件,使板材的利用率最高,它是计算机辅助排样的一个重要分支。矩形件排样问题广泛存在于机械、家具、服装等国民经济行业,解决好该问题可以节省原材料,简化生产工艺,降低生产成本,增加企业效益。对于许多不规则零件的排样问题,也可通过计算机的图形处理技术将其转化为矩形件排样问题。但矩形件排样问题在理论上是属高计算复杂性的NP完全问题,在问题规模较大时,很难用精确算法求得最优解。因此,研究矩形件排样问题具有重要的实用和理论价值。粒子群优化算法是一种新型的仿生进化计算技术,源于对鸟群觅食行为的研究,由Eberhart博士和Kennedy博士于1995年提出,该算法的提出立刻引起了优化及演化计算等领域的学者们的广泛关注。粒子群优化算法已广泛应用于函数优化,神经网络训练,模式分类,模糊系统控制等领域。但当前粒子群优化算法的研究尚处于初期,该算法的基础理论和实际应用方面还有许多工作可做,以该算法为基础,改进该算法用于求解的实际问题有重要的意义。基于上述考虑,本文以粒子群优化算法为基础,提出了一种基于离散粒子群优化算法求解矩形件排样问题的新算法。通过大量的实例测试,验证了该算法的有效性。本文的主要工作和创新点如下:首先,改进了一种矩形件近似排样算法。对中外学者提出的几种近似排样算法进行了比较和分析,在总结其优缺点的基础上,对基于最低水平线的搜索算法进行了改进。基于最低水平线的搜索算法用矩形件编号的正负符号来判断矩形件是否旋转90度再排放,其实质是为了改变矩形件横放或竖放的排放方式,以便得到更多可排放在当前最低水平线上的矩形件,尽可能的减少最低水平线以上的空闲区域浪费。本文将矩形件的编码全部用正数表示。将最低水平线的宽度先与当前矩形件的宽度比较,若最低水平线的宽度大于矩形件的宽度,将矩形件排放在此位置;否则将最低水平线的宽度与当前矩形的长度比较,若最低水平线的宽度大于矩形件的长度,将矩形件旋转90度排放在此位置。若最低水平线的宽度小于当前矩形件的宽度和长度,则在排样序列的当前位置向后搜索,选择一个满足排放条件并且宽度或长度与最低水平线的宽度最接近的矩形件排放;否则,更新最低水平线。因为判断矩形件编码符号的计算过程和将最低水平线的宽度与矩形件的长度比较的计算过程的时间复杂度是相等的,所以改进的最低水平线搜索算法可以简化编码,扩大搜索范围和提高排样效率。其次,将改进的最低水平线搜索算法和离散粒子群优化算法结合,提出了一种基于离散粒子群优化算法求解矩形件排样问题的新算法。矩形件排样问题中如何产生排样序列是一个关键的问题,许多学者应用遗传算法,模拟退火算法等算法产生排样序列,再将产生的排样序列与某种矩形件近似排样算法结合求解矩形件排样问题,取得了较好的排样效果。离散粒子群优化算法是在基本粒子群优化算法基础上改进的一种算法。本文分析了离散粒子群优化算法,设计了应用离散粒子群优化算法求解矩形件排样问题的相关操作,定义了离散粒子群优化算法求解矩形件排样问题的适应度函数,详细介绍了怎样应用离散粒子群优化算法产生排样序列。将离散粒子群优化算法产生矩形件的排样序列,按照改进的最低水平线的搜索算法和本文的适应度函数得到排样序列的适应度值,并生成排样图。通过排样序列的适应度值的比较,从而得到一个较优的排样方案。然后,研究和开发了一个实用的矩形件优化排样系统。在完成算法设计的基础上,规划和设计了排样系统的基本功能模块,开发了一个基于离散粒子群优化算法的矩形件优化排样系统。通过大量实验测试,并将实验结果与应用遗传算法、模拟退火算法、随机算法求解矩形件排样问题的实验结果进行了比较和分析,从板材利用率和排样时间两方面验证了该系统的算法的有效性。最后,论文在对己完成的工作进行了总结,提出了需要进一步改进的工作。