基于列生成和遗传算法的三阶段齐切割问题

打开文本图片集

中图分类号： TP391 文献标志码： A

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 programming model for two-dimensional guillotine cutting of sheet metal was established with the goal of maximizing 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 iteration， 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 utilization 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

0 引言

二维板材切割问题是一个典型的 NP-hard 问题，该问题具有较高的复杂性和应用性。（剩余13886字）