基于列生成的三阶段二维板材切割优化
Three-stage Two-dimensional Plate Cutting Optimization Based on Column Generation
张欣 1金月1
作者信息
- 1. 天津工业大学经济与管理学院,天津 300387
- 折叠
摘要
在大规模定制生产需求的背景下,对于方形件产品制造企业来说,面对一组多品种、小批量的矩形产品订单,如何生成科学合理的排样方案,以最小化使用板材的数量,从而有效降低企业下料生产调整费用、提高生产效率,是一个具有挑战性的现实问题.针对具有齐头切约束的二维板材下料问题,以最小化使用的板材数量为目标,建立基于各切割阶段的长宽限制、产品项的完整性和齐头切等约束条件的三阶段二维矩形板材排样的整数规划模型.为求解该模型设计了基于列生成的算法,将原问题分解为限制主问题和子问题,子问题为生成满足约束并可能提高板材利用率的排样方案,限制主问题为获取最优排样组合.算例分析结果验证了模型的有效性和可行性.结果表明,在大规模算例下,所设计的算法不仅能明显提高求解效率,还能得到更具优势的排样方案.
Abstract
In the context of mass customization,this is a challenging class of real-world problems where,given a set of predefined widths and heights of rectangular items for a square part manufacturer,the goal is to minimize the number of used plates,and to generate the cutting patterns to cut all demanded pieces,so as to effectively reduce the adjustment cost and improve the production efficiency of the enterprise. In order to minimize the number of plates used,a three-stage integer programming model is developed for 2D rectangular plate layouts with constraints on the length and width of each cutting stage,the completeness of the product item,and the guillotine cuts,etc. Further,a column generation-based algorithm is designed for solving the model,decomposing the original problem into a restricted master problem and a subproblem,where the subproblem is to generate a cutting pattern that satisfies the constraints and may improve the utilization of plates,and the restricted master problem is to obtain the near optimal solution. The validity and feasibility of the model are verified by the results of the arithmetic examples. The results show that the designed algorithm can not only significantly improve the solution efficiency but also obtain a more advantageous nesting solution under large-scale cases.
关键词
板材切割/二维装箱/齐头切/列生成Key words
plate cutting/two-dimensional bin packing/guillotine cut/column generation引用本文复制引用
出版年
2024
NETL
NSTL
万方数据