Optimization of Nesting Systems in Shipbuilding: A Review

Abstract

This review article provides a comprehensive analysis of nesting optimization algorithms in the shipbuilding industry, emphasizing their role in improving material utilization, minimizing waste, and enhancing production efficiency. The shipbuilding process involves the complex cutting and arrangement of steel plates, making the optimization of these operations vital for cost-effectiveness and sustainability. Nesting algorithms are broadly classified into four categories: exact, heuristic, metaheuristic, and hybrid. Exact algorithms ensure optimal solutions but are computationally demanding. In contrast, heuristic algorithms deliver quicker results using practical rules, although they may not consistently achieve optimal outcomes. Metaheuristic algorithms combine multiple heuristics to effectively explore solution spaces, striking a balance between solution quality and computational efficiency. Hybrid algorithms integrate the strengths of different approaches to further enhance performance. This review systematically assesses these algorithms using criteria such as material dimensions, part geometry, component layout, and computational efficiency. The findings highlight the significant potential of advanced nesting techniques to improve material utilization, reduce production costs, and promote sustainable practices in shipbuilding. By adopting suitable nesting solutions, shipbuilders can achieve greater efficiency, optimized resource management, and superior overall performance. Future research directions should focus on integrating machine learning and real-time adaptability to further enhance nesting algorithms, paving the way for smarter, more sustainable manufacturing practices in the shipbuilding industry.

References

[1] Abdou K, Mohammed O, Eskandar G, Ibrahim A, Matt PA, Huber MF. Smart nesting: estimating geometrical compatibility in the nesting problem using graph neural networks. Journal of Intelligent Manufacturing, 2023, 35(2024): 2811-2827

[2] Alblas G, Pruijn J. Are current shipbuilding cost estimation methods ready for a sustainable future? A literature review of cost estimation methods and challenges. International Shipbuilding Progress, 2024, 71(1): 3-28

[3] Alvarez-Valdes R, Martinez A, Tamarit JM. A branch and bound algorithm for cutting and packing irregularly shaped pieces. International Journal of Production Economics, 2013, 145(2): 463-477

[4] Arnaout JP, ElKhoury C, Karayaz G. Solving the multiple level warehouse layout problem using ant colony optimization. Operational Research, 2020, 20(1): 473-490

[5] Ashari IA, Muslim MA, Alamsyah A. Comparison performance of genetic algorithm and ant colony optimization in course scheduling optimizing. Scientific Journal of Informatics, 2016, 3(2): 149-158

[6] Azevedo BF, Rocha AMAC, Pereira AI. Hybrid approaches to optimization and machine learning methods: a systematic literature review. Machine Learning, 2024, 113(7): 4055-4097

[7] Baso S, Musrina M, Anggriani ADE. Strategy for improving the competitiveness of shipyards in the eastern part of indonesia. Kapal: Jurnal Ilmu Pengetahuan dan Teknologi Kelautan, 2020, 17(2): 74-85

[8] Basuki M, Manfaat D, Nugroho S, Dinariyana AAB. Improvement of the process of new business of ship building industry. Journal of Economics, Business, and Accountancy Ventura, 2012, 15(2): 187-204

[9] Bettemir H, Sonmez R. Hybrid genetic algorithm with simulated annealing for resource-constrained project scheduling. Journal of Management in Engineering, 2015, 31(5): 1-8

[10] Calabrese M, Primo T, Del Prete A, Filitti G. Nesting algorithm for optimization part placement in additive manufacturing. International Journal of Advanced Manufacturing Technology, 2022, 119(7–8): 4613-4634

[11] Canellidis V, Giannatsis J, Dedoussis V. Efficient parts nesting schemes for improving stereolithography utilization. CAD Computer Aided Design, 2013, 45(5): 875-886

[12] Cherri LH, Mundim LR, Andretta M, Toledo FMB, Oliveira JF, Carravilla MA. Robust mixed-integer linear programming models for the irregular strip packing problem. European Journal of Operational Research, 2016, 253(3): 570-583

[13] Cherri LH, Cherri AC, Soler EM. Mixed integer quadratically-constrained programming model to solve the irregular strip packing problem with continuous rotations. Journal of Global Optimization, 2018, 72(1): 89-107

[14] Djilali A, Fouad M, Kouloughli S. Optimizing the placement of irregular shapes 2D Nesting. 4th International Conference on Power Electronics and their Applications, ICPEA, 2019 1-5

[15] Egeblad J, Nielsen BK, Odgaard A. Fast neighborhood search for two- and three-dimensional nesting problems. European Journal of Operational Research, 2007, 183(3): 1249-1266

[16] Elhaddad YR. Combined simulated annealing and genetic algorithm to solve optimization problems. World Academy of Science, Engineering and Technology, 2012, 6(8): 1508-1510

[17] Fang J, Rao Y, Liu P, Zhao X. Sequence transfer-based particle wwarm optimization algorithm for irregular packing problems. IEEE Access, 2021, 9: 131223-131235

[18] Fang J, Rao Y, Zhao X, Du B. A hybrid reinforcement learning algorithm for 2D irregular packing problems. Mathematics, 2023, 11(2): 327

[19] Fang J, Rao Y, Luo Q, Xu J. Solving one-dimensional cutting stock problems with the deep reinforcement learning. Mathematics, 2023, 11(4): 1028

[20] Fekete SP, Morr S, Scheffer C. Split packing: Algorithms for packing circles with optimal worst-case density. Discrete and Computational Geometry, 2019, 61(3): 562-594

[21] Fernandez LC, Bennel JA, Martinez-Sykora A. Voxel-based solution approaches to the 3D irregular packing problem. Operations Research, 2022, 71(4): 1021-1439

[22] Firmansyah MR, Asri S, Fachruddin F, Mustafa W, Clausthaldi FR. Identifying and formulating information system of ship production process for an indonesian small shipyard. International Journal of Metacentre, 2021, 1(1): 12-23

[23] Fujita K, Akagi S, Hirokawa N. Hybrid approach for optimal nesting using a genetic algorithm and a local minimization algorithm. ASME 1993 Design Technical Conferences, 1993, 19: 477-484

[24] Gardeyn J, Wauters T. A goal-driven ruin and recreate heuristic for the 2D variable-sized bin packing problem with guillotine constraints. European Journal of Operational Research, 2022, 301(2): 432-444

[25] Gomes AM, Oliveira JF. Solving irregular strip packing problems by hybridising simulated annealing and linear programming. European Journal of Operational Research, 2006, 171(3): 811-829

[26] Gomez JC, Terashima-Marín H. Evolutionary hyper-heuristics for tackling bi-objective 2D bin packing problems. Genetic Programming and Evolvable Machines, 2018, 19(1–2): 151-181

[27] González-San-Martín J, Cruz-Reyes L, Gómez-Santillán C, Fraire H, Rangel-Valdez N, Dorronsoro B, Quiroz-Castellanos M. Comparative study of heuristics for the one-dimensional bin packing problem. Studies in Computational Intelligence, 2023, 1096: 293-305

[28] Goodman ED, Tetelbaum AY, Kureichik VM. A genetic algorithm approach to compaction, bin packing, and nesting problems, 1994

[29] Grange A, Kacem I, Martin S. Algorithms for the bin packing problem with overlapping items. Computers & Industrial Engineering, 2018, 115: 331-341

[30] Gray A. Body as voice: Restorative dance/movement psychotherapy with survivors of relational trauma. The Routledge International Handbook of Embodied Perspectives in Psychotherapy: Approaches from Dance Movement and Body Psychotherapies, 2019 147-160

[31] Gunbeyaz SA, Kurt RE, Turan O. Investigation of different cutting technologies in a ship recycling yard with simulation approach. Ships and Offshore Structures, 2022, 17(3): 564-576

[32] Guo B, Hu J, Wu F, Peng Q. Automatic layout of 2D freeform shapes based on geometric similarity feature searching and fuzzy matching. Journal of Manufacturing Systems, 2020, 56: 37-49

[33] Hamada K, Ikeda Y, Tokumoto H, Hase S. Development of automatic nesting system for shipbuilding using the branch-and-bound method. Journal of Marine Science and Technology (Japan), 2019, 24(2): 398-409

[34] Han X, Iwama K, Ye D, Zhang G. Strip packing vs. bin packing, 2007 358-367

[35] Hartono N, Ismail AH, Zeybek S, Caterino M, Jiang K, Sahin M, Natalia C. The 1-D bin packing problem optimisation using bees algorithm. Journal Industrial Servicess, 2022, 7(2): 323

[36] Hifi M. Exact algorithms for large-scale unconstrained two and three staged cutting problems. Computational Optimization and Applications, 2001, 18(1): 63-88

[37] Hong PC, Park YS, Hwang DW, Sepehr MJ. A growth theory perspective on the competitive landscape of shipbuilding: a comparative study of Japan, Korea, and China. Maritime Economics & Logistics, 2024, 26: 462-489

[38] Hu S, Liu T, Wang S, Kao Y, Sun X. A hybrid heuristic algorithm for ship block construction space scheduling problem. Discrete Dynamics in Nature and Society, 2015, 7: 1-6

[39] Huang L, Chen X, Huo W, Wang J, Zhang F, Bai B, Shi L. Branch and bound in mixed integer linear programming problems: A survey of techniques and trends. Discrete Optimization (November), 2021 1-29

[40] ILO. Sectoral skills priorities for the shipbuilding industry: Skills demand and supply insights based on the ILO Skills for Trade and Economic Diversification (STED) methodology Skills for prosperity Indonesia, 2023

[41] Ingber L. Simulated annealing: Practice versus theory. Mathematical and Computer Modelling, 1993, 18(11): 29-57

[42] Japan Ship Technology Research Association. Roadmap to zero emission from international shipping. Shipping Zero Emission Project (March), 2020 1-136

[43] Jones DR. A fully general, exact algorithm for nesting irregular shapes. Journal of Global Optimization, 2014, 59(2–3): 367-404

[44] Kamola-Cieslik M. Changes in the global shipbuilding industry on the examples of selected states worldwide in the 21st Century. European Research Studies Journal, 2021, XXIV(2B): 98-112

[45] Kareem SW, Ali KWH, Askar S, Xoshaba FS, Roojwan H. Metaheuristic algorithms in optimization and its application: a review. Journal on Advanced Research in Electrical Engineering, 2022, 6(1): 7-12

[46] Kennedy J, Eberhart R. Particle swarm optimization. Proceedings of ICNN’95-International Conference on Neural Networks, 1995 105-111

[47] Kierkosz I, Łuczak M. A one-pass heuristic for nesting problems. Operations Research and Decisions, 2019, 29(1): 37-60

[48] Ko MC, Hsieh SJ. Design and evaluation of algorithms for stacking irregular 3D objects using an automated material handling system. International Journal of Advanced Manufacturing Technology, 2023, 126(5–6): 1951-1964

[49] Ko S, Shinoda T. The development and challenges of China’s shipbuilding industry. 7th International Conference on Ship and Offshore Technology, ICSOT Indonesia, 2021 25-34

[50] Lallier C, Blin G, Pinaud B, Vézard L. Graph neural network comparison for 2D nesting efficiency estimation. Journal of Intelligent Manufacturing, 2024, 35(2): 859-873

[51] Lee J, Kim BI, Kim SH. A matheuristic algorithm for block assignment problem in long-term production planning in the shipbuilding industry. Computers and Industrial Engineering, 2023, 184(February): 109603

[52] Lee ZJ, Su SF, Chuang CC, Liu KH. Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment. Applied Soft Computing Journal, 2008, 8(1): 55-78

[53] Li YB, Sang HB, Xiong X, Li YR. An improved adaptive genetic algorithm for two-dimensional rectangular packing problem. Applied Sciences (Switzerland), 2021, 11(1): 1-20

[54] Liao X, Guo S, Ou C. An physical force-driven packing optimization design method in strip packing problems. International Forum on Energy, Environment and Sustainable Development (IFEESD), 2016 483-487

[55] Liu C, Si Z, Hua J, Jia N. Optimizing two-dimensional irregular packing: A hybrid approach of genetic algorithm and linear programming. Applied Sciences, 2023, 13(22): 12474

[56] Liu X, Chang D. An improved method for optimizing CNC laser cutting paths for ship hull components with thicknesses up to 24 mm. Journal of Marine Science and Engineering, 2023, 11(3): 652

[57] Lodi A. Algorithms for two-dimensional bin packing and assignment problems, 1999

[58] Lodi A, Martello S, Monaci M. Two-dimensional packing problems: A survey. European Journal of Operational Research, 2002, 141(2): 241-252

[59] Lourenço HR, Martin O, Stützle T. A Beginner’s introduction to iterated local search. Proceeding of the 4th Metaheuristics International Conference, 2001 1-6

[60] Martello S, Monaci M, Vigo D. An exact approach to the strip-packing problem. INFORMS Journal on Computing, 2003, 15(3): 310-319

[61] Martinez-Martinez G, Sanchez-Romero JL, Jimeno-Morenilla A, Mora-Mora H. An improved nesting algorithm for irregular patterns, 2021

[62] Martinez-Sykora A, Alvarez-Valdes R, Bennell JA, Ruiz R, Tamarit JM. Matheuristics for the irregular bin packing problem with free rotations. European Journal of Operational Research, 2017, 258(2): 440-455

[63] Mundim LR, Andretta M, Carravilla MA, Oliveira JF. A general heuristic for two-dimensional nesting problems with limited-size containers. International Journal of Production Research, 2018, 56(1–2): 709-732

[64] Muriyatmoko D, Djunaidy A, Muklason A. Heuristics and metaheuristics for solving capacitated vehicle routing problem: An algorithm comparison. Procedia Computer Science, 2024, 234: 494-501

[65] Mustafa W, Asri S, L FF, Rizal M, Clausthaldi FR, Rijal A, Jafar J, Putra M. Characteristics of SPOB ship hull block design based on the plate supply requirements. International Journal of Metacentre, 2022, 2(2): 1-8

[66] Na GY, Yang J. Two-dimensional polygon classification and pairwise clustering for pairing in ship parts nesting. Journal of Intelligent Manufacturing, 2024, 35(7): 3169-3184

[67] Nor DSARM, Nazery K. An overview of the shipbuilding industry in malaysia. 5th Asia Maritime Conference, 2008 1-12

[68] Okubo Y, Mitsuyuki T. Ship production planning using shipbuilding system modeling and discrete time process simulation. Journal of Marine Science and Engineering, 2022, 10(2): 176

[69] Okumoto Y, Takeda Y, Mano M, Okada T. Design of ship hull structures: A practical guide for engineers, 2009, Berlin Heidelberg, Springer 1-578

[70] Oliveira A, Gordo JM. Implementation of new production processes in panel’s line. Maritime Transportation and Harvesting of Sea Resources, 2018, 2(October2017): 763-773

[71] Page MJ, McKenzie J, Bossuyt PM, Boutron I, Hoffmann TC, Mulrow CD, Shamseer L, Tetzlaff JM, Akl AEA, Brennan SE, Chou R, Glanville J, Grimshaw JM, Hróbjartsson A, Lalu MM, Li T, Loder EW, Mayo-Wilson E, McDonald S, McGuinness LA, Stewart LA, Thomas J, Tricco AC, Welch VA, Whiting P, Moher D. The PRISMA 2020 statement: an updated guideline for reporting systematic reviews, 2020 1

[72] Page MJ, McKenzie J, Bossuyt PM, Boutron I, Hoffmann TC, Mulrow CD, Shamseer L, Tetzlaff JM, Akl AEA, Brennan SE, Chou R, Glanville J, Grimshaw JM, Hróbjartsson A, Lalu MM, Li T, Loder EW, Mayo-Wilson E, McDonald S, McGuinness LA, Stewart LA, Thomas J, Tricco AC, Welch VA, Whiting P, Moher D (2021)’ PRISMA 2020 Checklist. The BMJ: 2020–2021. https://doi.org/10.1136/bmj.n71

[73] Perez-Martinez J, Fernandez PR. Material and production optimization of the ship design process by introducing CADs from early design stages. Journal of Marine Science and Engineering, 2023, 11(1): 233

[74] Pospelov KN, Vatamaniuk IV, Lundaeva KA, Gintciak AM. Heuristic approach to planning complex multi-stage production systems. International Journal of Technology, 2023, 14(8): 1790-1799

[75] Rakotonirainy RG, Vuuren JHV. Improved metaheuristics for the two-dimensional strip packing problem. Applied Soft Computing Journal, 2020, 92: 106268

[76] Rigo P, Caprace JD. Optimization of ship structures. Marine Technology and Engineering, 2011, 2(October): 925-944

[77] Ru N, Jianhua Y. A GA and particle swarm optimization based hybrid algorithm. 2008 IEEE Congress on Evolutionary Computation, CEC, 2008, 2008: 1047-1050

[78] Saiyara N. Material of construction, steel material preparation & plate cutting for ship hull, 2024

[79] Sari WR, Gunawan Muzhoffar DAF. Systematic review of optimization of nesting system in shipbuilding. 5th International Conference on Information Technology and Advanced Mechanical and Electrical Engineering (ICITAMEE), 2024

[80] Selow R, Neves F, Lopes HS. Genetic algorithms for the nesting problem in the packing industry. Proceedings of the International MultiConference of Engineers and Computer Scientists (IMECS 2007), 2007 1-6

[81] Smith K, Diaz R, Shen Y. Development of a framework to support informed shipbuilding based on supply chain disruptions. Procedia Computer Science, 2022, 200: 1093-1102

[82] Son S, Kim B, Ryu C, Hwang I, Jung CH, Shin JG. Production automation system for three-dimensional template pieces used to evaluate shell plate completeness. International Journal of Naval Architecture and Ocean Engineering, 2020, 12: 116-128

[83] Sutrisno S, Suef M, Ma’ruf B. A conceptual model of agile manufacturing in the shipbuilding industry for improving shipyard performance. International Journal of Agile Systems and Management, 2024, 17(2): 246-268

[84] Suzuki S, Muraoka R, Obinata T, Endo S, Horita T, Omata K. Steel products for shipbuilding. JFE Technical Report, 2004, 2(2): 41-48

[85] Timmerman M. Optimization methods for nesting problems, 2013 49

[86] Ting TO, Yang XS, Cheng S, Huang K. Hybrid metaheuristic algorithms: Past, present, and future. Studies in Computational Intelligence, 2015, 585: 71-83

[87] Uemori R, Fujioka M, Inoue T, Minagawa M, Ichikawa K, Shirahata H, Nose T. Steels for marine transportation and construction, 2012 37-47

[88] Umetani S, Murakami S. Coordinate descent heuristics for the irregular strip packing problem of rasterized shapes. European Journal of Operational Research, 2022, 303(3): 1009-1026

[89] Vielma JP, Ahmed S, Nemhauser GL. A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs. INFORMS Journal on Computing, 2008, 20(3): 438-450

[90] Wang A, Hanselman CL, Gounaris CE. A customized branch-and-bound approach for irregular shape nesting. Journal of Global Optimization, 2018, 71(4): 935-955

[91] Wang Y, Zhang P, Gu Y, Zhang X, Jin C, Chen M. Research of ship nesting based on maximum residual rectangle strategy integrated improved genetic algorithm. Advances in Transdisciplinary Engineering, 2024, 46: 499-506

[92] Wang Y, Han Y, Wang Y, Li J, Gao K, Liu Y. An effective two-stage iterated greedy algorithm for distributed flowshop group scheduling problem with setup time. Expert Systems with Applications, 2023, 233: 120909

[93] Williams RI, Clark LA, Clark WR, Raffo DM. Re-examining systematic literature review in management research: Additional benefits and execution protocols. European Management Journal, 2021, 39(4): 521-533

[94] Wu TH, Chen JF, Low C, Tang PT. Nesting of two-dimensional parts in multiple plates using hybrid algorithm. International Journal of Production Research, 2003, 41(16): 3883-3900

[95] Xie SQ, Wang GG, Liu Y. Nesting of two-dimensional irregular parts: An integrated approach. International Journal of Computer Integrated Manufacturing, 2007, 20(8): 741-756

[96] Xu J, Yang W. Multi-objective steel plate cutting optimization problem based on real number coding genetic algorithm. Scientific Reports, 2022, 12(1): 1-20

[97] Xu JJ, Wu XS, Liu HM, Zhang M. An optimization algorithm based on no-fit polygon method and hybrid heuristic strategy for irregular nesting problem. Chinese Control Conference, CCC, 2017 2858-2863

[98] Xu YX. An efficient heuristic approach for irregular cutting stock problem in ship building industry. Mathematical Problems in Engineering, 2016, 8703782: 12

[99] Yu-ichi K. Status & prospects of shipbuilding steel and its weldability. Transactions of JWRI, 2007, 36(1): 1-6

[100] Yue M. A simple proof of the inequality FFD (L) ⩽ 11/9 OPT (L)+1, ∀L for the FFD bin-packing algorithm. Acta Mathematicae Applicatae Sinica, 1991, 7(4): 321-331

[101] Zhang C, Han F, Zhang W. A cutting sequence optimization method based on tabu search algorithm for complex parts machining. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2019, 233(3): 745-755

[102] Zhang H, Liu Q, Wei L, Zeng J, Leng J, Yan D. An iteratively doubling local search for the two-dimensional irregular bin packing problem with limited rotations. Computers and Operations Research, 2022, 137: 105550

[103] Zhang H, Yao S, Liu Q, Wei L, Lin L, Leng J. An exact approach for the constrained two- dimensional guillotine cutting problem with defects. International Journal of Production Research, 2023, 61(9): 2986-3003

RIGHTS & PERMISSIONS

Harbin Engineering University and Springer-Verlag GmbH Germany, part of Springer Nature