Routing of tool movements during sheet cutting on CNC machines. Part 1

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

Questions connected with cutting optimization under precedence conditions and constraints connected with efficient heat dissipation are studied. Arising routing problem immerses himself in the general formulation of the problem of sequential bypass of megacities with precedence conditions and cost functions with possible dependency on task list. The device of broadly understood dynamic programming (DP) is used for solution; in the case of the problem of tangible dimension the decomposition method is used also. In the latter case, optimal composition solutions that can be constructed in an acceptable time are our goal. The applied DP variant uses precedence conditions and cost functions with dependency on task list (this dependency arises in connection with thermal restrictions and especially important for thermal cutting). The algorithm based on DP is implemented on a multi-core PC. The results of solution of model examples are given. The article includes a review of the authors' previous works.

About the authors

Alexander G. Chentsov

Институт математики и механики им. Н. Н. Красовского УрО РАН

Author for correspondence.
Email: journal@electronics.ru

член-корреспондент РАН, главный научный сотрудник

Russian Federation, Екатеринбург

P. A. Chentsov

Уральский федеральный университет

Email: journal@electronics.ru

кандидат физико-математических наук, старший научный сотрудник

Russian Federation, Екатеринбург

References

  1. Gutin G., Punnen A. The traveling salesman problem and its variations. Berlin: Springer, 2002.
  2. Cook W. J. In pursuit of the traveling salesman. Mathematics at the limits of computation. Princeton, New Jersey: Princeton University Press, 2012.
  3. Гимади Э. Х., Хачай М. Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: УМЦ УПИ, 2016.
  4. Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера // Автоматика и телемеханика. 1989. Вып. 9. С. 3–33; Вып. 10. С. 3–29; Вып. 11. С. 3–26.
  5. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. М.: Мир, 1964. Т. 9. С. 219–228.
  6. Хелд М., Карп Р. М. Применение динамического программирования к задачам упорядочения // Кибернетический сборник. М.: Мир, 1964. Т. 9. С. 202–218.
  7. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и математические методы. 1965. Т. 1, Вып. 1. С. 94–107.
  8. Ченцов А. Г., Ченцов П. А. Маршрутизация в условиях ограничений: задача о посещении мегаполисов // Автоматика и телемеханика. 2016. Вып. 11. C. 96–117.
  9. Петунин А. А., Ченцов А. Г., Ченцов П. А. Оптимальная маршрутизация инструмента машин фигурной листовой резки с числовым программным управлением. Математические модели и алгоритмы. Екатеринбург: Ид-во УрФУ, 2020. 247 c.
  10. Беллман Р. Динамическое программирование. М.: ИЛ, 1960. 400 с.
  11. Мину М. Математическое программирование. М.: Наука, 1990. 486 с.
  12. Ченцов А. Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М.-Ижевск: Регулярная и хаотическая динамика, Ижевский институт компьютерных исследований, 2008. 238 с.
  13. Коробкин В. В., Сесекин А. Н., Ташлыков О. Л., Ченцов А. Г. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций // Под общ. ред. член-корр. РАН И. А. Каляева. М.: Новые технологии, 2012, 234 с.
  14. Ченцов А. Г., Ченцов А. А., Сесекин А. Н. Задачи маршрутизации перемещений с неаддитивным агрегированием затрат, ЛЕНАНД, М., 2021. 230 с.
  15. Ченцов А. Г., Ченцов П. А. Динамическое программирование в задаче маршрутизации: декомпозиционный вариант // Вестник российских университетов. Математика. 2022. Т. 27, № 137. С. 95–124.
  16. Ченцов А. Г., Ченцов П. А. Экстремальная двухэтапная задача маршрутизации и процедуры на основе динамического программирования // Тр. Ин-та математики и механики УрО РАН. 2022. Т. 28, № 2. С. 215–248.
  17. Ченцов А. Г., Ченцов П. А. Двухэтапное динамическое программирование в задаче маршрутизации с элементами декомпозиции // Автоматика и телемеханика. 2023. № 5. С. 133–164.
  18. Ченцов А. Г., Ченцов П. А. Задача маршрутизации перемещений (минимаксная постановка) // Механика, ресурс и диагностика материалов и конструкций: XVIII Международная конференция (Екатеринбург, 27–31 Мая 2024): сб. материалов. Екатеринбург: ИМАШ УрО РАН, 2024. С. 51–52.
  19. Ченцов А. Г. Динамическое программирование и декомпозиция в задачах маршрутизации с ограничениями // XIV Всероссийское совещание по проблемам управления ВСПУ-2024, Москва 17–20 июня 2024 г. С. 1184–1189.
  20. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970.
  21. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2002.
  22. Варга Дж. Оптимальное управление дифференциальными и функциональными уравнениями. М.: Наука, 1977. 624 с.
  23. Ченцов А. Г. Задача маршрутизации «на узкие места» с системой первоочередных заданий // Изв. ИМИ УдГУ. 2023. Т. 61. С. 156–186.
  24. Ченцов А. Г., Ченцов П. А. Динамическое программирование и декомпозиция в экстремальных задачах маршрутизации // Тр. Ин-та математики и механики УрО РАН. 2025. Т. 31. № 1. С. 247–272.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2026 Chentsov A.G., Chentsov P.A.