Premium
Algorithms for the circular two‐dimensional open dimension problem
Author(s) -
Akeb Hakim,
Hifi Mhand
Publication year - 2008
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2008.00655.x
Subject(s) - heuristics , heuristic , dimension (graph theory) , simple (philosophy) , position (finance) , mathematical optimization , series (stratigraphy) , computer science , interval (graph theory) , packing problems , beam search , mathematics , algorithm , search algorithm , combinatorics , paleontology , philosophy , epistemology , finance , economics , biology
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.