郑州大学学报（理学版）2025，Vol.57Issue(4)：63-70,8.DOI:10.13705/j.issn.1671-6841.2023226
基于列生成和遗传算法的三阶段齐切割问题
Three-stage Guillotine Cutting Problem Based on Column Generation and Genetic Algorithm
摘要
Abstract
In industrial customized production,the three-stage guillotine cutting layout method is often used,and a complete product must be cut after three stages.To address this issue,a mixed integer pro-gramming model for two-dimensional guillotine cutting of sheet metal was established with the goal of max-imizing sheet metal utilization.The three-stage cutting problem was abstracted as a sorting problem with size constraints.In the first stage,two cutting methods were used:horizontal and vertical cutting.The cut product items could be placed at 0° or 90°,and the subsequent two stages of cutting must meet the requirement of no overlap between any two product items.To improve solution efficiency,the model was decomposed into a main problem and several sub problems,and an iterative re-optimization framework and algorithm for genetic algorithm and column generation were proposed to solve the problem.In each it-eration,the genetic algorithm could provide multiple columns that met the conditions and added them as new columns to the main problem.In addition,the algorithm could re-optimize solutions with low utiliza-tion of sheet metal,improving the possibility of transforming the inferior solution to the optimal solution.The experimental results showed that in small-scale examples,the model could obtain accurate solutions.The proposed algorithm achieved a plate utilization rate of over 85％in large-scale examples,with a short solving time and could meet the requirements of industrial production.关键词
三阶段齐切割/混合整数规划/列生成算法/遗传算法Key words
three-stage guillotine cutting/mixed integer programming/column generation algorithm/genetic algorithm分类
计算机与自动化引用本文复制引用
冀荣根,胡志华,田曦丹,魏月荷..基于列生成和遗传算法的三阶段齐切割问题[J].郑州大学学报（理学版）,2025,57(4):63-70,8.基金项目
国家自然科学基金面上项目(71871136) （71871136）
上海市自然科学基金面上项目(23ZR1426500) （23ZR1426500）
