Column generation and sequential heuristic procedure for solving an irregular shape cutting stock problem

Xiang Song, J. A. Bennell

Research output: Contribution to journalArticlepeer-review


The research addressing two-dimensional (2D) irregular shape packing has largely focused on the strip packing variant of the problem. However, it can be argued that this is a simplification. The materials from which pieces are required to be cut will ultimately have a fixed length either due to the physical dimensions of the material or through constraints on the cutting machinery. Hence, in order to cut all the pieces, multiple sheets may be required. From this scenario arises the 2D irregular shape cutting stock problem. In this paper, we will present implementations of cutting stock approaches adapted to handle irregular shapes, including two approaches based on column generation (CG) and a sequential heuristic procedure. In many applications, setup costs can be reduced if the same pattern layout is cut from multiple sheets; hence there is a trade-off between material waste and number of patterns. Therefore, we describe the formulation and implementation of an adaptation of the CG method to control the number of different patterns. CG is a common method for the cutting stock problem; however, when the pieces are irregular the sub-problem cannot be solved optimally. Hence we implement CG and solve the sub-problem using the beam search heuristic. Further, we introduce a version of CG for instances where the number of rows is less than the number of columns.
Original languageEnglish
Pages (from-to)1037-1052
JournalJournal of the Operational Research Society
Early online date8 May 2013
Publication statusPublished - 2014


Dive into the research topics of 'Column generation and sequential heuristic procedure for solving an irregular shape cutting stock problem'. Together they form a unique fingerprint.

Cite this