Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
packing optimization; additive manufacturing; mathematical modeling; approximate solution method
packing optimization; additive manufacturing; mathematical modeling; approximate solution method
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.
References:
[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. DOI 10.1145/3092026 | MR 3716949 | Zbl 1427.68100
[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. DOI 10.1016/j.ejor.2024.09.013 | MR 4877319 | Zbl 1573.90470
[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. DOI 10.1016/j.procs.2025.10.312
[4] Allen, T.: Particle Size Measurement. Volume 1. Powder Sampling and Particle Size Measurement. Chapman & Hall, London (1997).
[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. DOI 10.1016/j.ijpe.2013.04.007
[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. DOI 10.1080/00207543.2018.1534016
[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. DOI 10.1016/0045-7825(88)90086-2 | MR 0969217 | Zbl 0671.73065
[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. DOI 10.1007/s10479-008-0456-5 | MR 2684242 | Zbl 1201.90167
[9] Birgin, E. G., Lobato, R. D., Martínez, J. M.: Packing ellipsoids by nonlinear optimization. J. Glob. Optim. 65 (2016), 709-743. DOI 10.1007/s10898-015-0395-z | MR 3522065 | Zbl 1377.90088
[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. DOI 10.1016/j.cja.2019.08.017
[11] Chernov, N., Stoyan, Y., Romanova, T.: Mathematical model and efficient algorithms for object packing problem. Comput. Geom. 43 (2010), 535-553. DOI 10.1016/j.comgeo.2009.12.003 | MR 2585572 | Zbl 1228.05117
[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. DOI 10.1155/2012/346358 | MR 2916161 | Zbl 1246.90127
[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. DOI 10.1007/s10898-018-0638-x | MR 3846928 | Zbl 1414.90234
[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. DOI 10.1007/s40305-020-00314-9 | MR 4337993 | Zbl 1488.90123
[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. DOI 10.3390/computation11020022
[16] Fasano, G.: Solving Non-Standard Packing Problems by Global Optimization and Heuristics. SpringerBriefs in Optimization. Springer, Cham (2014). DOI 10.1007/978-3-319-05005-8 | MR 3309433 | Zbl 1292.49001
[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. DOI 10.1007/978-3-319-18899-7_4 | MR 3379375 | Zbl 1384.90084
[18] Fasano, G., Pintér, J. D., (Eds.): Optimized Packings with Applications. Springer Optimization and Its Applications 105. Springer, Cham (2015). DOI 10.1007/978-3-319-18899-7 | MR 3381562 | Zbl 1329.90005
[19] Fischer, A., Litvinchev, I., Romanova, T., Stetsyuk, P., Yaskov, G.: Packing spheres with quasi-containment conditions. J. Glob. Optim. 90 (2024), 671-689. DOI 10.1007/s10898-024-01412-1 | MR 4810486 | Zbl 1558.90139
[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
[21] Garey, M. R., Johnson, D. S.: Computers and Intractability: A Guide to Theory of NP-Completeness. W. H. Freeman, San Francisco (1979). MR 0519066 | Zbl 0411.68039
[22] Gebhardt, A.: Understanding Additive Manufacturing: Rapid Prototyping, Rapid Tooling, Rapid Manufacturing. Hanser, Munich (2012). DOI 10.3139/9783446431621
[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. DOI 10.1016/j.knosys.2022.110177
[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. DOI 10.1016/j.ejor.2020.06.050 | MR 4170749 | Zbl 1487.90556
[25] Jones, D. R.: A fully general, exact algorithm for nesting irregular shapes. J. Glob. Optim. 59 (2014), 367-404. DOI 10.1007/s10898-013-0129-z | MR 3216685 | Zbl 1298.90087
[26] Kallrath, J., Rebennack, S.: Cutting ellipses from area-minimizing rectangles. J. Glob. Optim. 59 (2014), 405-437. DOI 10.1007/s10898-013-0125-3 | MR 3216686 | Zbl 1301.90073
[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. DOI 10.1007/s10898-022-01194-4 | MR 4530274 | Zbl 1511.90332
[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. DOI 10.1615/JAutomatInfScien.v50.i9.10
[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. DOI 10.1080/00207543.2015.1041571
[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. DOI 10.1016/j.matdes.2014.06.015
[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. DOI 10.1016/j.cad.2018.03.007
[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. DOI 10.1016/j.powtec.2020.04.020
[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. DOI 10.1007/s11036-023-02286-5
[34] Litvinchev, I., Pankratov, A., Romanova, T.: 3D irregular packing in an optimized cuboid container. IFAC-PapersOnLine 52 (2019), 2014-2019. DOI 10.1016/j.ifacol.2019.11.499
[35] Markl, M., Körner, C.: Multiscale modeling of powder bed-based additive manufacturing. Annual Rev. Mater. Res. 46 (2016), 93-123. DOI 10.1146/annurev-matsci-070115-032158
[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. DOI 10.3390/math13030493
[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. DOI 10.1016/j.cor.2012.08.019 | MR 2989530 | Zbl 1349.90718
[38] Pankratov, A., Romanova, T., Litvinchev, I.: Packing ellipses in an optimized convex polygon. J. Glob. Optim. 75 (2019), 495-522. DOI 10.1007/s10898-019-00777-y | MR 4012437 | Zbl 1429.90065
[39] Pankratov, A., Romanova, T., Litvinchev, I.: Packing oblique 3D objects. Mathematics 8 (2020), Article ID 1130, 16 pages. DOI 10.3390/math8071130
[40] Pederson, R., Andersson, J., Joshi, S.: Additive Manufacturing of High-Performance Metallic Materials. Elsevier, Amsterdam (2024). DOI 10.1016/C2021-0-00199-1
[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. DOI 10.1007/s11590-017-1194-x | MR 3784568 | Zbl 1400.90265
[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. DOI 10.1016/j.ejor.2018.01.025 | MR 3767526 | Zbl 1403.90586
[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. DOI 10.1007/978-3-031-18487-1_26
[44] Romanova, T., Litvinchev, I., Pankratov, A.: Packing ellipsoids in an optimized cylinder. Eur. J. Oper. Res. 285 (2020), 429-443. DOI 10.1016/j.ejor.2020.01.051 | MR 4085188 | Zbl 1441.90142
[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. DOI 10.1007/s10559-023-00544-8 | Zbl 1518.90095
[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. DOI 10.1080/00207543.2019.1697836
[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. DOI 10.1016/j.ejor.2020.09.021 | MR 4200641 | Zbl 1487.90567
[48] Romanova, T., Stoyan, Y., Pankratov, A., Litvinchev, I., Yanchevsky, I., Mozgova, I.: Optimal packing in additive manufacturing. IFAC-PapersOnLine 52 (2019), 2758-2763. DOI 10.1016/j.ifacol.2019.11.625
[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. DOI 10.1016/B978-0-323-89785-3.00008-6
[50] Rozvany, G. I. N., Zhou, M., Birker, T.: Generalized shape optimization without homogenization. Struct. Optim. 4 (1992), 250-252. DOI 10.1007/BF01742754
[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). DOI 10.1007/978-3-319-64403-5 | MR 3726881 | Zbl 1391.90002
[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. DOI 10.1007/s10559-005-0067-y | MR 2218452 | Zbl 1102.68684
[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. DOI 10.3390/ceramics6010038
[54] Schwentenwein, M., Homa, J.: Additive manufacturing of dense alumina ceramics. Int. J. Appl. Ceramic Technol. 12 (2015), 1-7. DOI 10.1111/ijac.12319
[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. DOI 10.1007/s11590-015-0937-9 | MR 3529852 | Zbl 1353.90133
[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. DOI 10.1007/s10559-024-00683-6 | Zbl 1551.90081
[57] Stoyan, Y., Pankratov, A., Romanova, T.: Quasi-phi-functions and optimal packing of ellipses. J. Glob. Optim. 65 (2016), 283-307. DOI 10.1007/s10898-015-0331-2 | MR 3498568 | Zbl 1369.90151
[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. DOI 10.1007/978-1-4614-4469-5_15 | MR 2905704 | Zbl 1365.90163
[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. DOI 10.1007/s10559-021-00412-3 | MR 4352819 | Zbl 1486.90167
[60] Stoyan, Y., Scheithauer, G., Gil, N., Romanova, T.: $\Phi$-functions for complex 2D-objects. 4OR 2 (2004), 69-84. DOI 10.1007/s10288-003-0027-1 | MR 2043317 | Zbl 1125.90382
[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. DOI 10.4064/am29-2-6 | MR 1923614 | Zbl 1053.90009
[62] Stoyan, Y., Terno, J., Scheithauer, G., Gil, N., Romanova, T.: $\Phi$-functions for primary 2D-objects. Stud. Inform. Univ. 2 (2002), 1-32.
[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. DOI 10.3390/app13106196
[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. DOI 10.1007/s10107-004-0559-y | MR 2195616 | Zbl 1134.90542
[65] Waechter, A., Laird, C.: Ipopt - Interior point optimizer. Available at https://github.com/coin-or/Ipopt
[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. DOI 10.1007/s10898-018-0637-y | MR 3827295 | Zbl 1405.90113
[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. DOI 10.1016/j.ejor.2005.12.047 | Zbl 1278.90347
[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. DOI 10.4108/eai.13-7-2018.164561
[69] Zhang, J., Jung, Y.-G., (Eds.): Additive Manufacturing: Materials, Processes, Quantifications and Applications. Butterworth-Heinemann, Oxford (2018). DOI 10.1016/C2016-0-01595-4
[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. DOI 10.1016/j.powtec.2019.09.072
[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. DOI 10.1016/j.powtec.2019.09.055
[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. DOI 10.3390/ma11091525
[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. DOI 10.1115/1.3123324
Search
Partner of
