Home // ADAPTIVE 2010, The Second International Conference on Adaptive and Self-Adaptive Systems and Applications // View article

An Adaptive Look-Ahead Strategy-Based Algorithm for the Circular Open Dimension Problem

Authors:
Hakim Akeb
Mhand Hifi

Keywords: beam search, cutting and packing, look-ahead, minimum local-distance position, multi-start strategy.

Abstract:
In this paper, we study the circular open dimension problem, a well-known combinatorial optimization problem of the cutting and packing family. We are given a set of circular pieces (or circles) of known radii and a strip of fixed width and unlimited length. The objective is to determine the minimum length of the initial strip that packs all the circular pieces. The problem is approximately solved with an adaptive look-ahead strategy-based algorithm, which combines greedy procedures, restarting and separate beams strategies, and a look-ahead search. The running experiments show, on a set of benchmark instances of the literature, the effectiveness of the proposed method. For these instances, the proposed algorithm improves 10 results out of 18.

Pages: 158 to 163

Copyright: Copyright (c) IARIA, 2010

Publication date: November 21, 2010

Published in: conference

ISSN: 2308-4146

ISBN: 978-1-61208-109-0

Location: Lisbon, Portugal

Dates: from November 21, 2010 to November 26, 2010