Column Generation Algorithms forTwo-dimensional Cutting Problem With SurfaceDefects

Abstract

This work investigates a two-dimensional cutting problem arising from the cutting process of plate products, in which order plates of given sizes are to be cut from a finite number of mother plates that contain several surface defects. Placement of order plates on a mother plate is restricted by defects of varying severity located on the mother plate as well as the quality grades of order plates to be cut. We adopt a two-staged guillotine cutting mode, where the first-staged cutting position is determined by a width permutation scheme. Considering the allocation intervals of order plates, we first formulate the problem as a mixed-integer programming model that aims at maximizing the total revenue of a steel plant. Then, we present a column generation-based (CG-based) algorithm to solve it. To further improve its performance, we devise an accelerated CG (ACG) algorithm that embeds three heuristic accelerating strategies in the pricing process. At last, we test the proposed algorithms by a series of randomly generated instances, which are constructed according to actual production rules. The experimental results show that ACG algorithm can effectively solve large-sized instances.