{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T14:38:05Z","timestamp":1784212685695,"version":"3.55.0"},"reference-count":45,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12072106"],"award-info":[{"award-number":["12072106"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"The Joint fund of Henan Science and Technology Research and Development Plan","award":["242103810064"],"award-info":[{"award-number":["242103810064"]}]},{"name":"The Science and Technology Project of Henan Province in China","award":["222103810085"],"award-info":[{"award-number":["222103810085"]}]},{"name":"The Science and Technology Project of Henan Province in China","award":["232103810085"],"award-info":[{"award-number":["232103810085"]}]},{"name":"The Science and Technology Project of Henan Province in China","award":["242102220029"],"award-info":[{"award-number":["242102220029"]}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Science Progress"],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:p>A backtracking heuristic algorithm (BHA) was proposed for a two-dimensional rectangular strip packing problem with rotations and without guillotine cutting, which has many applications. An improved fitness strategy was used to select the fittest rectangle to be packed on a strip with a certain height. Next, a backtracking constructive heuristic was repeatedly used at a higher height until all the rectangles were packed. A multi-start improvement procedure then found the best solution by taking a different rectangle as the first rectangle, whereas the sequence of the other rectangles remained unchanged. Finally, in order to further expand the scope of the solution, a simple randomized local search procedure based on random sequences of rectangles with the first rectangle unchanged was applied to search for the optimal solution. BHA has only two parameters; it is simple and effective. Computational results on benchmark problems (zero-waste instances and non-zero-waste instances) with different scales (from 10 to 75,032 rectangles) indicate the following: (1) though it is non-deterministic, the difference between the results after each running is tiny and (2) the proposed algorithm outperforms most of the other algorithms under comparison on the whole, especially for large-scale instances with more than 1000 rectangles, which is further verified by statistical analysis and greatly meaningful in mass industrial production like metal cutting.<\/jats:p>","DOI":"10.1177\/00368504241301530","type":"journal-article","created":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T03:26:42Z","timestamp":1738294002000},"update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":3,"title":["A backtracking heuristic algorithm for two-dimensional strip packing with rotation"],"prefix":"10.1177","volume":"108","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2242-2186","authenticated-orcid":false,"given":"Li","family":"Li","sequence":"first","affiliation":[{"name":"Henan University of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baoguo","family":"Liu","sequence":"additional","affiliation":[{"name":"Henan University of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhaoyun","family":"Wu","sequence":"additional","affiliation":[{"name":"Henan University of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2025,1,31]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.11.4.345"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00123-6"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.12.006"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1080\/00207540801935624"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.33.1.49"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.12.047"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105521"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.06.050"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1111\/itor.13236"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1590\/0101-7438.2016.036.02.0197"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.15.3.310.16082"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2008.08.020"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00357-4"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2010.10.022"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2011.04.105"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/0209064"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676307"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-009-0642-0"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2013.01.005"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1040.0109"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1111\/itor.12138"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2012.05.001"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.01.009"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.12.005"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.07.004"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2008.03.004"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2014.12.021"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.08.005"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2013.04.005"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.09.042"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)00166-9"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(97)00437-2"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.04.030"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.11.016"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1080.0306"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018517106992"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00218-7"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2011.06.002"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2011.09.005"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2009.05.008"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2016.11.024"},{"key":"e_1_3_4_43_2","first-page":"417","volume-title":"Proceedings of the 4th metaheuristics international conference","author":"Valenzuela CL","year":"2001","unstructured":"Valenzuela CL, Wang PY. Heuristics for large strip packing problems with guillotine patterns: an empirical study. Proceedings of the 4th metaheuristics international conference. University of Porto, Porto, Portugal, 2001, pp. 417\u2013421."},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(00)00263-0"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-021-01808-y"},{"key":"e_1_3_4_46_2","volume-title":"Second ESICUP Meeting","author":"Pinto E","year":"2005","unstructured":"Pinto E, Oliveira JF. Algorithm based on graphs for the non-guillotinable two-dimensional packing problem. Second ESICUP Meeting, Southampton, 2005."}],"container-title":["Science Progress"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/00368504241301530","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/00368504241301530","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/00368504241301530","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T11:14:10Z","timestamp":1777634050000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/00368504241301530"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["10.1177\/00368504241301530"],"URL":"https:\/\/doi.org\/10.1177\/00368504241301530","relation":{},"ISSN":["0036-8504","2047-7163"],"issn-type":[{"value":"0036-8504","type":"print"},{"value":"2047-7163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1]]},"article-number":"00368504241301530"}}