二维不规则件的排样优化问题是指在某形状(大多数为矩形)板材上排放多种大小规格不一的不规则件,不规则件之间在满足不相互重叠、同时也不超出板材边界的前提下,使得利用率尽可能地大。这一问题广泛存在于服装、钢材、家具、玻璃、机械制造等领域,与工厂的成本管理息息相关。因此,本论文的研究具有实际的应用价值。排样问题是一个典型的NP难问题,仍没有算法能在短时间内找到最优解。针对目前排样问题中普遍遇到的难点,本文采用基于临界多边形和并行遗传算法的方法对二维不规则件进行排样,并通过C++编程语言、Qt框架和OpenMP并行库实现了程序,主要工作如下:(1)运用马尔可夫链的数学模型研究了遗传算法,并简要证明了遗传算法的收敛性,给本文的算法补充了理论基础,这是本文的第一个创新点。(2)根据排样问题的特点,对排样数据进行编码,并设计了选择算子、交叉算子和变异算子。编码方面,采用十进制编码,该编码能最大限度保存排样的原始信息,并易于编程。选择算子方面,采用直接选优的方法,并阐述采用该选择算子的意义;在交叉算子方面,采用ordercrossover的交叉算子,尽可能减小运算量,以节省算法的时间。变异算子方面,对角度进行变异操作。(3)编写了排样测试软件。根据排样问题运算量大的特点,设计编写了排样程序的轻量级的模型层,一个轻量级的库能够让排样这种运算量特别大的程序运算更加快速。通过图形用户界面交互把临界多边形显示出来,有助于研究不同形状不规则件对排样效果的影响,这是本文的第二个创新点。在算法具体设计中,通过缓存技术很好地处理了每一代排样中重复计算的一些问题,把运算时间大大降低,这是本文的第三个创新点。(4)通过在程序中调整并行遗传算法参数,阐述了如何在并行遗传算法的利用率与运算时间中进行权衡取舍,并通过软件直观展示出来。(5)通过采用欧洲排样问题兴趣小组ESICUP提供的部分基准问题进行对比测试,取得了不错的效果,排样利用率与国外的对比算法的利用率不相上下,在部分数据的测试甚至超过了国外的对比算法。与国内的文献比较,排样利用率超过了部分文献得出的利用率。