{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T22:20:53Z","timestamp":1775082053934,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2005,12,31]]},"abstract":"<jats:p>In this paper, we consider the two-dimensional rectangular strip packing problem. A standard simple heuristic, Bottom-Left-Decreasing (BLD), has been shown to perform quite well in practice. We introduce and demonstrate the effectiveness of BLD*, a stochastic search variation of BLD. While BLD places the rectangles in decreasing order of height, width, area, and perimeter, BLD* successively tries random orderings, chosen from a distribution determined by their Kendall-tau distance from one of these fixed orderings. Our experiments on benchmark problems show that BLD* produces significantly better packings than BLD after only 1 min of computation. Furthermore, we also show that BLD* outperforms recently reported metaheuristics. Furthermore, we observe that people seem able to reason about packing problems extremely well. We incorporate our new algorithms in an interactive system that combines the advantages of computer speed and human reasoning. Using the interactive system, we are able to quickly produce significantly better solutions than BLD* by itself.<\/jats:p>","DOI":"10.1145\/1064546.1083322","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":32,"title":["New heuristic and interactive approaches to 2D rectangular strip packing"],"prefix":"10.1145","volume":"10","author":[{"given":"N.","family":"Lesh","sequence":"first","affiliation":[{"name":"Mitsubishi Electric Research Laboratories, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Marks","sequence":"additional","affiliation":[{"name":"Mitsubishi Electric Research Laboratories, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"McMahon","sequence":"additional","affiliation":[{"name":"University of Miami, Florida"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Mitzenmacher","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,12,31]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 18th National Conference on Artificial Intelligence. 209--216","author":"Anderson D.","year":"2000","unstructured":"Anderson , D. , Anderson , E. , Lesh , N. , Marks , J. , 2000 . Human-guided simple search . In Proceedings of the 18th National Conference on Artificial Intelligence. 209--216 . Anderson, D., Anderson, E., Lesh, N., Marks, J., et al. 2000. Human-guided simple search. In Proceedings of the 18th National Conference on Artificial Intelligence. 209--216."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209064"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90034-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/HICSS.2006.360"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90031-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676307"},{"key":"e_1_2_1_7_1","volume-title":"In: G. Ausiello, M. Lucertini, and P. Serafini, eds, Algorithm Design for Computer Systems Design","author":"Coffman E. G.","year":"1984","unstructured":"Coffman , E. G. , Garey , M. R. , and Johnson , D. S . 1984 . Approximation algorithms for bin-packing: an updated survey. In: G. Ausiello, M. Lucertini, and P. Serafini, eds, Algorithm Design for Computer Systems Design , Springer-Verlag , 49--106. Coffman, E. G., Garey, M. R., and Johnson, D. S. 1984. Approximation algorithms for bin-packing: an updated survey. In: G. Ausiello, M. Lucertini, and P. Serafini, eds, Algorithm Design for Computer Systems Design, Springer-Verlag, 49--106."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018517106992"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(90)90350-K"},{"key":"e_1_2_1_10_1","volume-title":"III: Exact algorithms. Available as a preprint at","author":"Fekete S. P.","year":"1997","unstructured":"Fekete , S. P. and Schepers , J . 1997 . On more-dimensional packing III: Exact algorithms. Available as a preprint at Mathematisches Institut, Universit\u00e4t zu K\u00f6ln , preprint key zpr97--290. Fekete, S. P. and Schepers, J. 1997. On more-dimensional packing III: Exact algorithms. Available as a preprint at Mathematisches Institut, Universit\u00e4t zu K\u00f6ln, preprint key zpr97--290."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 5th Annual European Symposium on Algorithms. 144--156","author":"Fekete S. P.","unstructured":"Fekete , S. P. and Schepers , J . 1997. A New Exact Algorithm for General Orthogonal D-Dimensional Knapsack Problems . In Proceedings of the 5th Annual European Symposium on Algorithms. 144--156 . Fekete, S. P. and Schepers, J. 1997. A New Exact Algorithm for General Orthogonal D-Dimensional Knapsack Problems. In Proceedings of the 5th Annual European Symposium on Algorithms. 144--156."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00357-4"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, Part 2 (of 3). 1583--1590","author":"Hwang S. M.","unstructured":"Hwang , S. M. , Cheng , Y. K. , and Horng , J. T . 1994. On solving rectangle bin packing problems using genetic algorithms . In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, Part 2 (of 3). 1583--1590 . Hwang, S. M., Cheng, Y. K., and Horng, J. T. 1994. On solving rectangle bin packing problems using genetic algorithms. In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, Part 2 (of 3). 1583--1590."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Iori M. Martello S. and Monaci M. 2003. Metaheuristic Algorithms for the Strip Packing Problem in P. M. Pardalos V. Korotkikh Eds. Optimization and Industry: New Frontiers Kluwer Academic Publishers Boston MA 159--179.  Iori M. Martello S. and Monaci M. 2003. Metaheuristic Algorithms for the Strip Packing Problem in P. M. Pardalos V. Korotkikh Eds. Optimization and Industry: New Frontiers Kluwer Academic Publishers Boston MA 159--179.","DOI":"10.1007\/978-1-4613-0233-9_7"},{"key":"e_1_2_1_16_1","volume-title":"Approximate Strip-Packing. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science. 31--36","author":"Kenyon C.","unstructured":"Kenyon , C. and Remilia , E . 1996 . Approximate Strip-Packing. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science. 31--36 . Kenyon, C. and Remilia, E. 1996. Approximate Strip-Packing. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science. 31--36."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 18th National Conference on Artificial Intelligence. 41--47","author":"Klau G.","unstructured":"Klau , G. , Lesh , N. , Marks , J. , and Mitzenmacher , M . 2002a. Human-Guided Tabu search . In Proceedings of the 18th National Conference on Artificial Intelligence. 41--47 . Klau, G., Lesh, N., Marks, J., and Mitzenmacher, M. 2002a. Human-Guided Tabu search. In Proceedings of the 18th National Conference on Artificial Intelligence. 41--47."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1556262.1556314"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS-03)","author":"Korf R. E.","year":"2003","unstructured":"Korf , R. E. 2003 . Optimal rectangle packing: Initial results . In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS-03) , Trento, Italy. Korf, R. E. 2003. Optimal rectangle packing: Initial results. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS-03), Trento, Italy."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Lesh N. Marks J. McMahon A. and Mitzenmacher M. 2003. New Exhaustive Heuristic and Interactive Approaches to 2D Rectangular Strip Packing. MERL Technical Report TR2003-05.  Lesh N. Marks J. McMahon A. and Mitzenmacher M. 2003. New Exhaustive Heuristic and Interactive Approaches to 2D Rectangular Strip Packing. MERL Technical Report TR2003-05.","DOI":"10.1145\/1064546.1083322"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.006"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00123-6"},{"key":"e_1_2_1_23_1","volume-title":"Analyzing and Modeling Rank Data","author":"Marden J. I.","unstructured":"Marden , J. I. 1995. Analyzing and Modeling Rank Data , Chapman & Hall , New York . Marden, J. I. 1995. Analyzing and Modeling Rank Data, Chapman & Hall, New York."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.15.3.310.16082"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics. 989--994","author":"Ratanapan K.","unstructured":"Ratanapan , K. and Dagli , C. H . 1997. An object-based evolutionary algorithm for solving rectangular piece nesting problems . In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics. 989--994 . Ratanapan, K. and Dagli, C. H. 1997. An object-based evolutionary algorithm for solving rectangular piece nesting problems. In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics. 989--994."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the International Conference on Evolutionary Computation. 581--586","author":"Ratanapan K.","unstructured":"Ratanapan , K. and Dagli , C. H . 1998. An object-based evolutionary algorithm: The nesting solution . In Proceedings of the International Conference on Evolutionary Computation. 581--586 . Ratanapan, K. and Dagli, C. H. 1998. An object-based evolutionary algorithm: The nesting solution. In Proceedings of the International Conference on Evolutionary Computation. 581--586."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90121-0"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255801"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1064546.1083322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T12:09:27Z","timestamp":1672229367000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1064546.1083322"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12,31]]},"references-count":27,"alternative-id":["10.1145\/1064546.1083322"],"URL":"https:\/\/doi.org\/10.1145\/1064546.1083322","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12,31]]}}}