A cooperative algorithm for constrained two-staged two-dimensional cutting problems. (2nd August 2010)

• Record Type: Journal Article
• Authors: Hifi, Mhand; Saadi, Toufik
• Is Part Of: International journal of operational research. Volume 9:Number 1(2010)
• Page Start: 104
• Page End: 124
• Publication Date: 2010-08-02
• Subjects: beam search -- cutting stock -- knapsack -- optimisation -- strip generation -- 2D cutting problems -- two-staged cutting problems -- search strategy -- fast filling procedure -- upper bound -- cooperative algorithms; Operations research -- Periodicals; 003.05
• Languages: English
• ISSNs: 1745-7645

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.