带剪刃长度约束的矩形件剪切下料优化算法

讨论矩形件二维下料问题,提出一种带剪刃长度约束的下料算法。这种算法将板材划分成四块,每块中排放长度和方向均相同的条带,每根条带中排放同种矩形件。运用递归技术构造四块排样方式的无约束生成算法和有约束生成算法。采用线性规划算法调用无约束生成算法生成第一部分下料方案;采用顺序启发式算法调用有约束生成算法生成第二部分下料方案。组合两部分下料方案形成最终解。数值实验结果表明下料算法有效地解决带剪刃长度约束的下料问题。

Optimization algorithm of rectangular items two dimensional guillotine cutting stock problem with blade length constraint

Discuss the rectangular items two-dimensional cutting stock problem. An algorithm of guillotine cutting stock problem with blade length constraint was proposed. The algorithm divides the sheet into four blocks, each block contains strips with the same length and direction, each strip contains identical rectangular items. Firstly, unconstrained algorithm and constrained algorithm for generate four-block pattern were constructed by using the recursive technique.Then, linear programming algorithm was used to call the unconstrained packing algorithm to generate the first part cutting plan, and sequential heuristic algorithm was used to call the constrained packing algorithm to generate the second part cutting plan. Finally, the two parts cutting plan was combined to form the final cutting plan. The results of numerical experiments show that this algorithm can effectively solve the two dimensional guillotine cutting stock problem with blade length constraint.