{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T11:48:19Z","timestamp":1775044099128,"version":"3.50.1"},"reference-count":54,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computers"],"abstract":"<jats:p>This paper proposes adaptive sequence-based heuristics for solving rectangular two-dimensional guillotine Cutting and Packing Problems (CPPs). These problems are essential in various industrial sectors, aiming to maximise resource utilisation by selecting profitable item subsets or minimise waste by using the fewest possible identical large objects. The core methodology is grounded in the principle that if a specific item sequence generates a high-quality solution, incremental adjustments to that sequence can yield even better outcomes. By iteratively refining item ordering through the BubbleSearch method, the heuristics balance search intensification with the diversification of the solution space. Extensive computational experiments were conducted on benchmark datasets, including SET1, ATP, and CLASS, across multiple problem variants such as the Single Stock-Size Cutting Stock Problem (SSSCSP) and the Single Large Object Placement Problem (SLOPP). The results confirm that these heuristics and their extension with path relinking consistently deliver optimal or near-optimal solutions. These heuristics achieve high performance in computational times that are significantly shorter than existing state-of-the-art methods, demonstrating their robustness, flexibility, and suitability for software transferability and real-world industrial adoption.<\/jats:p>","DOI":"10.3390\/computers15040216","type":"journal-article","created":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T10:09:21Z","timestamp":1775038161000},"page":"216","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Adaptive Sequence-Based Heuristic for Two-Dimensional Guillotine Cutting and Packing Problems"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3807-7292","authenticated-orcid":false,"given":"\u00d3scar","family":"Oliveira","sequence":"first","affiliation":[{"name":"Centro de Investiga\u00e7\u00e3o e Inova\u00e7\u00e3o em Ci\u00eancias Empresariais e Sociais, Escola Superior de Tecnologia e Gest\u00e3o, Polit\u00e9cnico do Porto, Rua do Curral, Casa do Curral, Margaride, 4610-156 Felgueiras, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8720-8597","authenticated-orcid":false,"given":"Dorabela","family":"Gamboa","sequence":"additional","affiliation":[{"name":"Centro de Investiga\u00e7\u00e3o e Inova\u00e7\u00e3o em Ci\u00eancias Empresariais e Sociais, Escola Superior de Tecnologia e Gest\u00e3o, Polit\u00e9cnico do Porto, Rua do Curral, Casa do Curral, Margaride, 4610-156 Felgueiras, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2026,4,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1109","DOI":"10.1016\/j.ejor.2005.12.047","article-title":"An improved typology of cutting and packing problems","volume":"183","author":"Schumann","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1057\/palgrave.jors.2601319","article-title":"A guide to vehicle routing heuristics","volume":"53","author":"Cordeau","year":"2002","journal-title":"J. Oper. Res. Soc."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/978-3-030-85476-8_8","article-title":"Adaptive Sequence-Based Heuristic for Two-Dimensional Non-guillotine Packing Problems","volume":"Volume 374","author":"Relvas","year":"2021","journal-title":"Proceedings of the Operational Research"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/978-3-030-38629-0_6","article-title":"Adaptive Sequence-Based Heuristic for the Three-Dimensional Bin Packing Problem","volume":"Volume 11968","author":"Matsatsinis","year":"2020","journal-title":"Proceedings of the Learning and Intelligent Optimization"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/opre.9.6.849","article-title":"A linear programming approach to the cutting-stock problem","volume":"9","author":"Gilmore","year":"1961","journal-title":"Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1287\/opre.13.1.94","article-title":"Multistage cutting stock problems of two and more dimensions","volume":"13","author":"Gilmore","year":"1965","journal-title":"Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1287\/opre.33.1.49","article-title":"An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure","volume":"36","author":"Beasley","year":"1985","journal-title":"Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1057\/jors.1985.51","article-title":"Algorithms for Unconstrained Two-Dimensional Guillotine Cutting","volume":"36","author":"Beasley","year":"1985","journal-title":"J. Oper. Res. Soc."},{"key":"ref_9","first-page":"145","article-title":"Performance of Two Heuristics for Solving Large Scale Two-Dimensional Guillotine Cutting Problems","volume":"33","author":"Morabito","year":"1995","journal-title":"INFOR Inf. Syst. Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1023\/A:1008743711658","article-title":"Exact algorithms for large-scale unconstrained two and three staged cutting problems","volume":"18","author":"Hifi","year":"2001","journal-title":"Comput. Optim. Appl."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1023\/A:1011628809603","article-title":"Approximate and Exact Algorithms for Constrained (Un) Weighted Two-dimensional Two-staged Cutting Stock Problems","volume":"5","author":"Hifi","year":"2001","journal-title":"J. Comb. Optim."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1287\/opre.1040.0154","article-title":"An exact algorithm for constrained two-dimensional two-staged cutting problems","volume":"53","author":"Hifi","year":"2005","journal-title":"Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s10107-002-0319-9","article-title":"Integer linear programming models for 2-staged two-dimensional Knapsack problems","volume":"94","author":"Lodi","year":"2003","journal-title":"Math. Program."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1023\/B:JOCO.0000038915.62826.79","article-title":"Models and bounds for two-dimensional level packing problems","volume":"8","author":"Lodi","year":"2004","journal-title":"J. Comb. Optim."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1016\/j.cor.2009.08.005","article-title":"Arc-flow model for the two-dimensional guillotine cutting stock problem","volume":"37","author":"Macedo","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1016\/j.ejor.2010.01.039","article-title":"An integer programming model for two- and three-stage two-dimensional cutting stock problems","volume":"205","author":"Silva","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.ejor.2004.08.036","article-title":"A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting","volume":"171","author":"Belov","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1304","DOI":"10.1016\/j.ejor.2005.11.064","article-title":"Models and algorithms for three-stage two-dimensional bin packing","volume":"183","author":"Puchinger","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.cor.2010.12.018","article-title":"Exact algorithms for the two-dimensional guillotine knapsack","volume":"39","author":"Dolatabadi","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1287\/ijoc.2016.0708","article-title":"An Exact Algorithm for the Two-Dimensional Stage-Unrestricted Guillotine Cutting\/Packing Decision Problem","volume":"28","author":"Fleszar","year":"2016","journal-title":"INFORMS J. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1287\/ijoc.2016.0710","article-title":"Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming","volume":"28","author":"Furini","year":"2016","journal-title":"INFORMS J. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1057\/jors.1987.70","article-title":"Two-Dimensional Finite Bin-Packing Algorithms","volume":"38","author":"Berkey","year":"1987","journal-title":"J. Oper. Res. Soc."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1016\/0377-2217(93)E0221-I","article-title":"An approximation algorithm for solving unconstrained two-dimensional knapsack problems","volume":"84","author":"Fayard","year":"1995","journal-title":"Eur. J. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1270","DOI":"10.1057\/palgrave.jors.2600638","article-title":"An efficient approach for large-scale two-dimensional guillotine cutting stock problems","volume":"49","author":"Fayard","year":"1998","journal-title":"J. Oper. Res. Soc."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0377-2217(92)90212-R","article-title":"An and-or-graph approach for two-dimensional cutting problems","volume":"58","author":"Morabito","year":"1992","journal-title":"Eur. J. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"548","DOI":"10.1016\/0377-2217(95)00128-X","article-title":"Staged and constrained two-dimensional guillotine cutting problems: An AND\/OR-graph approach","volume":"94","author":"Morabito","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/S0360-8352(96)00205-7","article-title":"Developing a simulated annealing algorithm for the cutting stock problem","volume":"32","author":"Lai","year":"1997","journal-title":"Comput. Ind. Eng."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1212","DOI":"10.1016\/j.ejor.2005.11.062","article-title":"A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem","volume":"183","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/s10878-009-9282-1","article-title":"A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem","volume":"22","author":"Resende","year":"2011","journal-title":"J. Comb. Optim."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1016\/S0305-0548(00)00095-2","article-title":"A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems","volume":"29","author":"Tamarit","year":"2002","journal-title":"Comput. Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1057\/palgrave.jors.2601829","article-title":"A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems","volume":"56","author":"Tamarit","year":"2005","journal-title":"J. Oper. Res. Soc."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1287\/ijoc.1050.0169","article-title":"GRASP and path relinking for the two-dimensional two-stage cutting-stock problem","volume":"19","author":"Tamarit","year":"2007","journal-title":"INFORMS J. Comput."},{"key":"ref_33","first-page":"337","article-title":"A skyline heuristic for the 2D rectangular packing and strip packing problems","volume":"215","author":"Wei","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1287\/ijoc.15.3.267.16080","article-title":"Guided Local Search for the Three-Dimensional Bin-Packing Problem","volume":"15","author":"Faroe","year":"2003","journal-title":"INFORMS J. Comput."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1080\/03052150902835960","article-title":"Sequence based heuristics for two-dimensional bin packing problems","volume":"41","author":"Alvelos","year":"2009","journal-title":"Eng. Optim."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1142\/S0217595911003168","article-title":"Heuristics with stochastic neighborhood structures for two-dimensional bin packing and cutting stock problems","volume":"28","author":"Chan","year":"2011","journal-title":"Asia-Pac. J. Oper. Res."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1287\/ijoc.1070.0233","article-title":"Algorithms for the constrained two-staged two-dimensional cutting problem","volume":"20","author":"Hifi","year":"2008","journal-title":"INFORMS J. Comput."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1016\/j.procs.2013.05.255","article-title":"Solving the 2D bin packing problem by means of a hybrid evolutionary algorithm","volume":"18","author":"Blum","year":"2013","journal-title":"Procedia Comput. Sci."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1007\/s10100-013-0300-0","article-title":"A hybrid evolutionary algorithm for the two-dimensional packing problem","volume":"22","author":"Kierkosz","year":"2014","journal-title":"Cent. Eur. J. Oper. Res."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1287\/ijoc.1040.0089","article-title":"A Set-Covering-Based Heuristic Approach for Bin-Packing Problems","volume":"18","author":"Monaci","year":"2006","journal-title":"INFORMS J. Comput."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1287\/ijoc.11.4.345","article-title":"Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems","volume":"11","author":"Lodi","year":"1999","journal-title":"INFORMS J. Comput."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"3238","DOI":"10.1111\/itor.13236","article-title":"An introduction to the two-dimensional rectangular cutting and packing problem","volume":"30","author":"Oliveira","year":"2022","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1064546.1083322","article-title":"New heuristic and interactive approaches to 2D rectangular strip packing","volume":"10","author":"Lesh","year":"2005","journal-title":"J. Exp. Algorithmics"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/j.ipl.2005.08.013","article-title":"BubbleSearch: A simple heuristic for improving priority-based greedy algorithms","volume":"97","author":"Lesh","year":"2006","journal-title":"Inf. Process. Lett."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1287\/mnsc.44.3.388","article-title":"Exact Solution of the Two-Dimensional Finite Bin Packing Problem","volume":"44","author":"Martello","year":"1998","journal-title":"Manag. Sci."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1287\/ijoc.12.1.75.11898","article-title":"A Minimal Algorithm for the Bounded Knapsack Problem","volume":"12","author":"Pisinger","year":"2000","journal-title":"INFORMS J. Comput."},{"key":"ref_47","first-page":"653","article-title":"Fundamentals of scatter search and path relinking","volume":"39","author":"Glover","year":"2000","journal-title":"Control Cybern."},{"key":"ref_48","unstructured":"Weghorn, H. (2019). Resources for Two-Dimensional (and Three-Dimensional) Cutting and Packing Solution Methods Research. Proceedings of the 16th International Conference on Applied Computing 2019, IADIS Press. Number 9."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF02430364","article-title":"Testing heuristics: We have it all wrong","volume":"1","author":"Hooker","year":"1995","journal-title":"J. Heuristics"},{"key":"ref_50","unstructured":"Cs\u00e9bfalvi, A., and Cs\u00e9bfalvi, G. (2012). Fair comparison of population-based heuristic approaches the evils of competitive testing. Proceedings of the IJCCI 2012\u2014Proceedings of the 4th International Joint Conference on Computational Intelligence, SciTePress."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"115501","DOI":"10.1016\/j.eswa.2021.115501","article-title":"A hybrid matheuristic for the Two-Stage Capacitated Facility Location problem","volume":"185","author":"Souto","year":"2021","journal-title":"Expert Syst. Appl."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1016\/j.ejor.2013.05.042","article-title":"Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns","volume":"231","author":"Cui","year":"2013","journal-title":"Eur. J. Oper. Res."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.ejor.2007.08.007","article-title":"Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation","volume":"191","author":"Cintra","year":"2008","journal-title":"Eur. J. Oper. Res."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0377-2217(90)90359-J","article-title":"Selection of stockplate characteristics and cutting style for two dimensional cutting stock situations","volume":"44","author":"Farley","year":"1990","journal-title":"Eur. J. Oper. Res."}],"container-title":["Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-431X\/15\/4\/216\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T10:21:57Z","timestamp":1775038917000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-431X\/15\/4\/216"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,1]]},"references-count":54,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2026,4]]}},"alternative-id":["computers15040216"],"URL":"https:\/\/doi.org\/10.3390\/computers15040216","relation":{},"ISSN":["2073-431X"],"issn-type":[{"value":"2073-431X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,1]]}}}