An Augmented Beam-search Based Algorithm for the Strip Packing Problem

Authors: Hakim Akeb, Mhand Hifi

Abstract:

In this paper, the use of beam search and look-ahead 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 look-ahead strategies is proposed. The look-ahead 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.

Keywords: Combinatorial optimization, cutting and packing, beam search, heuristic, look-ahead strategy.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072024

References:

[1] H. Akeb, and M. Hifi, "Algorithms for the circular two-dimensional open dimension problem," International Transactions in Operational Research, vol. 15, pp. 685-704, 2008.
[2] E. Baltacioglu, J.T. Moore, and R. R. Hill, "The distributor-s threedimensional pallet-packing problem: a human intelligence-based heuristic approach," International Journal of Operational Research, vol. 1, pp. 249-266, 2006.
[3] E. G. Birgin, J. M. Martinez, and D. P. Ronconi 2005, "Optimizing the packing of cylinders into a rectangular container: A nonlinear approach," European Journal of Operational Research, vol. 160, pp. 19-33, 2005.
[4] E. Burke, R. Hellier, G. Kendall, and G. Whitwell, "A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem," Operations Research, vol. 54, pp. 587-601, 2006.
[5] J. K. Cochran, and B. Ramanujam, "Carrier-mode logistics optimization of inbound supply chains for electronics manufacturing," International Journal of Production Economics, vol. 103, pp. 826-840, 2006.
[6] J. A. George, J. M. George, and B. W. Lamar, "Packing different-sized circles into a rectangular container," European Journal of Operational Research, vol. 84, pp. 693-712, 1995.
[7] M. Hifi, and R. M-Hallah, "A dynamic adaptive local search based algorithm for the circular packing problem," European Journal of Operational Research, vol. 183, pp. 1280-1294, 2007.
[8] M. Hifi, and R. M-Hallah, "Approximate algorithms for constrained circular cutting problems," Computers and Operations Research, vol. 31, pp. 675-694, 2004.
[9] M. Hifi, R. M-Hallah, and T. Saadi, "Beam search algorithms for constrained two-staged two-dimensional cutting problems," INFORMS Journal on Computing, vol. 20, pp. 212-221, 2008.
[10] W. Q. Huang, Y. Li, H. Akeb, and C. M. Li, "Greedy algorithms for packing unequal circles into a rectangular container," Journal of the Operational Research Society, vol. 56, pp. 539-548, 2005.
[11] W. Q. Huang, Y. Li, C. M. Li, and R. C. Xu, "New heuristics for packing unequal circles into a circular container," Computer and Operations Research, vol. 33, pp. 2125-2142, 2006.
[12] K. H. Kim, and J. B. Kim, . "Determining load patterns for the delivery of assembly components under JIT systems," International Journal of Production Economics, vol. 77, pp. 25-38, 2002.
[13] S. Menon, and L. Schrage, "Order allocation for stock cutting in the paper industry," Operations Research, vol. 50, pp. 324-332, 2002.
[14] P. S. Ow, and T. E. Morton, "Filtered beam search in scheduling," International Journal of Production Research, vol. 26, pp. 35-62, 1988.
[15] Y. G. Stoyan, and G. N. Yaskov, "Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints," International Transactions in Operational Research, vol. 5, pp. 45-57, 1998.
[16] K. Sugihara, M. Sawai, H. Sano, D. S. Kim, and D. Kim, "Disk packing for the estimation of the size of wire bundle," Japan Journal on Industrial and Applied Mathematics, vol. 21, pp. 259-278, 2004.
[17] G. W¨ascher, H. Haussner, and H. Schumann, "An improved typology of cutting and packing problems," European Journal of Operational Research, vol. 183, pp. 1109-1130, 2007.