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