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

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 in this paper 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 are obtained by applying inequality constraints on the number of parts by 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.

     

/

返回文章
返回