An augmented beam search-based algorithm for the circular open dimension problem

Abstract

In this paper, we discuss the circular open dimension problem (CODP); that is a problem of the cutting/packing family. In CODP, we are given an initial strip of fixed width W and unlimited length, as well as a finite set N of n circular pieces C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> of known radius r <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> , i isin N. The objective is to find a global optimum corresponding to the minimum length of the initial strip containing the n pieces. We propose an augmented algorithm for solving the CODP which combines a beam search, a binary search and the well known multistart strategy. In addition, in order to increase the efficiency of the algorithm, we incorporate a separate beams strategy instead of the pooled one. The performance of the proposed algorithm is evaluated on a set of benchmark instances: it improves several best known solutions of the literature.