{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T19:20:06Z","timestamp":1780773606946,"version":"3.54.1"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2007,3,1]],"date-time":"2007-03-01T00:00:00Z","timestamp":1172707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2007,3]]},"abstract":"<jats:p>We consider the problem of orthogonally packing a given set of rectangular-shaped boxes into the minimum number of three-dimensional rectangular bins. The problem is NP-hard in the strong sense and extremely difficult to solve in practice. We characterize relevant subclasses of packing and present an algorithm which is able to solve moderately large instances to optimality. Extensive computational experiments compare the algorithm for the three-dimensional bin packing when solving general orthogonal packings and when restricted to robot packings.<\/jats:p>","DOI":"10.1145\/1206040.1206047","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"7","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":77,"title":["Algorithm 864"],"prefix":"10.1145","volume":"33","author":[{"given":"Silvano","family":"Martello","sequence":"first","affiliation":[{"name":"University of Bologna, Bologna, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Pisinger","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniele","family":"Vigo","sequence":"additional","affiliation":[{"name":"University of Bologna, Bologna, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Edgar Den","family":"Boef","sequence":"additional","affiliation":[{"name":"Philips Research Laboratories, Eindhoven, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Korst","sequence":"additional","affiliation":[{"name":"Philips Research Laboratories, Eindhoven, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,3]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Bart\u00e1k R. 1998. Online guide to constraint programming. Available online at http:\/\/kti.mff.cuni.cz\/~bartak\/constraints\/.  Bart\u00e1k R. 1998. Online guide to constraint programming. Available online at http:\/\/kti.mff.cuni.cz\/~bartak\/constraints\/."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(98)00364-6"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1050.0210"},{"key":"e_1_2_2_4_1","unstructured":"Dyckhoff H. Scheithauer G. and Terno J. 1997. Cutting and Packing. In Annotated Bibliographies in Combinatorial Optimization M. Dell'Amico F. Maffioli and S. Martello Eds. John Wiley &amp; Sons Chichester England 393--413.  Dyckhoff H. Scheithauer G. and Terno J. 1997. Cutting and Packing. In Annotated Bibliographies in Combinatorial Optimization M. Dell'Amico F. Maffioli and S. Martello Eds. John Wiley &amp; Sons Chichester England 393--413."},{"key":"e_1_2_2_5_1","volume-title":"Performance measurement and analysis of certain search algorithms. Tech. rep. CMU-CS-79-124","author":"Gaschnig J.","unstructured":"Gaschnig , J. 1979. Performance measurement and analysis of certain search algorithms. Tech. rep. CMU-CS-79-124 . Carnegie-Mellon University , Pittsburgh, PA . Gaschnig, J. 1979. Performance measurement and analysis of certain search algorithms. Tech. rep. CMU-CS-79-124. Carnegie-Mellon University, Pittsburgh, PA."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(80)90051-X"},{"key":"e_1_2_2_7_1","first-page":"3","article-title":"Two-dimensional packing problems: A survey","volume":"141","author":"Lodi A.","year":"2002","unstructured":"Lodi , A. , Martello , S. , and Monaci , M. 2002 a. Two-dimensional packing problems: A survey . European J. Operat. Res. 141 , 3 -- 13 . Lodi, A., Martello, S., and Monaci, M. 2002a. Two-dimensional packing problems: A survey. European J. Operat. Res. 141, 3--13.","journal-title":"European J. Operat. Res."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00347-X"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.48.2.256.12386"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.44.3.388"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, PPCP'94","author":"Sabin D.","year":"1994","unstructured":"Sabin , D. and Freuder , E . 1994. Contradicting conventional wisdom in constraint satisfaction . In Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, PPCP'94 , Rosario, Orcas Island, WA, USA , May 1994 , A. Borning, Ed. Lecture Notes in Computer Science, vol. 874. Springer-Verlag, Berlin and Heidelberg, Germany, 10--20. Sabin, D. and Freuder, E. 1994. Contradicting conventional wisdom in constraint satisfaction. In Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, PPCP'94, Rosario, Orcas Island, WA, USA, May 1994, A. Borning, Ed. Lecture Notes in Computer Science, vol. 874. Springer-Verlag, Berlin and Heidelberg, Germany, 10--20."},{"key":"e_1_2_2_12_1","first-page":"3","article-title":"Equivalence and dominance for problems of optimal packing of rectangles","volume":"83","author":"Scheithauer G.","year":"1997","unstructured":"Scheithauer , G. 1997 . Equivalence and dominance for problems of optimal packing of rectangles . Ricerca Operat. 83 , 3 -- 34 . Scheithauer, G. 1997. Equivalence and dominance for problems of optimal packing of rectangles. Ricerca Operat. 83, 3--34.","journal-title":"Ricerca Operat."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1206040.1206047","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1206040.1206047","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:31Z","timestamp":1750278151000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1206040.1206047"}},"subtitle":["General and robot-packable variants of the three-dimensional bin packing problem"],"short-title":[],"issued":{"date-parts":[[2007,3]]},"references-count":12,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,3]]}},"alternative-id":["10.1145\/1206040.1206047"],"URL":"https:\/\/doi.org\/10.1145\/1206040.1206047","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,3]]},"assertion":[{"value":"2007-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}