УДК 519.85
ТЕХНОЛОГИИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ
ЗАДАЧ ГЕОМЕТРИЧЕСКОГО ПРОЕКТИРОВАНИЯ
Аннотация. В работе описано применение технологий параллельных вычислений на системах
с общей памятью и распределенной памятью для решения оптимизационных задач геометрического проектирования.
Первая технология базируется на максиминных свойствах phi-функций для составных объектов, а вторая технология использует стратегию мультистарта и методы минимизации негладких функций. Это позволило в несколько раз уменьшить затраты времени при поиске локально
оптимальных размещений 2D и 3D объектов и получить лучшие результаты по значению целевой функции.
Ключевые слова: размещение геометрических объектов, phi-функция, нелинейное программирование, параллельные вычисления.
ПОЛНЫЙ ТЕКСТ
Романова Тетяна Євгеніївна,
доктор техн. наук, професор, провідний науковий співробітник Інституту проблем машинобудування ім. А.М. Підгорного НАН України, Харків,
tarom27@yahoo.com
Стецюк Петро Іванович,
доктор фіз.-мат. наук, завідувач відділу Інституту кібернетики ім. В.М. Глушкова НАН України, Київ,
stetsyukp@gmail.com
Чугай Андрій Михайлович,
доктор техн. наук, старший науковий співробітник, старший науковий співробітник Інституту проблем машинобудування ім. А.М. Підгорного НАН України, Харків,
chugay@ipmach.kharkov.ua
Шеховцов Сергій Борисович,
кандидат техн. наук, доцент, доцент кафедри Харківського національного університету внутрішніх справ,
ep109@ukr.net
СПИСОК ЛИТЕРАТУРЫ
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Stoyan Yu., Yakovlev S. Configuration space of geometric objects. Cybernetics and Systems Analysis. 2018. Vol. 54, N 5. P. 716–726.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. Санкт-Петербург: БХВ-Петербург, 2002. 608 с.
- Кластерный комплекс Института кибернетики. Кластерный комплекс СКИТ. URL: https:// icybcluster.org.ua/.
- Chugay A., Stoian Ye. Cluster packing of concave non-oriented polyhedra in a cuboid. Сучасні інформаційні системи. 2018. Т. 2, № 1. С. 16–21.
- Коваленко А.А., Романова Т.Е., Стецюк П.И. Задача балансной компоновки 3D-объектов: математическая модель и методы решения. Кибернетика и системный анализ. 2015. Т. 51, № 4. С. 71–81.
- 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.
- 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.
- 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.
- Стецюк П.И. Теория и программные реализации r-алгоритмов Шора. Кибернетика и системный анализ. 2017. Т. 53, № 5. С. 43–57.
- Стецюк П.И. Методы эллипсоидов и r-алгоритмы. Эврика: Кишинэу, 2014. 488 с.
- Стецюк П.І., Лиховид О.П. Комп’ютерна програма «A parallel algorithm for a balanced circular packing problem». Свідоцтво про реєстрацію авторського права на твір № 62184. Україна. Міністерство освіти і науки. Державний департамент інтелектуальної власності. Дата реєстрації 20.10.2015.
- Лиховид А.П. О реализации параллельного алгоритма для решения задач равновесной упаковки. Теорія оптимальних рішень. Київ: Ін-т кібернетики ім. В.М. Глушкова НАН України, 2015. С. 154–159.