Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths

This paper deals with the classical one-dimensional integer cutting stock problem, which consists of cutting a set of available stock lengths in order to produce smaller ordered items. This process is carried out in order to optimize a given objective function (e.g., minimizing waste). Our study deals with a case in which there are several stock lengths available in limited quantities. Moreover, we have focused on problems of low demand. Some heuristic methods are proposed in order to obtain an integer solution and compared with others. The heuristic methods are empirically analyzed by solving a set of randomly generated instances and a set of instances from the literature. Concerning the latter. most of the optimal solutions of these instances are known, therefore it was possible to compare the solutions. The proposed methods presented very small objective function value gaps. (C) 2008 Elsevier Ltd. All rights reserved.

Fundacao de Amparo a Pesquisa do Estado de Sao Paulo (FAPESP)

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Conselho Nacional de Desenvolvimento Cientifico e Tecnologico (CNPq)

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)