Metaheuristic methods for solving the guillotine cutting stock problem
DOI:
https://doi.org/10.26906/SUNZ.2025.1.91-95Keywords:
guillotine cutting stock problem, material utilization rate, genetic algorithm, ant colony algorithm, level algorithms, heuristics, metaheuristics, selection, crossover, mutationAbstract
Topicality. The optimization of sheet material cutting is a critical task in the industry, enabling waste minimization and cost reduction in production. This article examines methods for solving the guillotine-cutting stock problem, including
level algorithms (specifically, Best Fit Decreasing), genetic algorithms, and the ant colony algorithm. The goal of this work is to
analyze the efficiency of heuristic and metaheuristic approaches to the cutting problem and compare them based on performance
speed and material utilization rate. The object of research is the process of cutting sheet materials into rectangular parts while
minimizing waste. The subject of research is the algorithms used to solve the guillotine-cutting stock problem. Results. This
paper explores the application of heuristic and metaheuristic approaches to solving the sheet material cutting problem. The results
of experimental research demonstrate the advantages and disadvantages of each proposed approach for solving the given problem.
Conclusions. The Best Fit Decreasing (BFD) algorithm-based method achieves the highest processing speed, whereas the ant
colony algorithm-based method demonstrates the highest accuracy.
Downloads
References
1. Кононенко А.І., Іващенко Г.С. (2023), “Аналіз методів вирішення задачі розкрою листового матеріалу”, III Всеукраїнська студентська наукова конференція “Науковий простір: аналіз, сучасний стан, тренди та перспективи“, С. 123-124, doi:https://doi.org/10.36074/liga-ukr-16.06.2023 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 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 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 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 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 DOI: https://doi.org/10.1109/COM-IT-CON54601.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 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.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
