МЕТАЕВРИСТИЧНІ МЕТОДИ ВИРІШЕННЯ ЗАДАЧІ ГІЛЬЙОТИННОГО РОЗКРОЮ

Г. С. Іващенко; А. І. Кононенко; Д. О. Тимошенко

doi:10.26906/SUNZ.2025.1.91-95

Автор(и)

Г. С. Іващенко Харківський національний університет радіоелектроніки
А. І. Кононенко Харківський національний університет радіоелектроніки
Д. О. Тимошенко Харківський національний університет радіоелектроніки

DOI:

https://doi.org/10.26906/SUNZ.2025.1.91-95

Ключові слова:

задача гільйотинного розкрою, коефіцієнт використання матеріалу, генетичний алгоритм, мурашиний алгоритм, рівневі алгоритми, евристика, метаевристика, селекція, кросовер, мутація

Анотація

Актуальність. Оптимізація розкрою листових матеріалів є важливою задачею в промисловості, що
дозволяє мінімізувати відходи та зменшити витрати у виробництві. У цій роботі розглядаються методи вирішення
задачі гільйотинного розкрою, включаючи рівневі алгоритми (зокрема, Best Fit Decreasing), генетичні алгоритми та
алгоритм мурашиної колонії. Метою даної роботи є дослідження ефективності евристичних та метаевристичних
підходів до задачі розкрою та порівняння їх за критеріями швидкодії та коефіцієнта використання матеріалу.
Об’єктом дослідження є процеси побудови розкрою листових матеріалів на прямокутні частини з мінімізацією відходів. Предметом дослідження є метаевристичні алгоритми для вирішення задач гільйотинного розкрою листового матеріалу. Результати. У даній роботі розглядаються особливості застосування евристичних та метаевристичних підходів для вирішення задачі розкрою листового матеріалу. Представлені результати експериментальних досліджень, що демонструють переваги та недоліки кожного з запропонованих підходів для рішення поставленої задачі.
Висновок. Найбільшу швидкодію забезпечує запропонований метод на основі алгоритму Best Fit Decreasing (BFD),
проте найвищу точність демонструє підхід на основі мурашиного алгоритму.

Завантаження

Посилання

1. Кононенко А.І., Іващенко Г.С. (2023), “Аналіз методів вирішення задачі розкрою листового матеріалу”, III Всеукраїнська студентська наукова конференція “Науковий простір: аналіз, сучасний стан, тренди та перспективи“, С. 123-124, doi:https://doi.org/10.36074/liga-ukr-16.06.2023

2. Lodi A., Martello S., Vigo D. (2002), “Recent advances on two-dimensional bin packing problems”, Discrete Applied Mathematics, Vol. 123/124, pp. 373-380, doi: https://doi.org/10.1016/S0166-218X(01)00347-X

3. OuYang Q., Xu H. (2015), “The study of comparisons of three crossover operators in genetic algorithm for solving single machine scheduling problem”, International Conference on Manufacturing Science and Engineering (ICMSE 2015), Atlantis Press, pp. 293-297, doi: https://doi.org/10.2991/icmse-15.2015.55

4. Bortfeldt A. (2006), “A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces”, European Journal of Operational Research, Vol. 172, No 3, pp. 814-837, doi: https://doi.org/10.1016/j.ejor.2004.11.016

5. Kazakovtsev L.A., Stanimirovic P.S. (2013), “An Approach to the Multi-facility Weber Problem with Special Metrics”, European Modelling Symposium (EMS), pp. 119-124, doi: https://doi.org/10.1109/EMS.2013.21

6. Kumar R., Memoria M., Thapliyal M., Kirola M., Ahmad I., Gupta A., Tyagi S., Ansari N. (2022), “Analyzing The Performance Of Crossover Operators (OX, OBX, PBX, MPX) To Solve Combinatorial Problems”, 2022 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COM-IT-CON), pp. 817-821, doi: https://doi.org/10.1109/COM-ITCON54601.2022.9850689

7. Валеева А.Ф., Петунін А.А., Файзрахманов Р.І. (2006), “Застосування конструктивних евристик у завданнях розкрою-упаковки”, Додаток до журналу «Інформаційні технології», № 11, С. 1-24.

8. Chopard B., Tomassini M. (2018), “The Ant Colony Method”, An Introduction to Metaheuristics for Optimisation, pp. 81-96, doi:https://doi.org/10.1007/978-3-319-93073-2_5

9. Валеева А.Ф., Петунін А.А., Файзрахманов Р.І. (2007), “Застосування конструктивної метаевристики «мурашина колонія» до завдання гільйотинного прямокутного розкрою”, Вісник Башкирського університету, Т. 12, № 3, С. 12-14.

10. Петунин А.А., Полевов А.В., Куреннов Д.В. (2005), “Про один підхід до вирішення завдань розкрою-упаковки”, Конструювання та технологія виготовлення машин: Збірник наукових праць, Ч. 2, Вісник УДТУ – УПІ, № 18 (70), С. 212-216.

11. Орлов А.Н., Курейчик В.В., Кудрякова Т.Ю. (2015), “Комбінований алгоритм розв'язання задачі прямокутного розкрою”, Праці Конгресу з інтелектуальних систем та інформаційних технологій «IS&IT’15», С. 212-217.

12. Валіахметова Ю.І., Телицький С.В. (2012), “Застосування систем автоматизованого проектування карт розкрою в суднобудуванні”, Вісник ВДТУ, № 6, С. 38-43.

13. Whitwell G. (2004), “Novel Heuristic and Metaheuristic Approaches to Cutting and Packing”, BSc Thesis Submitted to the University of Nottingham for the degree of Doctor of Philosophy, School of Computer Science and Information Technology, pp. 68-71.

14. Подлазова А.В. (2008), “Генетичні алгоритми на прикладах вирішення задач розкрою”, Проблеми управління, № 2, С. 57-63.

15. Валеева А.Ф. (2005), “Застосування метаевристики мурашиної колонії до задач двомірної упаковки”, Інформаційні технології, № 10, С. 36-43.