Reducing the number of cuts in generating three-staged cutting patterns

• Published in: European journal of operational research 2012-04, Vol.218 (2), p.358-365
• Main Authors: Cui, Yaodong, Huang, Baixiong
• Format: Article
• Language: English
• Subjects: Applied sciences; Cost reduction; Cuts reduction; Cutting; Cutting stock problem; Exact sciences and technology; Flows in networks. Combinatorial problems; Linear programming; Manufacturing; Mathematical programming; Operational research and scientific management; Operational research. Management science; Optimization algorithms; Packing; Studies; Two-dimensional cutting
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2011.10.047

► We present a column-generation approach for the 2D cutting stock problem. ► Three-staged patterns are used and cuts reduction is considered in optimization. ► The approach can obviously reduce the number of cuts without increasing plate cost. Three-staged guillotine patterns are widely used in the manufacturing industry to cut stock plates into rectangular items. The cutting cost often increases with the number of cuts required. This paper focuses on the rectangular two-dimensional cutting stock problem, where three-staged guillotine patterns are used, and the objective is to minimize the sum of plate and cutting costs. The column generation framework is used to solve the problem. It uses a pattern-generation procedure to obtain the patterns. The cutting cost is considered in both the pattern-generation procedure and the objective of the linear programming formulation. The computational results indicate that the approach can reduce the number of cuts, without increasing the plate cost.