A breadth-first search applied to the minimization of the open stacks

Abstract

This paper presents a heuristic for the minimization of the open stacks problem (MOSP). The proposed heuristic is based on a simple breadth-first search in MOSP graphs and two new greedy rules to overcome errors. The performance of the proposed heuristic is compared with the best exact and heuristic methods available in the literature. The results show that in addition to the suggested heuristic having much shorter running times than the exact algorithm, the error gap between them is small for a substantial proportion of almost 4500 benchmark instances taken from the literature. The proposed heuristic also has a more robust behaviour than the best heuristic for the MOSP, although less accurate. The proposed heuristic therefore constitutes a viable and cost-effective alternative for solving or obtaining good upper bounds for the MOSP.

Keywords:

• cutting stock problem
• heuristics
• discrete optimization
• scheduling

Acknowledgements

The authors thank Maria Garcia de la Banda and Geoffrey Chu for kindly providing their source codes, Horacio H. Yanasse for his valuable discussions and the anonymous referees who helped improve the paper. This research was partially supported by CAPES, CNPq and grant 2009/51831-9 from FAPESP—This paper is dedicated in loving memory of Professor Alberto Caprara.