Hakim Akeb and Mhand Hifi
An Augmented Beamsearch Based Algorithm for the Strip Packing Problem
531 - 537
2010
4
6
International Journal of Industrial and Manufacturing Engineering
https://publications.waset.org/pdf/9043
https://publications.waset.org/vol/42
World Academy of Science, Engineering and Technology
In this paper, the use of beam search and lookahead strategies for solving the strip packing problem (SPP) is investigated. Given a strip of fixed width W, unlimited length L, and a set of n circular pieces of known radii, the objective is to determine the minimum length of the initial strip that packs all the pieces. An augmented algorithm which combines beam search and a lookahead strategies is proposed. The lookahead is used in order to evaluate the nodes at each level of the tree search. The best nodes are then retained for branching. The computational investigation showed that the proposed augmented algorithm is able to improve the best known solutions of the literature on most instances used.
Open Science Index 42, 2010