多块排样方式的二维板材下料优化模型与算法  

Optimization Model and Algorithm of Two-dimensional Plate Guillotine Cutting Stock Problem Based on Multiple-block Layout

作　　者：潘卫平 樊治平[2,4] 黄敏 计明军[1] PAN Weiping;FAN Zhiping;HUANG Min;JI Mingjun(Transportation Management College,Dalian Maritime University,Dalian 116026,China;School of Business Administration,Northeast University,Shenyang 110169,China;College of Information Science and Engineering,Northeastern University,Shenyang 110819,China;State Key Laboratory of Synthetical Automation for Process Industries,Northeastern University,Shenyang 110819,China)

机构地区：[1]大连海事大学交通运输工程学院,辽宁大连116026 [2]东北大学工商管理学院,辽宁沈阳110169 [3]东北大学信息科学与工程学院,辽宁沈阳110819 [4]东北大学流程工业综合自动化国家重点实验室,辽宁沈阳110819

出　　处：《运筹与管理》2024年第4期56-62,共7页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(71971035);国家自然科学基金重点国际合作研究项目(71620107003);辽宁省“兴辽英才计划”(XLYC1802115);流程工业综合自动化国家重点实验室基础科研业务费专项资金项目(2013ZCX11);中央高校基本科研业务费专项资金项目(N2106008)。

摘　　要：针对矩形件二维板材剪切下料问题,提出一种多块排样方式的二维板材下料优化模型与求解算法。为了均衡考虑排样方式的计算复杂度和板材利用率,将多块排样方式的块数定为八块。通过3次一分为二剪切操作将板材分割成八个矩形块,并将每个块剪切成方向相同的同种矩形件。构造八块排样的优化模型及算法是按照排样价值最大原则来确定所有可能尺寸的块中矩形件的最优布局和板材的最优八块划分。提出的列生成算法迭代调用上述八块排样算法生成一系列下料方案,选择耗费板材最少的一个下料方案作为最终解。通过采用文献基准例题和实际生产实例验证了本文算法,实验结果表明:八块排样算法的排样价值高于3种文献排样算法,并且,八块排样方式的下料算法板材利用率高于已有文献给出的下料算法。本文给出算法计算时间可满足实际应用需要。The two-dimensional cutting problem of rectangular plates refers to cutting several types of rectangular parts from a set of plates,and minimizing the number of plates used while ensuring that the demand for each type of rectangular part is met.This problem has a wide range of applications in the industrial field.A good cutting plan can improve the utilization rate of plate metal,reduce production costs,and enhance the competitiveness of enterprises.The cutting plan generally consists of multiple layouts,each of which provides the layout of rectangular parts on a single plate of material.Therefore,the two-dimensional cutting problem of rectangular plates includes two combinatorial optimization problems:the one is determining the layout by combining rectangular parts on a single plate;the other is combining the feasible layouts in the set to determine the cutting plan.The commonly used methods for solving the cutting problem of two-dimensional rectangular plates can be divided into three types.The first type is the integer programming method.The second type is the sequential heuristic method.This method generates a layout using the remaining rectangular parts to meet the partial demand for the rectangular parts,and repeats the process until all the demands for the rectangular parts are met.The third type is the linear programming method.Due to a large number of decision variables in the model,it is difficult for the integer programming method to calculate solutions for medium to large-scale cutting problems in a reasonable time.Sequential heuristic algorithms are generally used for cutting problems with low demand for rectangular parts.For cutting problems with high demand for rectangular parts,the calculation time is too long and it is difficult to meet practical application requirements.The utilization rate of the cutting plan generated by the linear programming method and the complexity of the cutting process depend on the layout used.The two-dimensional plate cutting stock problem of rectangular parts is discu

关 键 词：二维板材下料 矩形件 八块排样方式 列生成算法 板材利用率 

分 类 号：TH164[机械工程—机械制造及自动化]