摘要

二维不规则排样问题属于平面布局优化问题，是指在给定的魇材料空间布局内，排放若干零件，且保证各个零件之间互不重叠。目标是寻找一个最优的排样方案，提高原材料的利用率。

基于矢量线段的临界多边形（NFP）生成算法研究：NFP算法是二维排样中的关键基础性问题，也是二维算法发展的瓶颈问题。

关键词

不规则排样，临界多边形，随机遗传算法；带缺陷的不规则原材料

Ch01 绪论

1.1 研究背景与意义

排样问题，也称为下料问题，排料问题，是一个在工业生产中有关广泛应用的重要问题。应用在给定的原材料的空间布局内，排放（切割）出若干符合要求的形状和大小的零件，各个零件的排放都互不重叠以，寻找一个最优的排放（布局）方案，使得原材料的利用率越高越好。

排样问题是典型的带几何约束的组合优化问题。

1.2 排样问题的分类

Coffman等人称排样问题为几何组合问题，将其是否以空间进行划分为依据把排样问题划分为狭义排样问题和广义排样问题。