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

2021年10月15日 93 次阅读    本文共903字,预计阅读时间3分钟

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

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

二维排样算法展示
二维排样算法展示

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

一、底层几何算法

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

二、排样策略

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

三、优化算法

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

上一篇:

下一篇: