Article ID: | iaor20105686 |
Volume: | 9 |
Issue: | 1 |
Start Page Number: | 104 |
End Page Number: | 124 |
Publication Date: | Aug 2010 |
Journal: | International Journal of Operational Research |
Authors: | Hifi Mhand, Saadi Toufik |
In this paper, we propose a cooperative algorithm for approximately solving the two-staged two-dimensional cutting stock problem (2TDC). We solve 2TDC by considering three key features: a search strategy, a fast filling procedure (FP) and a tighter complementary upper bound. Firstly, the search strategy uses a beam-search method which considers both priority and total cost evaluation operators. Secondly, the FP is used for improving the quality of the obtained results. Finally, a tighter upper bound is applied for refining the selected paths. The method is analysed computationally on a set of instances of the literature and compared to the results provided by several algorithms of the literature. Encouraging results have been obtained.