Solving the circular open dimension problem by using separate beams and look-ahead strategies

摘要

In this paper, a constructive method is investigated for solving the circular open dimension problem (CODP), a problem of the Cutting and Packing family. CODP is a combinatorial optimization problem which is characterized by a set of circular pieces of known radii and a strip of fixed width W and unlimited length. The objective is to determine the smallest rectangle of dimensions (L, W), where L is the length of the rectangle, that will contain all the pieces such that there is no overlapping between the placed pieces and all the demand constraints are satisfied. The method combines the separate-beams search, look-ahead, and greedy procedures. A study concerning both restarting and look-ahead strategies is undertaken to determine the best tuning for the method. The performance of the method is computationally analyzed on a set of instances taken from the literature and for which optimal solutions are not known. Best-known solutions are obtained.