APS排程：二维排样优化算法

编辑导语： 二维排样问题普遍存在于工程领域中，如钣金下料、玻璃切割、造船、车辆、家具生产、报刊排版、服装和皮革裁剪等。最优的排样方案可以最大限度地节约材料、提高材料利用率，在经济上制造可观的效益。排样问题属于典…

二维排样问题普遍存在于工程领域中，如钣金下料、玻璃切割、造船、车辆、家具生产、报刊排版、服装和皮革裁剪等。最优的排样方案可以最大限度地节约材料、提高材料利用率，在经济上制造可观的效益。排样问题属于典型的组合优化问题，从理论上讲，该类问题属于具有最高计算复杂性的优化计算问题，即NP完全问题。对于NP完全问题，以目前计算理论和方法，在可行的时间界限内不可能找到问题的最优解，只能求其局部最优的近似解。

下料工序的生产计划是二维排样与排产优化综合问题，不仅仅根据物料的形状进行排样，同时也要考虑料号的生产计划或者交货期，因此排样+排产同时考虑。APS智能排产系统需要整合国内顶尖的排样引擎，实现二维排样与排产计划联动，有效解决下料工序的生产计划难题，效果如下图所示。

排样算法的基础有三层，分别是底层几何算法、排样策略、优化算法。

一、底层几何算法"font-size: 12pt;">一、底层几何算法">一、底层几何算法

底层的几何算法是指多边形之间的位置、距离这类的算法，由于排料策略和优化算法的不同，衍生出很多替代或者变相的多边形位置、距离等算法。比如以多边形重叠面积来衡量多边形之间的关系，或者是多边形互相“侵入”的某个方向的长度来表达多边形之间的关系。还有NFP算法，NFP算法不仅让多边形之间的位置判断更加快速，也提供了更多的排料策略选择。

二、排样策略"font-size: 12pt;">二、排样策略">二、排样策略

排料策略分两大类。第一类是初始解是可行解，第二类是初始解可接受不可行解。最直观的看不可行解就是有重叠的。整个策略和算法会慢慢移除重叠，当然移除方法依据都有很多种类。对于第一类的排样策略，很好理解，比如传统的左底排放策略，虽然它不是很有效，但也算是种策略。再看第二类的排样策略，现在我们就能理解为什么需要计算多边形的重叠关系了，它是多边形移动方向和移动距离大小的依据。这个时候NFP算法也常能带来很好的效果。

三、优化算法"font-size: 12pt;">三、优化算法">三、优化算法

优化算法这个层次相对来说影响并不大，这是仅对于第一类排样策略。因为第一类排样策略大部分是基于调序优化的，对于这种转化为组合优化的问题，实际上各类智能优化算法比如模拟退火、遗传算法等之间并没有很多差别。而对于第二来排样策略来说，更多的会采用传统优化算法（线性和非线性规划）和智能优化相结合的办法。

最近更新于 2022-05-14，由 猿小六 于 2021-10-15 发布，已阅 2257 次。