2023, issue 4, p. 34-42
Received 29.09.2023; Revised 15.10.2023; Accepted 28.11.2023
Published 04.12.2023; First Online 05.12.2023
https://doi.org/10.34229/2707-451X.23.4.5
Previous | FULL TEXT (in Ukrainian) | Next
Parallel Algorithm of Balanced Sparse Packing of Rectangular Parallelepipeds
Oleg Berezovskyi *
, Oleksii Lykhovyd,
Maria Stetsyuk
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. Varieties of the problem of packing of rectangular parallelepipeds have a wide practical application in various fields of activity, for example, in the optimal filling of containers, in the design and layout of a wide variety of technological objects and systems, in the creation of backup copies on removable media, in the optimization of storage, protection and transportation of goods, in additive manufacturing, etc. This work continues research on this topic and is devoted to the problem of balanced sparse packing of a given set of identically oriented rectangular parallelepipeds of different sizes into a rectangular parallelepiped of minimum volume. It presents a mathematical model for this packing problem and a parallel algorithm for solving it. This algorithm is based on the reduction of the original problem to an unconditional optimization problem using penalty functions, which is solved by the multistart method, in which r-algorithm is used to find local minima from the set of generated starting points.
The purpose. Construction of a mathematical model and development of an algorithm for solving the problem of balanced sparse packing of a given set of identically oriented rectangular parallelepipeds into a rectangular parallelepiped of minimum volume.
Results. A mathematical model and a parallel algorithm for balanced sparse packing of identically oriented rectangular parallelepipeds into a rectangular parallelepiped of minimum volume are presented. The algorithm is based on reducing the problem with the help of penalty functions to an unconditional nondifferentiable optimization problem, for finding the solution of which multistart method is used in combination with r-algorithm for finding local minima. The results of numerical experiments are given.
Conclusions. The application of the algorithm described in the work based on non-smooth optimization methods allows to improve the results of balanced sparse packing of rectangular parallelepipeds in an acceptable time. Numerical experiments showed effectiveness of the algorithm in practice.
Keywords: balanced sparse packing, multistart method, r-algorithm, penalty function, "Master-Slave" procedure, numerical experiments.
Cite as: Berezovskyi O., Lykhovyd O., Stetsyuk M. Parallel Algorithm of Balanced Sparse Packing of Rectangular Parallelepipeds. Cybernetics and Computer Technologies. 2023. 4. P. 34–42. (in Ukrainian) https://doi.org/10.34229/2707-451X.23.4.5
References
1. Hopper E., Turton B.C.H. A review of the application of meta-heuristic algorithms to 2D strip packing problems. Artificial Intelligence Review. 2001. 16. P. 257–300. https://doi.org/10.1023/A:1012590107280
2. Lins L., Lins S., Morabito R. An n-tet graph approach for non-guillotine packings of n-dimensional boxes into an n-container. European Journal of Operational Research. 2002. 141 (2). P. 421–439. https://doi.org/10.1016/S0377-2217(02)00135-2
3. Hu N.-Z., Li H.-L., Tsai J.-F. Solving Packing Problems by a Distributed Global Optimization Algorithm. Mathematical Problems in Engineering. 2012. Vol. 2012, Art. ID 931092. 13 p. https://doi.org/10.1155/2012/931092
4. Stetsyuk P.I., Bortis Н., Emmenegger Z.-F. et al. Institutional and Technological Modifications in Countries with Market and Transition Economy. Kyiv: Kiyevo-Mogilyansky Academy, 2015. 336 p. (in Russian)
5. Stetsyuk P.I., Romanova T.E., Scheithauer G. On the global minimum in a balanced circular packing problem. Optimization Letters. 2016. 10 (6). P. 1347–1360. https://doi.org/10.1007/s11590-015-0937-9
6. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. Boston/London/Dordrecht: Kluwer Academic Publishers, 1998. 394 p. https://doi.org/10.1007/978-1-4757-6015-6
7. Stetsyuk P.I., Berezovskyi O.A., Lykhovyd O.P., Stetsyuk M.G. Mathematical models and algorithms for optimal packing of spheres and cubes in spherical and cubic containers. International Scientific Technical Journal "Problems of Control and Informatics". 2022. 3. C. 87–100. (in Ukrainian)
8. Lykhovyd O.P. On the implementation of a parallel algorithm for solving equilibrium packing problems. Theory of optimal solutions. 2015. P. 154–159. http://dspace.nbuv.gov.ua/handle/123456789/112413 (in Russian)
9. Lykhovyd O.P., Stetsyuk P.I. Computer program "Parallel program "Balanced packing of circles with specified permissible distances between them". Certificate of copyright registration for the work No. 109298. Ukraine. The national body of intellectual property, the state enterprise "Ukrainian Institute of Intellectual Property" (Ukrpatent). Date of registration 11/10/2021. 40 p. (in Ukrainian)
10. Stetsyuk P.I. Ellipsoid methods and r-algorithms. Chisinau: Evrika, 2014. 488 p. (in Russian)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next