Одержано 29.09.2023; Виправлено 15.10.2023; Прийнято 28.11.2023

Надруковано 04.12.2023; Вперше Online 05.12.2023

https://doi.org/10.34229/2707-451X.23.4.5

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

УДК 519.8

Паралельний алгоритм збалансованого розрідженого пакування прямокутних паралелепіпедів

О.А. Березовський ^* ,   О.П. Лиховид,   М.Г. Стецюк

Інститут кібернетики імені В.М. Глушкова НАН України, Київ

^* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

Вступ. Різновиди задачі пакування прямокутних паралелепіпедів мають широке практичне застосування у різних сферах діяльності, наприклад, при оптимальному заповненні контейнерів, при проєктуванні та компонуванні найрізноманітніших технологічних об'єктів та систем, створенні резервних копій на знімних носіях, при оптимізації зберігання, захисту та транспортування товарів, у адитивному виробництві тощо. Дана робота продовжує дослідження за даною тематикою і присвячена задачі збалансованого розрідженого пакування заданого набору однаково орієнтованих прямокутних паралелепіпедів різних розмірів у прямокутний паралелепіпед мінімального об’єму. В ній представлено математичну модель для цієї задачі пакування та паралельний алгоритм для її розв’язування. Цей алгоритм базується на зведенні за допомогою штрафних функцій початкової задачі до задачі безумовної оптимізації, для розв’язування якої застосовується метод мультистарту, в рамках якого для пошуку локальних мінімумів з набору згенерованих початкових точок використовується r-алгоритм.

Мета роботи. Побудова математичної моделі та розроблення алгоритму розв’язання задачі  збалансованого розрідженого пакування заданого набору однаково орієнтованих прямокутних паралелепіпедів у прямокутний паралелепіпед мінімального об’єму. 

Результати. Представлено математичну модель та паралельний алгоритм для збалансованого розрідженого пакування однаково орієнтованих прямокутних паралелепіпедів у прямокутний паралелепіпед мінімального об’єму. Алгоритм базується на зведенні задачі за допомогою штрафних функцій до задачі безумовної недиференційованої оптимізації, для знаходження розв’язку якої застосовується метод мультистарту у поєднанні з r-алгоритмом  для пошуку локальних мінімумів. Наведено результати чисельних  експериментів.

Висновки. Застосування описаного в роботі алгоритму на основі методів негладкої оптимізації дозволяє покращити результати збалансованого розрідженого пакування прямокутних паралелепіпедів  за прийнятний час. Проведені чисельні експерименти показали ефективність алгоритму на практиці.

 

Ключові слова: збалансоване розріджене пакування, метод мультистарту, r-алгоритм, штрафна функція, процедура “Master-Slave”, чисельні експерименти.

 

Цитувати так: Березовський О.А., Лиховид О.П., Стецюк М.Г. Паралельний алгоритм збалансованого розрідженого пакування прямокутних паралелепіпедів. Cybernetics and Computer Technologies. 2023. 4. С. 34–42. https://doi.org/10.34229/2707-451X.23.4.5

 

Список літератури

           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.     Стецюк П.И., Бортис Г., Эмменеггер Ж.-Ф. и др. Институциональные и технологические изменения в странах с рыночной и переходной экономикой. К.: Видавничий дім "Києво-Могилянська академія", 2015. 336 с.

           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.     Стецюк П.І., Березовський О.А., Лиховид О.П., Стецюк М.Г. Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери. International Scientific Technical Journal" Problems of Control and Informatics". 2022. № 3. C. 87–100.

           8.     Лиховид А.П. О реализации параллельного алгоритма для решения задач равновесной упаковки. Теорія оптимальних рішень. 2015. С. 154–159. http://dspace.nbuv.gov.ua/handle/123456789/112413

           9.     Лиховид О.П., Стецюк П.І. Комп'ютерна програма “Паралельна програма “Збалансована упаковка кругів з заданими допустимими відстанями між ними”. Свідоцтво про реєстрацію авторського права на твір №109298. Україна. Національний орган інтелектуальної власності державне підприємство Український інститут інтелектуальної власності (Укрпатент). Дата реєстрації 10.11.2021. 40 c.

       10.     Стецюк П.И. Методы эллипсоидов и r–алгоритмы. Кишинев: Эврика, 2014. 488 с.

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна