求解一维下料问题精确解的分步式优化算法

A Step-by-step Optimization Algorithm for Solving the Exact Solution of One-Dimensional Cutting Stock Problem

  • 摘要: 为适应企业的数字化转型,针对使用线性规划方法求解一维下料问题的过程中,难以生成所有可行切割模式而采用不等式约束求解,导致结果与需求订单中零件数量不一致的问题,提出了一种求解一维下料问题精确解的分步式优化算法。首先,通过限制切割模式数量和利用率的有限切割模式模型对零件数量作不等式约束求解得到初步结果;然后,通过对结果进行两次筛选得到一个包含多余零件的切割模式组成的最优切割模式集合;最后,再将最优切割模式集合拆分成子问题,对子问题采用生成所有可行切割模式并对零件数量作等式约束求解的方法,得到一维下料问题的精确解。计算结果表明,应用分步式优化算法计算的结果准确的对应零件的种类和数量需求,计算速度更快,适应性更广。

     

    Abstract: To adapt to the digital transformation of enterprises, a step-by-step optimization algorithm (SOA) is proposed to solve the one-dimensional cutting stock problem using the linear programming method, which is difficult to generate all feasible cutting patterns and solve with inequality constraints, resulting in inconsistent results with the number of parts in the demand order. Firstly, Preliminary results were obtained by applying inequality constraints on the number of parts using a finite cutting pattern model that limits the number and utilization of cutting patterns; Then, by filtering the results twice, an optimal set of cutting patterns consisting of cutting patterns containing excess parts is obtained; Finally, the optimal cutting pattern set is split into subproblems, which are solved by generating all feasible cutting patterns and applying equality constraints to the number of parts to obtain the exact solution of the one-dimensional cutting stock problem. The calculation results show that the application of the step-by-step optimization algorithm accurately corresponds to the type and quantity requirements of the parts, with faster calculation speed and wider adaptability.

     

/

返回文章
返回