Algorithms for the circular two-dimensional open dimension problem

Authors: Akeb, Hakim; Hifi, Mhand

Source: International Transactions in Operational Research, Volume 15, Number 6, November 2008 , pp. 685-704(20)

Buy & download fulltext article:

Price: $48.00 plus tax (Refund Policy)

Abstract:

In this paper, we propose three heuristics for the circular two-dimensional open dimension problem, also known as the circular strip cutting/packing problem. We first propose an open strip generation solution procedure that uses the best local position rule into the open strip. Second, we propose a simple augmented version of the first heuristic by introducing an exchange-order strategy. Third, we propose a hybrid heuristic that combines beam search and a series of target values belonging to a predetermined interval search. We evaluate the performance of these heuristics on several instances varying from small to large ones. Encouraging results have been obtained.

Keywords: beam search; best local position; binary search; strip cutting/packing; open dimension

Document Type: Research article

DOI: http://dx.doi.org/10.1111/j.1475-3995.2008.00655.x

Affiliations: 1: Institut Supérieur du Commerce, 22 Bd du Fort de Vaux, 75017 Paris, France

Publication date: 2008-11-01