Article
| Title: | Packing problems with applications in additive manufacturing (English) |
| Author: | Fischer, Andreas |
| Author: | Romanova, Tetyana |
| Author: | Pankratov, Oleksandr |
| Author: | Berger, Christian |
| Author: | Scheithauer, Uwe |
| Language: | English |
| Journal: | Applications of Mathematics |
| ISSN: | 0862-7940 (print) |
| ISSN: | 1572-9109 (online) |
| Volume: | 71 |
| Issue: | 4 |
| Year: | 2026 |
| Pages: | 477-510 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| Summary: | Additive manufacturing is a very complex process. Hence, optimization models and methods play a central role for improving related technologies to save resources like material, time, and energy, and to protect the environment. We first provide existing principles for modeling corresponding tasks as problems of packing optimization, particularly the phi-function technique as a basic analytical tool. Due to the large number of items to pack, the mutual influence of items, and the resulting nonconvexity of the packing optimization problem, a practical solution may become extremely difficult. Therefore, in a generalized way, we present model-based algorithmic ideas to tackle such optimization problems. This includes a decomposition principle and heuristics for obtaining good feasible solutions. We discuss three main cases of packing optimization problems with significant relevance to additive manufacturing, where the general methodology is applied. In the first case we are concerned with the generation of void structures in components that should be printed. Those structures can save material, time, and energy. The second case deals with optimal placements of components in the build space of a 3D printer. In this way, production time can be saved. Finally, we study the problem of simulating the filling of a given 3D volume with particles of possibly different shapes. This may be employed for decreasing the porosity in printed parts, as well as for saving material. (English) |
| Keyword: | packing optimization |
| Keyword: | additive manufacturing |
| Keyword: | mathematical modeling |
| Keyword: | approximate solution method |
| MSC: | 49M27 |
| MSC: | 90C06 |
| MSC: | 90C59 |
| MSC: | 90C90 |
| DOI: | 10.21136/AM.2026.0012-26 |
| . | |
| Date available: | 2026-09-15T09:42:45Z |
| Last updated: | 2026-09-21 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/153746 |
| . | |
| Reference: | [1] Adamaszek, A., Kociumaka, T., Pilipczuk, M., Pilipczuk, M.: Hardness of approximation for strip packing.ACM Trans. Comput. Theory 9 (2017), Article ID 14, 7 pages. Zbl 1427.68100, MR 3716949, 10.1145/3092026 |
| Reference: | [2] Akçay, F. B., Delorme, M.: Solving the parallel processor scheduling and bin packing problems with contiguity constraints: Mathematical models and computational studies.Eur. J. Oper. Res. 323 (2025), 701-723. Zbl 1573.90470, MR 4877319, 10.1016/j.ejor.2024.09.013 |
| Reference: | [3] Albers, S., Gálvez, W., Ã zdemir, Ã . B.: On the 2D demand bin packing problem: Hardness and approximation algorithms.Procedia Comput. Sci. 273 (2025), 301-308. 10.1016/j.procs.2025.10.312 |
| Reference: | [4] Allen, T.: Particle Size Measurement. Volume 1. Powder Sampling and Particle Size Measurement.Chapman & Hall, London (1997). |
| Reference: | [5] Alvarez-Valdes, R., Martinez, A., Tamarit, J. M.: A branch & bound algorithm for cutting and packing irregularly shaped pieces.Int. J. Prod. Econ. 145 (2013), 463-477. 10.1016/j.ijpe.2013.04.007 |
| Reference: | [6] Araújo, L. J. P., Ã zcan, E., Atkin, J. A. D., Baumers, M.: Analysis of irregular three-dimensional packing problems in additive manufacturing: A new taxonomy and dataset.Int. J. Prod. Res. 57 (2019), 5920-5934. 10.1080/00207543.2018.1534016 |
| Reference: | [7] Bendsøe, M. P., Kikuchi, N.: Generating optimal topologies in structural design using a homogenization method.Comput. Methods Appl. Mech. Eng. 71 (1988), 197-224. Zbl 0671.73065, MR 0969217, 10.1016/0045-7825(88)90086-2 |
| Reference: | [8] Bennell, J., Scheithauer, G., Stoyan, Y., Romanova, T.: Tools of mathematical modeling of arbitrary object packing problems.Ann. Oper. Res. 179 (2010), 343-368. Zbl 1201.90167, MR 2684242, 10.1007/s10479-008-0456-5 |
| Reference: | [9] Birgin, E. G., Lobato, R. D., Martínez, J. M.: Packing ellipsoids by nonlinear optimization.J. Glob. Optim. 65 (2016), 709-743. Zbl 1377.90088, MR 3522065, 10.1007/s10898-015-0395-z |
| Reference: | [10] Chen, J., Hou, W., Wang, X., Chu, S., Yang, Z.: Microstructure, porosity and mechanical properties of selective laser melted AlSi10Mg.Chin. J. Aeronaut. 33 (2020), 2043-2054. 10.1016/j.cja.2019.08.017 |
| Reference: | [11] Chernov, N., Stoyan, Y., Romanova, T.: Mathematical model and efficient algorithms for object packing problem.Comput. Geom. 43 (2010), 535-553. Zbl 1228.05117, MR 2585572, 10.1016/j.comgeo.2009.12.003 |
| Reference: | [12] Chernov, N., Stoyan, Y., Romanova, T., Pankratov, A.: Phi-functions for 2D objects formed by line segments and circular arcs.Adv. Oper. Res. 2012 (2012), Article ID 346358, 26 pages. Zbl 1246.90127, MR 2916161, 10.1155/2012/346358 |
| Reference: | [13] Cherri, L. H., Cherri, A. C., Soler, E. M.: Mixed integer quadratically-constrained programming model to solve the irregular strip packing problem with continuous rotations.J. Glob. Optim. 72 (2018), 89-107. Zbl 1414.90234, MR 3846928, 10.1007/s10898-018-0638-x |
| Reference: | [14] Duriagina, Z., Lemishka, I., Litvinchev, I., Marmolejo, J. A., Pankratov, A., Romanova, T., Yaskov, G.: Optimized filling of a given cuboid with spherical powders for additive manufacturing.J. Oper. Res. Soc. China 9 (2021), 853-868. Zbl 1488.90123, MR 4337993, 10.1007/s40305-020-00314-9 |
| Reference: | [15] Duriagina, Z., Pankratov, A., Romanova, T., Litvinchev, I., Bennel, J., Lemishka, I., Maximov, S.: Optimized packing titanium alloy powder particles.Computation 11 (2023), Article ID 22, 13 pages. 10.3390/computation11020022 |
| Reference: | [16] Fasano, G.: Solving Non-Standard Packing Problems by Global Optimization and Heuristics.SpringerBriefs in Optimization. Springer, Cham (2014). Zbl 1292.49001, MR 3309433, 10.1007/978-3-319-05005-8 |
| Reference: | [17] Fasano, G.: A modeling-based approach for non-standard packing problems.Optimized Packings with Applications Springer Optimization and Its Applications 105. Springer, Cham (2015), 67-85. Zbl 1384.90084, MR 3379375, 10.1007/978-3-319-18899-7_4 |
| Reference: | [18] Fasano, G., Pintér, J. D., (Eds.): Optimized Packings with Applications.Springer Optimization and Its Applications 105. Springer, Cham (2015). Zbl 1329.90005, MR 3381562, 10.1007/978-3-319-18899-7 |
| Reference: | [19] Fischer, A., Litvinchev, I., Romanova, T., Stetsyuk, P., Yaskov, G.: Packing spheres with quasi-containment conditions.J. Glob. Optim. 90 (2024), 671-689. Zbl 1558.90139, MR 4810486, 10.1007/s10898-024-01412-1 |
| Reference: | [20] Technology, Fraunhofer Institute of Production: Additive Manufacturing in the Process Chain.Available at {\def{ }\let \relax \brokenlink{https://www.ipt.fraunhofer.de/en/technologies/}{additive-manufacturing/technology-evaluation.html}}\kern0pt. |
| Reference: | [21] Garey, M. R., Johnson, D. S.: Computers and Intractability: A Guide to Theory of NP-Completeness.W. H. Freeman, San Francisco (1979). Zbl 0411.68039, MR 0519066 |
| Reference: | [22] Gebhardt, A.: Understanding Additive Manufacturing: Rapid Prototyping, Rapid Tooling, Rapid Manufacturing.Hanser, Munich (2012). 10.3139/9783446431621 |
| Reference: | [23] Hifi, M., Mohamed-Youssouf, A., Yousef, L.: A threshold search-based population algorithm for the sphere packing problem.Knowl. Based Syst. 261 (2023), Article ID 110177. 10.1016/j.knosys.2022.110177 |
| Reference: | [24] Iori, M., Lima, V. L. de, Martello, S., Miyazawa, F. K., Monaci, M.: Exact solution techniques for two-dimensional cutting and packing.Eur. J. Oper. Res. 289 (2021), 399-415. Zbl 1487.90556, MR 4170749, 10.1016/j.ejor.2020.06.050 |
| Reference: | [25] Jones, D. R.: A fully general, exact algorithm for nesting irregular shapes.J. Glob. Optim. 59 (2014), 367-404. Zbl 1298.90087, MR 3216685, 10.1007/s10898-013-0129-z |
| Reference: | [26] Kallrath, J., Rebennack, S.: Cutting ellipses from area-minimizing rectangles.J. Glob. Optim. 59 (2014), 405-437. Zbl 1301.90073, MR 3216686, 10.1007/s10898-013-0125-3 |
| Reference: | [27] Kallrath, J., Romanova, T., Pankratov, A., Litvinchev, I., Infante, L.: Packing convex polygons in minimum-perimeter convex hulls.J. Glob. Optim. 85 (2023), 39-59. Zbl 1511.90332, MR 4530274, 10.1007/s10898-022-01194-4 |
| Reference: | [28] Kiseleva, E. M.: The emergence and formation of the theory of optimal set partitioning for sets of the $n$-dimensional Euclidean space: Theory and application.J. Autom. Inf. Sci. 50 (2018), 1-24. 10.1615/JAutomatInfScien.v50.i9.10 |
| Reference: | [29] Leao, A. A. S., Toledo, F. M. B., Oliveira, J. F., Carravilla, M. A.: A semi-continuous MIP model for the irregular strip packing problem.Int. J. Prod. Res. 54 (2016), 712-721. 10.1080/00207543.2015.1041571 |
| Reference: | [30] Leary, M., Merli, L., Torti, F., Mazur, M., Brandt, M.: Optimal topology for additive manufacture: A method for enabling additive manufacture of support-free optimal structures.Mater. Design 63 (2014), 678-690. 10.1016/j.matdes.2014.06.015 |
| Reference: | [31] Lee, M., Fang, Q., Cho, Y., Ryu, J., Liu, L., Kim, D.-S.: Support-free hollowing for 3D printing via Voronoi diagram of ellipses.Comput.-Aided Des. 101 (2018), 23-36. 10.1016/j.cad.2018.03.007 |
| Reference: | [32] Li, J., An, X., Wang, J., Zhao, H., Zou, R., Dong, K., Gou, D.: Experimental study on 3D vibrated packing densification of mono-sized dodecahedral particles.Powder Technol. 367 (2020), 703-712. 10.1016/j.powtec.2020.04.020 |
| Reference: | [33] Litvinchev, I., Infante, L., Romanova, T., Martinez-Noa, A., Gutierrez, L.: Packing soft convex polygons in an optimized convex container.Mobile Netw. Appl. 29 (2024), 211-220. 10.1007/s11036-023-02286-5 |
| Reference: | [34] Litvinchev, I., Pankratov, A., Romanova, T.: 3D irregular packing in an optimized cuboid container.IFAC-PapersOnLine 52 (2019), 2014-2019. 10.1016/j.ifacol.2019.11.499 |
| Reference: | [35] Markl, M., Körner, C.: Multiscale modeling of powder bed-based additive manufacturing.Annual Rev. Mater. Res. 46 (2016), 93-123. 10.1146/annurev-matsci-070115-032158 |
| Reference: | [36] Melashenko, O., Romanova, T., Litvinchev, I., Gomez, C. G. Martínez, Yang, R., Sun, B.: A model-based heuristic for packing soft rotated rectangles in an optimized convex container with prohibited zones.Mathematics 13 (2025), Article ID 493, 21 pages. 10.3390/math13030493 |
| Reference: | [37] M'Hallah, R., Alkandari, A., Mladenovic, N.: Packing unit spheres into the smallest sphere using VNS and NLP.Comput. Oper. Res. 40 (2013), 603-615. Zbl 1349.90718, MR 2989530, 10.1016/j.cor.2012.08.019 |
| Reference: | [38] Pankratov, A., Romanova, T., Litvinchev, I.: Packing ellipses in an optimized convex polygon.J. Glob. Optim. 75 (2019), 495-522. Zbl 1429.90065, MR 4012437, 10.1007/s10898-019-00777-y |
| Reference: | [39] Pankratov, A., Romanova, T., Litvinchev, I.: Packing oblique 3D objects.Mathematics 8 (2020), Article ID 1130, 16 pages. 10.3390/math8071130 |
| Reference: | [40] Pederson, R., Andersson, J., Joshi, S.: Additive Manufacturing of High-Performance Metallic Materials.Elsevier, Amsterdam (2024). 10.1016/C2021-0-00199-1 |
| Reference: | [41] Pintér, J. D., Kampas, F. J., Castillo, I.: Globally optimized packings of non-uniform size spheres in $\Bbb{R}^d$: A computational study.Optim. Lett. 12 (2018), 585-613. Zbl 1400.90265, MR 3784568, 10.1007/s11590-017-1194-x |
| Reference: | [42] Romanova, T., Bennell, J., Stoyan, Y., Pankratov, A.: Packing of concave polyhedra with continuous rotations using nonlinear optimisation.Eur. J. Oper. Res. 268 (2018), 37-53. Zbl 1403.90586, MR 3767526, 10.1016/j.ejor.2018.01.025 |
| Reference: | [43] Romanova, T., Chuhai, A., Yaskov, G., Litvinchev, I., Stoian, Y.: Irregular packing for additive manufacturing.Advances in Mechanical and Power Engineering Lecture Notes in Mechanical Engineering. Springer, Cham (2023), 256-264. 10.1007/978-3-031-18487-1_26 |
| Reference: | [44] Romanova, T., Litvinchev, I., Pankratov, A.: Packing ellipsoids in an optimized cylinder.Eur. J. Oper. Res. 285 (2020), 429-443. Zbl 1441.90142, MR 4085188, 10.1016/j.ejor.2020.01.051 |
| Reference: | [45] Romanova, T. E., Stetsyuk, P. I., Fischer, A., Yaskov, G. M.: Proportional packing of circles in a circular container.Cybern. Syst. Anal. 59 (2023), 82-89. Zbl 1518.90095, 10.1007/s10559-023-00544-8 |
| Reference: | [46] T. Romanova, Y. Stoyan, A. Pankratov, I. Litvinchev, K. Avramov, M. Chernobryvko, I. Yanchevskyi, I. Mozgova, J. Bennell: Optimal layout of ellipses and its application for additive manufacturing.Int. J. Prod. Res. 59 (2021), 560-575. 10.1080/00207543.2019.1697836 |
| Reference: | [47] Romanova, T., Stoyan, Y., Pankratov, A., Litvinchev, I., Plankovskyy, S., Tsegelnyk, Y., Shypul, O.: Sparsest balanced packing of irregular 3D objects in a cylindrical container.Eur. J. Oper. Res. 291 (2021), 84-100. Zbl 1487.90567, MR 4200641, 10.1016/j.ejor.2020.09.021 |
| Reference: | [48] Romanova, T., Stoyan, Y., Pankratov, A., Litvinchev, I., Yanchevsky, I., Mozgova, I.: Optimal packing in additive manufacturing.IFAC-PapersOnLine 52 (2019), 2758-2763. 10.1016/j.ifacol.2019.11.625 |
| Reference: | [49] Romanova, T., Yaskov, G., Litvinchev, I., Yanchevskyi, I., Stoian, Y., Vasant, P.: Optimized designing spherical void structures in 3D domains.Advances of Artificial Intelligence in a Green Energy Environment Academic Press, London (2022), 331-346. 10.1016/B978-0-323-89785-3.00008-6 |
| Reference: | [50] Rozvany, G. I. N., Zhou, M., Birker, T.: Generalized shape optimization without homogenization.Struct. Optim. 4 (1992), 250-252. 10.1007/BF01742754 |
| Reference: | [51] Scheithauer, G.: Introduction to Cutting and Packing Optimization: Problems, Modeling Approaches, Solution Methods.International Series in Operations Research & Management Science 263. Springer, Cham (2018). Zbl 1391.90002, MR 3726881, 10.1007/978-3-319-64403-5 |
| Reference: | [52] Scheithauer, G., Stoyan, Y. G., Romanova, T. Y.: Mathematical modeling of interactions of primary geometric 3D objects.Cybern. Syst. Anal. 41 (2005), 332-342. Zbl 1102.68684, MR 2218452, 10.1007/s10559-005-0067-y |
| Reference: | [53] Scheithauer, U., Romanova, T., Pankratov, O., Schwarzer-Fischer, R., Schwentenwein, M., Ertl, F., Fischer, A.: Potentials of numerical methods for increasing the productivity of additive manufacturing processes.Ceramics 6 (2023), 630-650. 10.3390/ceramics6010038 |
| Reference: | [54] Schwentenwein, M., Homa, J.: Additive manufacturing of dense alumina ceramics.Int. J. Appl. Ceramic Technol. 12 (2015), 1-7. 10.1111/ijac.12319 |
| Reference: | [55] Stetsyuk, P. I., Romanova, T. E., Scheithauer, G.: On the global minimum in a balanced circular packing problem.Optim. Lett. 10 (2016), 1347-1360. Zbl 1353.90133, MR 3529852, 10.1007/s11590-015-0937-9 |
| Reference: | [56] Stoyan, Y., Pankratov, O., Lemishka, I., Duriagina, Z., Bennell, J., Romanova, T., Stetsyuk, P.: Simulation of 3D volume filling with non-spherical and spherical titanium alloy powder particles for additive manufacturing.Cybern. Syst. Anal. 60 (2024), 422-432. Zbl 1551.90081, 10.1007/s10559-024-00683-6 |
| Reference: | [57] Stoyan, Y., Pankratov, A., Romanova, T.: Quasi-phi-functions and optimal packing of ellipses.J. Glob. Optim. 65 (2016), 283-307. Zbl 1369.90151, MR 3498568, 10.1007/s10898-015-0331-2 |
| Reference: | [58] Stoyan, Y., Romanova, T.: Mathematical models of placement optimisation: Two- and three-dimensional problems and applications.Modeling and Optimization in Space Engineering Springer Optimization and Its Applications 73. Springer, New York (2013), 363-388. Zbl 1365.90163, MR 2905704, 10.1007/978-1-4614-4469-5_15 |
| Reference: | [59] Stoyan, Y. G., Romanova, T. E., Pankratov, O. V., Stetsyk, P. I., Maksimov, S. V.: Sparse balanced layout of ellipsoids.Cybern. Syst. Anal. 57 (2021), 864-873. Zbl 1486.90167, MR 4352819, 10.1007/s10559-021-00412-3 |
| Reference: | [60] Stoyan, Y., Scheithauer, G., Gil, N., Romanova, T.: $\Phi$-functions for complex 2D-objects.4OR 2 (2004), 69-84. Zbl 1125.90382, MR 2043317, 10.1007/s10288-003-0027-1 |
| Reference: | [61] Stoyan, Y., Terno, J., Gil, M., Romanova, T., Scheithauer, G.: Construction of a $\Phi$-function for two convex polytopes.Appl. Math. 29 (2002), 199-218. Zbl 1053.90009, MR 1923614, 10.4064/am29-2-6 |
| Reference: | [62] Stoyan, Y., Terno, J., Scheithauer, G., Gil, N., Romanova, T.: $\Phi$-functions for primary 2D-objects.Stud. Inform. Univ. 2 (2002), 1-32. |
| Reference: | [63] Svyetlichnyy, D.: Model of the selective laser melting process-powder deposition models in multistage multi-material simulations.Appl. Sci. 13 (2023), Article ID 6196, 19 pages. 10.3390/app13106196 |
| Reference: | [64] Wächter, A., Biegler, L. T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming.Math. Program. 106 (2006), 25-57. Zbl 1134.90542, MR 2195616, 10.1007/s10107-004-0559-y |
| Reference: | [65] Waechter, A., Laird, C.: Ipopt - Interior point optimizer.Available at https://github.com/coin-or/Ipopt. |
| Reference: | [66] Wang, A., Hanselman, C. L., Gounaris, C. E.: A customized branch-and-bound approach for irregular shape nesting.J. Glob. Optim. 71 (2018), 935-955. Zbl 1405.90113, MR 3827295, 10.1007/s10898-018-0637-y |
| Reference: | [67] Wäscher, G., Hauà ner, H., Schumann, H.: An improved typology of cutting and packing problems.Eur. J. Oper. Res. 183 (2007), 1109-1130. Zbl 1278.90347, 10.1016/j.ejor.2005.12.047 |
| Reference: | [68] Yantchevskyi, I., Lachmayer, R., Mozgova, I., Lippert, R.-B., Yaskov, G., Romanova, T., Litvinchev, I.: Circular packing for support-free structures.EAI Endorsed Trans. Energy Web 7 (2020), Article ID 20(30): e3, 10 pages. 10.4108/eai.13-7-2018.164561 |
| Reference: | [69] Zhang, J., Jung, Y.-G., (Eds.): Additive Manufacturing: Materials, Processes, Quantifications and Applications.Butterworth-Heinemann, Oxford (2018). 10.1016/C2016-0-01595-4 |
| Reference: | [70] Zhao, B., An, X., Wang, Y., Zhao, H., Shen, L., Sun, X., Zou, R.: Packing of different shaped tetrahedral particles: DEM simulation and experimental study.Powder Technol. 360 (2020), 21-32. 10.1016/j.powtec.2019.09.072 |
| Reference: | [71] Zhao, B., An, X., Zhao, H., Gou, D., Shen, L., Sun, X.: DEM simulation on random packings of binary tetrahedron-sphere mixtures.Powder Technol. 361 (2020), 160-170. 10.1016/j.powtec.2019.09.055 |
| Reference: | [72] Zhao, Z., Li, L., Tan, L., Bai, P., Li, J., Wu, L., Liao, H., Cheng, Y.: Simulation of stress field during the selective laser melting process of the nickel-based superalloy, GH4169.Materials 11 (2018), Article ID 1525, 14 pages. 10.3390/ma11091525 |
| Reference: | [73] Zhou, J., Zhang, Y., Chen, J. K.: Numerical simulation of random packing of spherical particles for powder-based additive manufacturing.J. Manuf. Sci. Eng. 131 (2009), Article ID 031004, 8 pages. 10.1115/1.3123324 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
