二维非规则带排样问题,就是给定一个平面布局空间和若干形状不规则的待排件,在满足彼此不重叠的前提下,将待排件摆放在布局空间中,使得材料的利用率最高。排料问题是一个应用极为广泛的问题,在轻工业制造、航空航天、皮革、服装等行业均有涉及。排样结果的优劣直接关系到企业的生产效益。理论上,二维排料问题属于组合优化问题,涉及到计算机图形学和运筹学等多领域的知识,是属于具有最高计算复杂度的NP完全问题,具有重要的研究和实用价值。本文对二维非规则带排样过程中的关键问题进行了深入研究,主要的研究工作如下:1、给出了基于最小移动距离的定位算法,抛弃了NFP(No-Fit-Polygon)预处理和相应的判交方法,采用了更简单直观的多边形碰撞算法,极大地降低了整体的计算消耗时间;2、在经典的BL算法的基础上,根据已排件顶点作为步长递增标准,将原有的定长步长的方式改为不定长步长的方式;并提出了滑动区域、二次滑动等概念,有效地提高排样速度和排样效果;3、针对于BL算法过程中造成的空白区域的问题,提出了可充分填充空白区域的反向检测算法,提高了原材料的利用率;4、在上述工作的基础上,给出了二维非规则带排样算法,并对其进行了数值实验和对比分析。本文所提启发式算法克服了现代智能优化算法运行不稳定的弊端,力求对同一输入样本(待排件),执行算法都可以得到绝对稳定的输出结果(排料布局)以及相对稳定的运行时间。数值结果表明,本文所提算法能够有效地提高材料利用率并极大地降低整体时间消耗。