Heuristics for the integer one-dimensional cutting stock problem: A computational study

In this paper the problem of generating integer solutions to the standard one-dimensional cutting stock problem is treated. In particular, the authors study a specific class of heuristic approaches that have been proposed in the literature, and some straightforward variants. These methods are compared with respect to solution quality and computing time. The present evaluation is based on having solved 4,000 randomly generated test problems. Not only will it be shown that two methods are clearly superior to the others but also that they solve almost any instance of the standard one-dimensional cutting stock problem to an optimum.