An Augmented Beam-search Based Algorithm for the Strip Packing Problem
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.
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:58115", author = "Hakim Akeb and Mhand Hifi", title = "An Augmented Beam-search Based Algorithm for the Strip Packing Problem", 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.", volume = "4", number = "6", pages = "511-7", }
