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

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_i of known radius r_i,i ∈ N. The objective is to search for 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 multi-start strategy. In addition, in order to increase the efficiency of the algorithm, we incorporate a strategy based on the separate beams instead of the pooled ones. The performance of the proposed algorithm is evaluated on a set of benchmark instances composed of a group taken from the literature and another group of randomly generated instances. The results show that the proposed algorithm is able to improve several best known solutions of the literature and it remains competitive for the new generated ones.