Title: A cooperative algorithm for constrained two-staged two-dimensional cutting problems

Authors: Mhand Hifi, Toufik Saadi

Addresses: Universite de Picardie Jules Verne, UFR des Sciences, MIS, Optimisation Discrete et Reoptimisation, 33 rue Saint Leu, Amiens 80000, France. ' Universite de Picardie Jules Verne, UFR des Sciences, MIS, Optimisation Discrete et Reoptimisation, 33 rue Saint Leu, Amiens 80000, France

Abstract: 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.

Keywords: beam search; cutting stock; knapsack; optimisation; strip generation; 2D cutting problems; two-staged cutting problems; search strategy; fast filling procedure; upper bound; cooperative algorithms.

DOI: 10.1504/IJOR.2010.034363

International Journal of Operational Research, 2010 Vol.9 No.1, pp.104 - 124

Published online: 01 Aug 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article