Pattern-set generation algorithm for the one-dimensional multiple stock sizes cutting stock problem

Abstract

A pattern-set generation algorithm (PSG) for the one-dimensional multiple stock sizes cutting stock problem (1DMSSCSP) is presented. The solution process contains two stages. In the first stage, the PSG solves the residual problems repeatedly to generate the patterns in the pattern set, where each residual problem is solved by the column-generation approach, and each pattern is generated by solving a single large object placement problem. In the second stage, the integer linear programming model of the 1DMSSCSP is solved using a commercial solver, where only the patterns in the pattern set are considered. The computational results of benchmark instances indicate that the PSG outperforms existing heuristic algorithms and rivals the exact algorithm in solution quality.

Keywords:

• cutting and packing
• one-dimensional cutting stock
• column generation
• CPLEX solver

Acknowledgements

This research is part of Projects 71371058 and 61363026, supported by the National Natural Science Foundation of China. It is also part of Project 201010LX003, supported by the scientific research of the universities in Guangxi of China.