Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
Volume 55 >>> № 6 NOVEMBER — DECEMBER 2019
UDC 519.85
T.E. Romanova1, P.I. Stetsyuk2, A.M. Chugay3, S.B. Shekhovtsov4


1 A.N. Podgorny Institute for Mechanical Engineering of the National Academy of Sciences of Ukraine, Kharkiv, Ukraine

 tarom27@yahoo.com

2 V.M. Glushkov Institute of Cybernetics, National Academy
of Sciences of Ukraine, Kyiv, Ukraine

 stetsyukp@gmail.com

3 A.N. Podgorny Institute for Mechanical Engineering of the National Academy of Sciences of Ukraine, Kharkiv, Ukraine

 chugay@ipmach.kharkov.ua

4 Kharkiv National University of Internal Affairs, Kharkiv, Ukraine

 ep109@ukr.net

PARALLEL COMPUTING TECHNOLOGIES FOR SOLVING OPTIMIZATION PROBLEMS
OF GEOMETRIC DESIGN

Abstract. The paper describes the use of parallel computing technologies on systems with shared memory and distributed memory for solving optimization geometric design problems. The first technology is based on the maxmin properties of phi-functions for composed objects, and the second technology uses the multi-start strategy and methods for minimizing non-smooth functions. This made it possible to reduce several times the computational time spent in searching for locally optimal placements of 2D and 3D objects and to get the best results in terms of the objective function value.

Keywords: placement of geometric objects, phi-function, nonlinear programming, parallel computing.



FULL TEXT

REFERENCES

  1. Liu X., Liu J., Cao A. HAPE3D — a new constructive algorithm for the 3D irregular packing problem. Frontiers Inf. Technol. Electronic Eng. 2015. Vol. 16, N 5. P. 380–390.

  2. Guangqiang L., Fengqiang Z., Rubo Z. Du Jialu Du., Chen G., Yiran Z. A parallel particle bee colony algorithm approach to layout optimization. Journal of Computational and Theoretical Nanoscience. 2016. Vol. 13, N 7. P. 4151–4157.

  3. Karabulut K., Inceolu M.A. Hybrid genetic algorithm for packing in 3D with deepest bottom left with fill method. In: Advances in Information Systems. ADVIS 2004. Lecture Notes in Computer Science. Yakhno T. (Ed.). 2004. Vol. 3261. P. 441–450.

  4. Litvinchev I., Infante L., Ozuna L. Approximate packing: integer programming models, valid inequalities and nesting. In: Optimized Packings and Their Applications (Ser. Springer Optimization and Its Applications). Fasano G., Pinter J.D. (Eds.). 2015. Vol. 105. P. 187–205.

  5. Litvinchev I., Infante L., Ozuna L. Packing circular-like objects in a rectangular container. Journal of Computer and Systems Sciences International. 2015. Vol. 54, N 2. P. 259–267.

  6. Burke E.K., Hellier R.S. R., Kendall G., Whitwell G. Irregular packing using the line and arc no-fit polygon. Operations Research. 2010. Vol. 58, N 4. P. 948–970.

  7. Cherri L.H., Mundim L.R., Andretta M., Toledo F.M., Oliveira J. F., Carravilla M.A. Robust mixed-integer linear programming models for the irregular strip packing problem. European Journal of Operational Research. 2016. Vol. 253. P. 570–583.

  8. Stoyan Yu., Romanova T. Mathematical models of placement optimization: two- and three-dimensional problems and applications. In: Modeling and Optimization in Space Engineering. (Ser. Springer Optimization and Its Applications). Fasano G., Pinter J.D. (Eds.). New York: Springer, 2012. Vol. 73. 404 p.

  9. Stoyan Yu., Yakovlev S. Configuration space of geometric objects. Cybernetics and Systems Analysis. 2018. Vol. 54, N 5. P. 716–726.

  10. Stoyan Yu., Pankratov A., Romanova T. Placement problems for irregular objects: mathematical modeling, optimization and applications. In: Optimization Methods and Applications. Modeling and Optimization in Space Engineering (Ser. Springer Optimization and Its Applications). Butenko S., Pardalos P., Shylo V. (Eds.). New York: Springer, 2017. Vol. 130. P. 521–559.

  11. Stoyan Yu., Chugay А. Mathematical modeling of the interaction of non-oriented convex polytopes. Cybernetics and Systems Analysis. 2012. Vol. 48, N 6. P. 837–845.

  12. Stoyan Yu., Pankratov A., Romanova T. Cutting and packing problems for irregular objects with continuous rotations: mathematical modeling and nonlinear optimization. Journal of the Operational Research Society. 2016. Vol. 67, Iss. 5. P. 786–800.

  13. Stoyan Yu., Pankratov A., Romanova T., Chugay A. Optimized object packings using quasi--functions. In: Optimized Packings and Their Applications (Ser. Springer Optimization and Its Applications). Fasano G., Pinter J.D. (Eds.). New York: Springer, 2015. Vol. 105. P. 265–291.

  14. Stoyan Y.G., Chugay A.M. Packing different cuboids with rotations and spheres into a cuboid. Advances in Decision Sciences. 2014. URL:: https://www.hindawi.com/journals/ads/2014/571743.

  15. Stoyan Y.G., Semkin V.V., Chugay A.M. Modeling close packing of 3D objects. Cybernetics and Systems Analysis. 2016. Vol. 52, N 2. P. 296–304.

  16. Stoian Y.E., Chugay A.M., Pankratov A.V., Romanova T.E. Two approaches to modeling and solving the packing problem for convex polytopes. Cybernetics and Systems Analysis. 2018. Vol. 54, N 4. P. 585–593.

  17. Romanova T., Bennell J., Stoyan Yu., Pankratov A. Packing of concave polyhedra with continuous rotations using nonlinear optimization. European Journal of Operational Research. 2018. Vol. 268, Iss. 1. P 37–53.

  18. Pankratov A., Romanova T., Litvinchev I. Packing ellipses in an optimized convex polygon. Journal of Global Optimization. 2019. https://doi.org/10.1007/s10898-019-00777-y.

  19. Pankratov A., Romanova T., Litvinchev I. Packing ellipses in an optimized rectangular container. Wireless Networks. 2018. https://doi.org/10.1007/s11276-018-1890-1.

  20. Romanova T., Pankratov A., Litvinchev I., Pankratova Yu., Urniaieva I. Optimized packing clusters of objects in a rectangular container. Mathematical Problems in Engineering. Vol. 2019. Article ID 4136430. 12 p. https://doi.org/10.1155/2019/4136430.

  21. Wang Y., Lin C.L., Miller J.D. 3D image segmentation for analysis of multisize particles in a packed particle bed. Powder Technology. 2016. Vol. 301. P. 160–168.

  22. Li S.X., Zhao J., Lu P., Xie Y. Maximum packing densities of basic 3D objects. Chinese Science Bulletin. 2010. Vol. 55, Iss. 2. P.114–119.

  23. Ramya A., Vanapalli S. 3D printing technologies in various applications. International Journal of Mechanical Engineering and Technology. 2016. Vol. 7, N 3. P. 396–409.

  24. Baumers M., Dickens P., Tuck C., Hague R. The cost of additive manufacturing: machine productivity, economies of scale and technology-push. Technological Forecasting & Social Change. 2016. Vol. 102, Iss. C. P. 193–201.

  25. Voevodin V.V., Voevodin Vl.V. Parallel computing [in Russian]. St. Petersburg: BHV Petersburg, 2002. 608 p.

  26. The cluster complex of the Institute of Cybernetics. Cluster complex SKIT. URL: https:// icybcluster.org.ua/.

  27. Chugay A., Stoian Ye. Cluster packing of concave non-oriented polyhedra in a cuboid. Suchasni informatsiyni systemy. 2018. Т. 2, № 1. P. 16–21.

  28. Kovalenko A.A., Romanova T.E., Stetsyuk P.I. The problem of a balanced layout of 3D-objects: A mathematical model and solution methods. Kibernetika i sistemnyj analiz. 2015. Vol. 51, N 4. P. 71–81.

  29. Stoyan Yu., Romanova T., Pankratov A., Kovalenko A., Stetsyuk P. Balance layout problems: Mathematical modeling and nonlinear optimization. In: Space Engineering. Modeling and Optimization with Case Studies (Ser. Springer Optimization and its Applications). Fasano G., PintБr J. (Eds). New York: Springer, 2016. Vol. 114. Р. 369–400.

  30. Stetsyuk P., Romanova T., Scheithauer G. On the global minimum in a balanced circular packing problem. Optimization Letters. 2016. Vol. 10, Iss. 6. P. 1347–1360.

  31. Stetsyuk P.I. Shor’s r-algorithms: theory and practice. In: Optimization Methods and Applications: In Honor of the 80th Birthday of Ivan V. Sergienko. Butenko S., Pardalos P.M, Shylo V. (Eds.). New York: Springer, 2017. P. 495–520.

  32. Stetsyuk P.I. Theory and software implementations of Shor r-algorithms. Kibernetika i sistemnyj analiz. 2017. Vol. 53, N 5. P. 43–57.

  33. Stetsyuk P.I. Ellipsoid methods and r-algorithms. Chisinau: Eureka, 2014. 488 p.

  34. Stetsyuk P.I., Likhovid O.P. A parallel algorithm for a balanced circular packing problem computer program. Certificate of registration of copyright for the work N 62184. Ukraine. Ministry of Education and Science. State Department of Intellectual Property. Registration Date 20.10.2015.

  35. Likhovid A.P. On the implementation of a parallel algorithm for solving the problems of equilibrium packaging. The theory of optimal solutions. Kyiv: V.M. Glushkov Institute of Cybernetics. NAS of Ukraine, 2015. P. 154–159.
Editorial Board Announcements Abstracts Authors Archive
about scope office editorial board instructions for authors subscriptions contacts
© 2019 Kibernetika.org. All rights reserved.